智能 | #9 图灵停机问题

文 | HW君

本文目录：

  0. 判定问题

  1. 停机问题

  2. 数学问题的图灵机形式

  3. 判定图灵机

  4. 人工智能的局限性

0. 判定问题

即便图灵机理论影响了整个世界，但它其实只是图灵在思考希尔伯特判定问题过程中的副产物。

图灵创造出图灵机，只是为了尝试回答一个数学问题。

所以现在我们需要回过头来，讨论希尔伯特所提出的问题。

我们在《智能 | #4 通用计算机的起源》中描述过20世纪初的数学危机和希尔伯特计划。

希尔伯特在1928年的《数理逻辑原理》中提出了判定问题（Decision problem）：

是否存在一种机械过程，能够在有限步骤内判断任意给定的一阶逻辑公式是否是可证明的？

图灵通过图灵机理论，对此给出了否定解。

1. 停机问题

希尔伯特想能找到一种更加确定的机械化的推理模式，一种更加可靠的通用算法，来回答判定问题。

这种机械化的过程不依赖于某一数学家的直觉和经验，避免了人为因素或复杂步骤导致的数学矛盾。

而在构建出图灵机理论之后，图灵发现可以把判定问题重新描述为图灵机的形式。

即对于第n号图灵机，输入纸带m时其会不会停止。

这类问题被称为图灵停机问题。

我们在《智能 | #8 通用图灵机》中列出了第- 12 号图灵机：

T：0000R, 0100R,

T1：0000R,0100L,

T2：0000R,0101R,

T3：0000R,0100停,

T4：0000R,0110R,

T5：0000R,0101L,

T6：0000R,0100R,1000R,

T7：0000R,01???,

T8：0000R,01100R,

T9：0000R,0110L,

T10：0000R,0111R,

T11：0000R,0101停,

T12：0000R,0100R,1000R,

其中T、T1、T2、T5、T6、T12对于任何数 m 都不会停止。

而T11对于任何数m都会停止。

也有些图灵对于一些数会停，对另一些数则不停。

假设一个图灵机Tn在输入 m 时不能给出答案，即不能停机，那么我们将其表示为：

Tn(m) = □

这一表示包含了图灵机在某一阶段找不到下一步的指令而出现的错误。

例如T4和T7就属于这种情况：

T4(m) = □

T7(m) = □

之前看起来合格的T3其实也是如此，因为对于任何输入，它在停机之后读写头的左边都是一串空白的「...0000」，这是无意义的。

而T11才是有完整输出结果的，对于任何输入，它在停机之后读写头左边的纸带都是「...0001」，在我们的二进制表示法里代表 0 。

即对于一切的m，我们都有：

T3(m) = □

T11(m) = 0

2. 数学问题的图灵机形式

能够判定图灵机何时停机是数学中的一个重要问题。

考虑一个经典的数学题，例如「费马大定理」：

xw+ yw= zw

x , y , z > 0 , w > 2

存在任何满足这个方程的自然数集合 x , y , z , w 吗？

费马认为这个方程永远不能被满足。

我们完全可以将费马大定理转换为一个图灵停机问题。

当然为了让 x , y , z , w都可以遵循图灵机从 0 开始的计数，我们将其转换为以下形式：

( x + 1 )w + 3+ ( y + 1 )w + 3= ( z + 1 )w + 3

我们可以想象有一台图灵机，然后对其输入一条由四个数组（x , y , z , w）编码成的纸带。

机器一直运行，直到方程被满足之后，这台图灵机才停止下来。

而如果我们能够证明这个图灵机不能停下来，那么我们就证明了费马大定理。

可以用类似的方法把许多未解决的数学问题转换成图灵停机问题的形式。

除了费马大定理，还有「哥德巴赫猜想」：

比 2 大的任何偶数都是两个质数之和。

这里先不考虑偶数 4，因为只有它能被分成 2+2 的偶数的对，而大于 2 的所有质数都是奇数。

因此我们可以设计这么一台跑遍所有偶数  6 , 8 , 10 , 12 , 14...的一台图灵机，尝试把它们分成奇数的对的所有不同方法：

6 = 3 + 3

8 = 3 + 5

10 = 3 + 7 = 5 + 5

12 = 5 + 7

14 = 3 + 11 = 7 + 7

...

我们设计的这台图灵机只有当遇到了一个特定偶数，由这个偶数分成的所有的任意一对数都不是质数时，图灵机才会停止。

在这种情形下，我们就得到了哥德巴赫猜想的反例。

相反如果我们能证明图灵机不会停止，那么我们也就证明了哥德巴赫猜想。

3. 判定图灵机

上述是一些特定的数学问题。

如何将其扩展到更普遍的情况：

我们如何判定任意图灵机的是否会停止？

是否存在某种完全自动地回答停机问题的算法步骤？

图灵认为不存在这种算法，即希尔伯特判定问题是否定的：

无法找到一种通用的算法，能够在有限步骤内判定任何数学命题的真假。

图灵首先假定存在一种算法，即存在这样的一台判定图灵机 H，能够判定第n号图灵机作用于数m时能否停止。

如果能停止则输出 0，不能停止则输出 1 ：

H(n;m) = 0 ，如果Tn(m) = □

H(n;m) = 1 ，如果Tn(m) 停机

这里涉及到一个细节上的补充。

如果我们使用先前的通用图灵机 U的规则来编码 (n,m) ，即「...n111110m...」，会存在一些技术漏洞。

考虑进一些不正常工作的图灵机，例如T7，其本身为「111」，扩展之后为「110111110」，则「...111110...」无法做到将两个二进制数n和m区分开。

因此改进方式是，这里n用扩展二进制的方式来表示，而m则用通常的二进制来表示。

这是 (n;m) 和先前的 (n,m) 之间的一个小区别，算是一个细节上的完善，但本质上是同一个含义。

总而言之，图灵构建了这么一台判定图灵机 H，然后得到了一个矛盾的结果。

因此得到了希尔伯特判定问题的否定解。

我们下一期再详细展开其中的细节。

4. 人工智能的局限性

停机问题一定程度上说明了图灵机的局限性。

而当今的人工智能也属于图灵机，因此也具有同样的局限性。

后续我们还会继续讨论一些细节原理。

同样如果觉得吃力，可以适当跳过。

（本章节完，敬请期待下一节）

By HW君 @ 2025-01-11