文 | HW君
系列文章：
- 智能 | #0 人工智能的哲学原理
- 智能 | #1 在神经网络之前
- 智能 | #2 人工智能的三种流派
- 智能 | #3 可计算性，在图灵机之前
- 智能 | #4 通用计算机的起源
- 智能 | #5 一进制图灵机
- 智能 | #6 扩展二进制图灵机
0. 在通用图灵机之前
在连续两期介绍了略显枯燥的「一进制图灵机」和「扩展二进制图灵机」之后，我们终于快迎来图灵机理论最精彩的部分了。
图灵在构思图灵机的时候，定义了「通用图灵机」的概念。
它的核心思想就是任意图灵机A、B、C…的内部控制器也可以被编码成一段纸带，放到一个特定的图灵机U里进行执行。
这样图灵机U就可以模仿出任意图灵机A、B、C…的行为。
而这台能模仿任意图灵机的万能的图灵机U就是通用图灵机。
这是一个影响了世界的思想洞见。
现代的软件产业就是建立在这个理论基础之上的：
被编码成纸带的图灵机就是软件。
冯诺依曼设计的计算机被人称为「冯诺依曼架构」，其核心思想就是存储程序，而理论就来源于通用图灵机。
我们今天的电脑、手机……相同的硬件上可以安装五花八门的不同软件，实现各种各样的功能，其起源就是图灵的这一深刻洞见。
从「扩展二进制图灵机」到「通用图灵机」之间还有一段路程。
其细节比较复杂，但我们认为这是值得向你展示的。
同样如果觉得吃力，可以适当跳过。
1. 编码一台图灵机
在上一期《智能 | #6 扩展二进制图灵机》中我们提到了一个一台「扩展二进制+1图灵机」。
它的状态控制器如下：
0 0 → 0 0 R
0 1 → 1 1 R
1 0 → 0 0 R
1 1 → 2 1 R
2 0 → 3 0 L
2 1 → 2 1 R
3 0 → 0 1 R 停
3 1 → 4 0 L
4 0 → 5 1 L
4 1 → 4 1 L
5 0 → 6 0 R
5 1 → 2 1 R
6 1 → 7 1 R
7 0 → 3 1 R
7 1 → 7 0 R
这里我们试着考虑如何将这台图灵机编码成一条纸带。
在这个过程中需要有一些细节上的处理。
首先我们其实不需要对「→」左边的所有符号进行编码，但代价是需要插入一些虚指令，让整个表更规范一点，确保没有顺序上的空隙。
例如，原先的状态控制器应该补充为：
0 0 → 0 0 R
0 1 → 1 1 R
1 0 → 0 0 R
1 1 → 2 1 R
2 0 → 3 0 L
2 1 → 2 1 R
3 0 → 0 1 R 停
3 1 → 4 0 L
4 0 → 5 1 L
4 1 → 4 1 L
5 0 → 6 0 R
5 1 → 2 1 R
6 0 → 0 0 R （虚指令，合并到表后不改变任何事情）
6 1 → 7 1 R
7 0 → 3 1 R
7 1 → 7 0 R
增加的「6 0 → 0 0 R」这条虚指令不会改变任何东西，但可以让「→」左边的指令符合一定的规则。
这样我们可以依照读到的顺序确定「→」左边的指令，因此「→」左边的指令全都可以被省略掉。
又因为「L」和「R」就足以将每条指令区隔开，因此「→」本身也可以被省略。
而在《智能 | #5 一进制图灵机》中，我们规定读写头总是从最左端开始读取纸带上的输入数据，从左往右移动，最后在输出数据最右端停止。
因此「L 停」不会发生，所以「R 停」可以被简化为「停」。
这样简化之后，这台图灵机可以被改写为：
0 0 R
1 1 R
0 0 R
2 1 R
3 0 L
2 1 R
0 1 停
4 0 L
5 1 L
4 1 L
6 0 R
2 1 R
0 0 R
7 1 R
3 1 R
7 0 R
然后将十进制的状态数 0 , 1 , 2 , 3 …改写为二进制形式 0 , 1 , 10 , 11 …得到：
0 0 R
1 1 R
0 0 R
10 1 R
11 0 L
10 1 R
0 1 停
100 0 L
101 1 L
100 1 L
110 0 R
10 1 R
0 0 R
111 1 R
11 1 R
111 0 R
因为「 L / R / 停」的左边必定有一个「0」或「1」。
又因为在二进制表示中，数值「0」和「1」可以被合并进二进制状态 0 , 1 , 10 , 11 , 100 …的末尾而不影响识别。
其中「0 0」可以被直接省略，「0 1」则可以被简化为「1」，这样处理不会改变作用。
因此用来区分状态和数值的颜色也可以去掉。
所以我们可以将上述简化为：
R
11 R
R
101 R
110 L
101 R
1 停
1000 L
1011 L
1001 L
1100 R
101 R
R
1111 R
111 R
1110 R
而「 L / R / 停」足以将指令隔开，所以上面的换行可以去掉，将数据连接一起：
R11RR101R110L101R1停1000L1011L1001L1100R101RR1111R111R1110R
然后我们使用以下扩展二进制形式规则来转换指令：
二进制 0 → 0
二进制 1 → 10
R → 110
L → 1110
停 → 11110
转换之后的纸带数据为：
11010101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100110
对于这个数我们还可以进一步进行优化。
因为我们规定了读写头总是从最左端开始读取纸带上的输入数据，因此第一个指令永远是 R（00→00R），所以纸带开头的「110」可以被省去。
而纸带的最末端一定是「 L / R / 停」，这三个的结尾都是「110」，因此纸带的结尾一定为「110」，所以纸带最末端的「110」也可以被省略。
也就是我们可以省略掉纸带首尾的两个「110」，简化后纸带如下：
10101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100
以上这条纸带就是我们编码之后的「扩展二进制+1图灵机」。
2. 第N号图灵机
我们已经得到「扩展二进制+1图灵机」的纸带如下：
10101101101001011010100111010010110101111010000111010010101110100010111010100011010010110110101010101101010101101010100
可以将其改写成为十进制数，那么它就是：
450813704461563958982113775643437908
约为 4.5×1035，这真是一个非常大的数。
我们可以称「扩展二进制+1图灵机」为第 450813704461563958982113775643437908 号图灵机。
也可以用同样的方式把「一进制+1图灵机」编码成如下纸带：
101011010111101010
它的十进制形式为：
177642
即「一进制+1图灵机」为第 177642 号图灵机。
同样的「扩展二进制×2图灵机」为第 10389728107 号图灵机。
而「一进制×2图灵机」为第 1492923420919872026917547669 号图灵机。
即我们可以把任意图灵机都编码成特定的纸带，成为第N号图灵机。
3. 通往通用之路
至此我们终于完成了敲开「通用图灵机」大门的所有前置工作。
我们可以将任意的图灵机都编码成一条纸带，成为第N号图灵机，从而被另外一台图灵机读取。
这将是现代通用计算机的起源，整个世界都受益于图灵的深刻洞见。
（本章节完，敬请期待下一节）
By HW君 @ 2025-01-06