文 | HW君
系列文章：
0. 必经之路
从本章开始，我们会花费很多的篇幅讨论图灵机的细节。
这并不是跑题，而是探索人工智能的必经之路。
图灵给世界留下了图灵机和图灵测试，每一个议题都值得仔细考究。
上一期《智能 | #4 通用计算机的起源》的末尾，我们简单地介绍了图灵机的基本组成：
（1）无限长的纸带
纸带上分为一格一格的单元，每一个格子可以储存一个符号标记；
（2）读写头
读写头可以读取纸带上当前格子的符号，也可以改写当前格子的符号；
（3）状态控制器
读写头上有一个状态控制器，其状态的数目是有限的；
（4）动作规则
读写头通过读取状态控制器当前的内部状态以及在纸带上格子的符号，来确定读写头下一步的动作：
a. 读写头写入或者擦除纸带上当前格子的标记（1表示有标记，0表示空白）；
b. 读写头在纸带上移动一格（L表示向左，R表示向右）；
c. 状态控制器转换为另一个状态；
这就是图灵机的理论模型。
也是图灵对于希尔伯特判定问题中「机械过程」的精确定义。
图灵宣称，这样的一台设备就能模拟人类所能进行的任何计算过程。
本章先从最简单的一进制图灵机开始，带大家熟悉图灵机的基础原理。
这个过程中会引用到一些数学公式，但并不复杂，仅仅需要一些耐心。
如果觉得吃力，也可以适当跳过。
1. 一进制数
如何在图灵机这么简单的规则下去实现一些计算。
图灵机无限长纸带上的每个单元格只有两种状态，有标记为1，空白为0。
为了让其能够表示自然数，我们不妨应用以下简单的一进制数表示方法（先不考虑自然数0）：
1 → 1；
2 → 11；
3 → 111；
4 → 1111；
…
即自然数 4 可以描述成这样的一条一进制纸带：
…000011110000….
这样单个空白符 0 可以作为一进制数与一进制数之间的分隔。
即自然数 6 和 8 可以放在一起描述为：
…00001111110111111110000…
对于图灵机而言，其输入是一条标有0和1数据的纸带。
图灵机读取纸带上的数据，然后根据其内部的状态控制器对纸带进行擦写和移动。
最后其输出也还是一条0和1数据的纸带。
为了便于分析，我们假设读写头总是从最左端开始读取纸带上的输入数据，从左往右移动。
然后经历若干中间过程的来来回回移动之后，最后在输出数据最右端停止。
以下为一台输入为 4 的一进制图灵机的起始状态：
在经过状态控制器的操作之后，它输出的答案为 6：
即需要输入的问题都在读写头启动前的右端纸带上，输出的答案都在读写头停止后的左端纸带上。
2. 一进制+1图灵机
读写头通过状态控制器当前的内部状态以及读取纸带上格子的符号，来确定下一步的动作：
a. 读写头写入或者擦除纸带上当前格子的标记（1表示有标记，0表示空白）；
b. 读写头在纸带上移动一格（L表示向左，R表示向右）；
c. 状态控制器转换为另一个状态；
这里我们用标签0，1，2，3，4，5……来标明不同内部状态的编号。
然后构建一个状态控制器如下的图灵机：
0 0 → 0 0 R
0 1 → 1 1 R
1 0 → 0 1 R 停
1 1 → 1 1 R
红色数字为状态编号，「→」表示转换状态。
蓝色数字为纸带上的符号，「→」左边的蓝色数字为读取头读取的值，「→」右边的蓝色数字为读取头写入的值。
「R」表示读取头向右移动一格，「L」表示向左移动一格，「停」表示机器停止，完成答案输出。
假设我们对这台图灵机输入一条标记有一进制 3 的纸带：
…00001110000….
然后观察图灵机的动作。
首先依据第一条指令，它的初始状态为0，读取头读取到0时，会变更状态为0，并写入0，然后向右移动一格。
实际上可以视为它会跳过一进制 3 前面的所有无意义的空白 0：
直到读取头遇到纸带上的第一个1，触发第二条指令，它会将内部状态变更为1，然后在当前格子上写入1，再向右移动一格：
当状态为1时，只要读取头遇到1，它都维持状态为1，然后写入1，再向右移动一格：
当状态为1而读写头遇到一个0时，触发第三条指令，状态变更为0，写入1，向右移动一格，然后停机：
停机之后，读写头左边的纸带上就输出了我们想要的答案，是一个一进制表示的数 4：
因此内部状态如下的这样一个图灵机，它执行的操作就是给一个一进制的数 +1：
0 0 → 0 0 R
0 1 → 1 1 R
1 0 → 0 1 R 停
1 1 → 1 1 R
我们不妨将这个图灵机称之为「一进制+1图灵机」。
你可以尝试用其它一进制数输入给这台图灵机，确定它是否真的可以对其进行 +1 操作。
3. 一进制×2图灵机
除了最简单的 +1 操作之外，我们也可以制作一个 ×2 操作的图灵机。
这个「一进制×2图灵机」的状态控制器为：
0 0 → 0 0 R
0 1 → 1 0 R
1 0 → 2 1 L
1 1 → 1 1 R
2 0 → 3 0 R
2 1 → 4 0 R
3 0 → 0 1 R 停
3 1 → 3 1 R
4 0 → 5 1 L
4 1 → 4 1 R
5 0 → 2 1 L
5 1 → 5 1 L
假设我们对这台图灵机输入一条标记有一进制 2 的纸带：
…0000110000….
然后观察图灵机的动作，可以看到经过了以下几个步骤：
同样的它会跳过纸带前端的所有无意义的 0 ，直到遇到第一个 1：
最终当图灵机停机的时候，读取头左边的纸带为：
…000011110000….
是一个一进制表示的 4。
虽然步骤有点冗长，但这台「一进制×2图灵机」的确完成了「2×2=4」的操作。
4. 一进制的欧几里得算法
到这里我们已经实现了两种「一进制图灵机」，它们可以进行简单的「+1」和「×2」的操作。
但这台机器可以实现的计算操作远不止这么简单。
图灵宣称的是，这样的一台设备就能模拟人类所能进行的任何计算过程。
还记不记得初中数学中求解最大公约数的欧几里得算法（辗转相除法）。
假设我们要求 1365 和 3654 的最大公约数，可以这样解算：
3654 ÷ 1365，余数924
1365 ÷ 924，余数441
924 ÷ 441，余数42
441 ÷ 42，余数21
42 ÷ 21，余数0
即 21 为 1365 和 3654 的最大公约数。
同样的，我们可以构造出一台「一进制欧几里得算法图灵机」，用来求解两个一进制数的最大公约数。
这样的一台图灵机的状态控制器如下：
0 0 → 0 0 R
0 1 → 1 1 L
1 0 → 2 1 R
1 1 → 1 1 L
2 0 → 10 0 R
2 1 → 3 0 R
3 0 → 4 0 R
3 1 → 3 1 R
4 0 → 4 0 R
4 1 → 5 0 R
5 0 → 7 0 L
5 1 → 6 1 L
6 0 → 6 0 L
6 1 → 1 1 L
7 0 → 7 0 L
7 1 → 8 1 L
8 0 → 9 0 L
8 1 → 8 1 L
9 0 → 2 0 R
9 1 → 1 1 L
10 0 → 0 0 R 停
10 1 → 10 1 R
对这台图灵机输入用 0 隔开的两个一进制数，就可以用求解它们的最大公约数。
例如输入一组一进制的 4 和 6 ：
…0000111101111110000…
在经过许多步骤之后，图灵机停机，我们可以得到如下的纸带：
…0000110000….
即最大公约数为 2 。
「一进制欧几里得算法图灵机」比较复杂，有时间精力的读者可以尝试动手推算一遍。
虽然只是计算很简单的 4 和 6 的最大公约数，但读写头一共来回移动了143次（如果我没有数错的话）。
如果你记忆力惊人，那么理论上你可以在脑海中模拟整个计算过程，因为人脑也可以等价于图灵机。
当然如果遇到困难，不妨也可以借助一张纸和一支笔，作为记忆的扩展。
这里面的魅力就在于，哪怕是一个完全不理解欧几里得算法的小学生，只要按照图灵机的规则一格一格地机械计算，就一定能够得到正确的答案。
而这就是希尔伯特在判定问题里想要的「机械过程」：
一种更加确定的机械化的推理模式，不依赖于某一数学家的直觉和经验，可以避免人为因素或复杂步骤导致的数学矛盾。
5. 万里长征
这一期从最简单的「一进制图灵机」开始，带大家初步熟悉图灵机的基础原理。
图灵机的魅力就在于，哪怕是如此简陋的一进制图灵机，它的数学模型和我们现代的计算机也是等价的。
甚至可以断言，一进制图灵机和我们的手机、电脑等通用计算机其实没有区别。
图灵认为这样的一台设备就足以模拟人类所能进行的任何计算过程。
当然「一进制图灵机」是一种效率很低的图灵机。
我们固然可以用一进制的 1111 来表示十进制的 4，但假如想表示十进制数 10000，那就需要有一万个1。
这显然无法胜任更加复杂的数学计算。
但这只是10000里长征的第一步，接下来我们会继续讨论图灵机的细节。
直到抵达人工智能。
（本章节完，敬请期待下一节）
By HW君 @ 2024-12-30