文章索引

文 | HW君

系列文章：

0. 前言

这一节讨论的东西很少，但却有必要单独成为一章。

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

这一章我们则会展示，存在着一些情况，一定没有办法判定其是否可以停机。

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

我们找到了一种图灵机的局限性，并且有一种改善这种局限性的方法。

这对于人工智能这一图灵机系统来说也同样如此。

1. 受限的判定图灵机

在上一期《智能 | #10 康托尔对角线与停机悖论》中，我们证明了万能的判定图灵机 H 并不存在。

但假设我们后退一步，不假定判定图灵机 H 对所有图灵机都能判定，而是假定它有时可以有效地工作。

这个受限的判定图灵机 H 构造如下：

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

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

即当被判定的 T_n (m) = □ 不停机时，判定图灵机 H 也有可能不停机而得到 H (n ; m) = □ 。

这样上一期的 T_n (m) 阵列表格中，我们就不再把所有的 □ 替换为 0，而是留下了一部分 □ 。

只要 H (n ; m) = □ ，我们就将得到一个 □ 。

而以下的运算仍然是成立的：

□ × □ = □

1 + □ = □

同样使用康托尔对角线方法，得到对角线上 + 1 后的元素为：

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

将 m = n = k 代入后得到：

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

如果 T_k (k) 停止，那么我们就得到 H (k ; k) = 1，于是：

1 + T_k (k) = T_k (k)

这个式子是不成立的。

因此 T_k (k) 不能停止。

于是我们能够得到结论：

T_k (k) = □

然而，算法不能「知道」这一信息。

因为如果算法能够知道 T_k (k) = □ ，那么 H (k ; k) = 0，则我们会得到：

1 + 0 = □

这个式子也是不成立的。

这样我们就找到了受限的判定图灵机 H 的一个弱点。

那就是存在着这样一个我们知道，但判定图灵机 H 不知道的信息：

T_k (k) = □

事实上不管是哪一个 H，我们都可以通过合适的步骤找到合适的 k ，使得 T_k (k) 击败 H。

而如何找到合适的 k 的步骤，同样可以构成一个 H+ 。

这也意味着，由于 H+ 比 H 多知道了「 T_k (k) = □ 」这一额外信息，所以 H+ 可以改善 H 。

而一台图灵机即为一个算法过程。

这就让我们明白了算法的局限性，以及如何超越算法。

这是图灵停机问题留下的另一个深刻的洞见。

而要理解它，则需要拜访另一位传奇的人物，香农，以及他的信息论。

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

By HW君 @ 2025-01-12