智能 | #10 康托尔对角线与停机悖论

文 | HW君

本文目录：

  0. 前言

  1. 遍历停机数列

  2. 康托尔对角线

  3. 方程悖论

  4. 结语

0. 前言

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

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

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

1. 遍历停机数列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

这个计算步骤为：

Tn(m) ×H(n;m)

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

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

□ × 0 = 0

于是现在这张表变成了：

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

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

Q(n;m) =Tn(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，因此可以假设这个新的数列是Tk(n) ：

Tk(n) = 1 +Q(n;n) = 1 +Tn(n) ×H(n;n)

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

然而这是不可能的。

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

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

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

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

出现了一个悖论。

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

3. 方程悖论

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

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

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

Tk(n) = 1 +Tn(n) ×H(n;n)

将n=k代入得到：

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

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

Tk(k) = 1 +Tk(k)

这个等式是不成立的。

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

□ = 1 + 0

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

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

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

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

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

4. 结语

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

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

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

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

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

By HW君 @ 2025-01-12