分享本周所学——停机问题与可计算性

article/2025/8/29 5:15:04

大家好，欢迎来到《分享本周所学》第七期。本人是一名人工智能初学者，刚刚大一。大一学校里学的课程主要还是偏理论方面的，我感兴趣的人工智能方面的课程到大二才会开，所以目前只能自己瞎搞搞研究，最近在做点AI作曲之类的项目。最近学校在学关于停机问题的一些分析。停机问题是个挺经典的问题，我觉得还挺有意思的，就想和大家分享一下。

读懂这篇文章需要你知道任意一个语言的基本语法并了解循环结构。

啥是停机问题啊

1. 停机问题的定义

2. 停机问题的分析

3. 停机问题的意义与重要性

4. 我个人对于停机问题的思考

上期文章链接：

分享本周所学——概率论：贝叶斯更新详解

本期封面：

啥是停机问题啊

不知道大家有没有遇到过这样的问题：编程的时候写一个while循环，然后忘了在循环里面给循环变量赋值了，结果导致程序陷入死循环了，永远都停不下来。这个时候我们一般需要手动让程序停下来。我在刚接触编程那会老是犯这种错误。停机问题就和这种程序进入死循环的情况有很大的关联。

1. 停机问题的定义

为了解决程序可能陷入死循环的问题，我们希望存在一个能够判断程序是否会进入死循环的程序。我们定义这个用来判断一个程序是否会进入死循环的程序为程序P。对于任意程序p和输入i而言， $P(p,i)$ 可能返回两个结果：true和false。如果返回结果为true，代表如果在运行程序p时将i作为输入，那么程序p会陷入死循环；如果为false，则代表p不会陷入死循环。

现在我们定义另一个程序 $P^+$ 。假设有一个程序p可以接收一个程序作为输入，那么它就可以将自己作为自己的输入（这在现实中是可行的，比如Pascal的编译器可以用Pascal来书写）。对于这样的一个程序p，我们调用 $P(p,p)$ 。如果 $P(p,p)$ 为true，那么 $P^+(p)$ 会强制终止程序执行；如果 $P(p,p)$ 为false， $P^+(p)$ 会执行一个死循环。P+可以用以下代码来表示：

# P_plus.py
import sysdef P(p, i):# 判断将i输入程序p是否会导致死循环passif __name__ == '__main__':# 读取程序pif P(p, p):sys.exit()while True:continue

// P_plus.cpp
bool P(char* p, char* i) {// 判断将i输入程序p是否会导致死循环
}int main() {// 读取程序pif (P(p, p))return 0;while (true)continue;
}

那现在问题来了，如果将 $P^+$ 输入 $P^+$ ，会发生什么呢？也就是说， $P^+ \left ( P^+ \right )$ 会得到什么运行结果？

2. 停机问题的分析

想要知道 $P^+ \left ( P^+ \right )$ 的执行结果，我们需要先知道 $P \left ( P^+ , P^+ \right )$ 的执行结果。我们假设 $P \left ( P^+ , P^+ \right )$ 为true，也就是说， $P^+ \left ( P^+ \right )$ 会导致 $P^+$ 陷入死循环。这时，我们会强制终止运行，这样一来， $P^+$ 就不会陷入死循环了，这与上面说到的 $P^+ \left ( P^+ \right )$ 导致 $P^+$ 陷入死循环矛盾。

如果我们假设 $P \left ( P^+ , P^+ \right )$ 为false，也就是 $P^+ \left ( P^+ \right )$ 不会导致 $P^+$ 陷入死循环，那么 $P^+$ 就会执行一个死循环，这与上面说的 $P^+ \left ( P^+ \right )$ 不会导致 $P^+$ 陷入死循环矛盾。

因此，无论如果，这个程序在运行过程中都会产生自相矛盾的结果，那么我们就可以得到一个结论：程序P，也就是判断一个程序是否进入死循环的程序，是不存在的。

3. 停机问题的意义与重要性

停机问题给人的感觉就像一个程序员版的理发师悖论。那这个问题除了好玩之外，能不能说明什么问题呢？

我认为停机问题说明的最主要的问题就是，计算机并不是无所不能的。自从上世纪40、50年代，人们用错综的电子管和磁带编织成世界上最初的一批计算机开始，人类的计算机技术就在以极快的速度不断发展。如果有一天，极为精巧的电路设计和皮米甚至飞米级别的制造工艺使得计算机的储存空间和运算速度达到几乎无限，到那时，计算机能解决宇宙中的一切问题吗？答案是否定的，停机问题就是一个很好的反例。

这也引入了计算机领域一个很重要的概念——可计算性。一个问题是否是“可计算的”，取决于它能否用计算机来解决。我们这里讨论的停机问题，就是一个不可计算的问题。

4. 我个人对于停机问题的思考

以下纯属个人有感而发，而且纯属瞎想，不想看的话可以跳过（指直接去结尾给我点赞）。

我们来思考这样一个问题：人类是否能够判断一个程序是否会陷入死循环？

这个问题似乎让停机问题变得更加哲学了。稍微思考一下，人类似乎可以判断一个程序是否会陷入死循环。对于一些简单的程序，比如C++中的“while (true) continue;”，我们一眼就看出来这必然是个死循环。对于稍微复杂一点的程序，我们稍微研究分析一下，也能给出一个正确的结论。

但是人类是怎么思考的呢？人类的思考是通过人脑中的几百亿个神经元互相连接，通过几十种神经递质传递信息来完成的。然而，每一个神经元的运作方式都是固定的，现代的神经科学也已经对单个神经元的运作方式有了比较透彻的了解。那么，我们是不是也可以推断，大脑中的几百亿个神经元互相连接，它们作为一个整体的运作方式也是固定的？换句话说，我们人类的运作方式，是不是也是固定的？如果真是这样，那么人类是不是和计算机没有区别？

我们甚至也可以把人类看作一种程序，我们接收的输入来自自然环境，比如光线、声波以及我们接触和摄入的各种物质，而我们的大脑会根据一个固定的机制对这些输入作出回应。

再回到刚才的问题。假设我们把“人类判断一个程序是否会陷入死循环”这一过程称为过程P，把人类在阅读一个程序时接收到的一系列视觉信号称为p，把被判断的程序接收到的输入称为i，那么 $P(p,i)$ 是有解的吗？

这就交给各位来思考了。