智能 | #11 超越算法

文 | HW君

本文目录：

  0. 前言

  1. 受限的判定图灵机

  2. 超越算法

0. 前言

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

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

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

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

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

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

1. 受限的判定图灵机

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

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

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

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

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

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

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

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

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

□ × □ = □

1 + □ = □

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

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

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

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

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

1 +Tk(k) =Tk(k)

这个式子是不成立的。

因此Tk(k) 不能停止。

于是我们能够得到结论：

Tk(k)  = □

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

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

1 + 0 = □

这个式子也是不成立的。

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

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

Tk(k)  = □

2. 超越算法

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

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

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

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

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

算法如此，人工智能如此，人类智能也是如此。

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

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

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

By HW君 @ 2025-01-12