停机问题

我在网上查看了几个讲解“停机问题”的视频后，发现评论区有很多人反驳此证明的正确性。 我仔细想了一下，觉得应该是视频讲得都不是很清楚，关键的逻辑点没有讲到。我看了视频后也是相当困惑的。 所以这里我就讲一下我自己的理解。

1. 假设有一台机器A，可以解决某个问题。输入一些数据后得到结果，设输入为X，输出为Y。 那么机器就可以视为一种固定逻辑、运算的组合。相当于我们写一段程序A，输入X，那么就会输出此算法的结果Y。程序的算法本身是固定的，那么运算过程是固定，则必然输出固定的结果。 这有点类似函数的概念，但是略有不同。例如 y^2 = x 的计算方法，y是会有两个值。实际为 y = sqrt(x) 或 y = -sqrt(x)。但是我们可以将两个结果值整合在一起为表示为一个结果。 例如，2个普通骰子的抛掷结果是 [2, 12]； 单个输入的结果值可能是多个，但实际可以视为1个。 那么机器A，接受输入2，得到结果[2, 12]。就可以等价视为算法A，输入X，得到答案Y。

2. 当然要得到答案，需要有限次的计算。图灵假设的纸带机器，和现在计算机的基本原理类似（或反过来说）。程序就是一段文字（指令+数据），加载到内存后，CPU不断在纸带上跳转，读取或写入。最终达到一个停止状态，纸带上保存着结果。当然程序很容易出现死循环，在两个或多个地方循环跳转，例如程序编写错误，或意外的输入值。

3. 是否有一个机器H，来验证机器A，在任意的输入X下，是否会导致死循环？这个就是停机问题。 可以等价为，是否存在一种算法，来验证任意算法在任意输入是否有解。 前面说了机器本身就是一段程序，程序就是一段文字，那么机器本身也可以视为一种输入。

4. 首先假设机器H存在，有以下定义：

H 万能的验证机（输入[机器A、输入X]，输出YES或者NO）

A 被验证的机器（不重要）

P 复制机（输入机器A，输出[机器A，机器A]）

B 取反机（输入YES输出NO，或输入NO输出YES）

我们将 P、H、B三台机器连接起来，称之为H+机器。 那么看一下 输入H+到H+机器会发生什么？

1. 输入H+被P复制机复制一份，输出 H+、H+ 。

2. 输入 H+、H+ 到 H万能的验证机。

H会验证机器H+，在输入H+后，是否会导致死循环。

3.1 假设不会导致停机（死循环），会输出YES。

输入YES到B取反机，会输出NO。 那么H+机器，在输入H+的时候，输出的结果是NO。而上一步 H已经验证机器H+，在输入H+后，不会导致停机。结果与假设矛盾，所以此假设不成立。

3.2 假设会导致停机，会输出NO。

输入NO到B取反机，会输出YES。 那么H+机器，在输入H+的时候，输出的结果是YES。而上一步 H已经验证机器H+，在输入H+后，会导致停机。结果与假设矛盾，所以此假设不成立。

4.所以机器H对H+机器的验证功能失效，所以不存在万能的验证机。 这就等价于无法有一个程序来判断任意程序在任意输入，是否会停机。

其实条件比较苛刻，上述证明无法说明不存在一个机器M，可以验证任意机器，在特定输入下是否会停机。 因为前面我们将H+、和H+传入了H，这里只能是任意输入。 大概就是意思就是，我编写了一个服务器程序，在接受外部输入源（恶意攻击等），是否会导致服务器停机。没有通用的方法，来证明此程序是否会卡死。 但这不意味着，不能通过此程序的逻辑来证明此程序不会卡死。例如不管输入什么，我都直接抛弃掉，那此程序就不会停机。 关键点在于“任意问题”和“任意算法+任意输入”的关系。 例如五次方程是否有求根公式这个问题，任意算法就是求根公式，任意输入就是五次方程。 这种问题，必然没有通用的程序来判断，某个算法是否会卡死。这意思是，不能证否，不能证明此算法是错的。更不能证明此算法是对的。

所以网上有些人说的“停机问题可以说明，不存在万能的程序来证明任意问题是否有解”，应该是错误的。应该是说明了，不存在万能的程序来证明任意问题的解法是否错的。

从现实意义来看，人在脑中用逻辑思维来解决一个问题时，偶尔就会陷入死循环。但还是可以突然切掉电源去做其他事情。所以这个证明只能解释纯逻辑构建的、独立的世界。比如数学、物理等等，那可能里生活太远了 ？不过AI也是一种建立到纯计算逻辑的机器。 所以AI无法成为一个可以验证任何算法是否错误的工具。

5. 假设机器A是一个定理推导器，输入一个定理，它通过基本的公理，来计算推导定理，如果得出结果，则输出YES，如果推不出来则会停机。（因为定理就是由公理组合而来的） 那么机器A就可以用来验证某个猜想是否是定理。 如果机器H存在，那么就可以判断机器A在猜想X的输入下是否会停机，如果不会停机，则说明此猜想是对的。 不过前提是需要存在这个机器A，但是我们在学数学的时候，不也是通过以前学的知识，来推导的吗？所以机器A是很有可能存在的，不管它的运算时间有多久，只要用机器H说明它不停机，则说明这个猜想是真的。 我估计网上将“停机问题”的效果夸大和这个有点关系。