文章索引

文 | HW君

系列文章：

0. 前言

为了回答希尔伯特的判定问题，图灵构造了图灵机理论，并将判定问题重新描述为图灵机的形式，即图灵停机问题。

图灵停机问题仍然有一些比较复杂的细节需要讨论，理解它有助于我们更好地理解同为图灵机的人工智能的局限性。

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

1. 遍历停机数列

在《智能 | #9 图灵停机问题》中我们介绍了，图灵构造出了一个判定图灵机 H ，其形式如下：

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

H (n ; m) = 1 ，如果T_n (m) ≠ □

判定图灵机 H 的作用是，如果第 n 号图灵机 T_n 作用于数 m 时不能停机，就输出 0，能停机则输出 1。

图灵给出的结论是，不存在这样的一台判定图灵机 H。

要考察这一断言，让我们先想象一个无穷的阵列，它列出所有的图灵机作用于所有的输入得到所有的输出。

阵列的第 n 行展现当第 n 号图灵机应用于不同的输入 0 , 1 , 2 , 3 , 4 …时的输出。

即 T_n (m) 可以展示为以下阵列形式：

注意这里表格内的输出只是举例，并非真实输出的结果。

因为我们之前分析过第 0 – 12 号图灵机，即 n 小于11的所有图灵机都不能停机，只能得到 □ ，而 n = 11 的图灵机只能得到 0。

但这里只是想要直观地展示这张表可能的情况，因此我们任意地填充进去了一些结果，让这张表看上去不那么无聊。

我们不需要设计一个算法实际去计算得到这么一个阵列，而是假设这张表已经出现在我们面前了。

如果我们真的去计算这么一个阵列，那就会发现那些不停机的 □ 会导致问题，因为图灵机在 □ 的这个位置会一直不停算下去。

因此我们根本不知道 □ 应该具体放在哪些位置上。

然后假设存在判定图灵机 H ，则它会告诉我们不停机的 □ 会在哪些地方发生：

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

H (n ; m) = 1 ，如果T_n (m) ≠ □

这样我们就有了一种可以产生这张表的计算步骤，将表里所有的 □ 替换为 0 。

这个计算步骤为：

T_n (m) × H (n ; m)

有个小细节是这里使用数学运算顺序的普通习惯，在右边的先进行。

并且，以下运算是成立的：

□ × 0 = 0

于是现在这张表变成了：

所有不停机的 □ 都变成了可以停机的 0 了。

因此理论上存在着一台图灵机 Q，当它作用于一对数 (n , m) 时，可以得到这张表中的所有数据：

Q (n ; m) = T_n (m) × H (n ; m)

首先这个Q (n ; m) 是可以停机的（可计算的），因为它的结果里没有 □ 元素。

而这张表已经遍历了所有的第 n 号图灵机，以及对其输入自然数 m = 0 , 1 , 2 , 3 , 4 …… 得到的数列。

因此一定包含了所有的第 n 号图灵机输入自然数 m = 0 , 1 , 2 , 3 , 4 …… 后所有元素都可以停机的情况。

而这个可以停机的第 n 行数列中的所有元素不为 0 。

2. 康托尔对角线

现在我们观察这张表在对角线上的元素：

这些元素提供了一个数列：

0 , 0 , 1 , 2 , 1 , 0 , 3 , 7 , 1 ……

现在将它们都 + 1 得到新的数列：

1 , 1 , 2 , 3 , 2 , 1 , 4 , 8 , 2 ……

因为这张表是可计算的，即 Q (n ; m) 可以停机的。

而 + 1 步骤也是一个清楚的可计算步骤，因此新的数列也是一个可计算得到的序列，即也是可以停机的。

而对角线步骤是令 m = n ，因此可以假设这个新的数列是 T_k (n) ：

T_k (n) = 1 + Q (n ; n) = 1 + T_n (n) × H (n ; n)

而因为我们的表已经包含了所有的可停机的序列，因此新的序列也必定包含在这张表之中。

然而这是不可能的。

因为新序列在第1行与第1个元素不同（相差1），在第2行与第2个元素不同，在第3行与第3个元素不同……

新序列的每一列的元素都会与这张表的每一行的同列元素不同，因此它不可能出现在这张表之内。

而我们前面说了，这张 Q (n ; m) 的表遍历了所有的第 n 号图灵机输入自然数 m = 0 , 1 , 2 , 3 , 4 …… 后所有元素都非 0 （可以停机）的情况。

但现在出现了一个所有元素都非 0 的数列 T_k (n) ，而 T_k (n) 却并不在 Q (n ; m) 这张表之内。

出现了一个悖论。

因此万能的判定图灵机 H 并不存在。

3. 方程悖论

用康托尔对角线方法来阐述停机问题是比较直观的。

但我们也可以使用更加一般的分析方法来说明这个问题。

对于已经构造出来的 T_k (n) ，有：

T_k (n) = 1 + T_n (n) × H (n ; n)

将 n = k 代入得到：

T_k (k) = 1 + T_k (k) × H (k ; k)

假设 T_k (k) 停机，即 T_k (k) ≠ □ ，于是 H (k ; k) = 1，那么就得到了：

T_k (k) = 1 + T_k (k)

这个等式是不成立的。

假设 T_k (k) 不停机，即 T_k (k) = □ ，于是 H (k ; k) = 0，那么就得到了：

□ = 1 + 0

这个等式同样是不成立的。

因此无论如何假设，都导向了不成立的结果。

因此万能的判定图灵机 H 并不存在。

因此不存在判定数学问题的一般算法。

希尔伯特的判定问题为否定解。

4. 结语

至此我们只是展示了，至少有些数学问题我们没有办法判断是否可以停机。

实际上我们还没有展示，存在着一些情况，我们一定没有办法判定其是否可以停机。

而神奇的地方在于，我们会发现在算法内部无法判定的数学问题，却可以通过在算法外部引入额外信息来进行判定。

同样的后续仍然会涉及一些细节，如果觉得吃力，可以适当跳过。

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

By HW君 @ 2025-01-12