文 | HW君
系列文章：
0. 在图灵机之前
在上一期《智能 | #3 可计算性，在图灵机之前》中，我们从如何获取数学真理出发，顺着「可计算性」理论的发展脉络，抵达了「图灵机」。
而这也是现代计算机和人工智能诞生的前夜。
提起现代计算机的起源，可以追溯到两个关键的人物，图灵和冯诺依曼。
图灵提出了现代通用计算机的理论模型「图灵机」。
冯诺依曼则在工程上实现了计算机。
人工智能是生长在现代计算机之上的，想要理解人工智能，图灵机是绕不开去的话题。
本系列接下来的几期，会试图带着大家一步一步理解图灵机的理论。
这并非三言两语可以做到，我们尝试将其分解为多个小部分，每期只讲清楚一两个重点概念，不至于吓退读者。
在这过程中会引用到一些数学公式，但并不复杂，仅仅需要一些耐心。
如果你觉得吃力，也可以适当跳过。
但如果你愿意耐心去弄懂它，那图灵机的理论会给你带来前所未有的顿悟。
1. 判定问题
数学在19世纪下半叶有了伟大的进展，其部分原因在于人们发展了数理逻辑证明的方法。
而罗素提出了「罗素悖论」，揭示了数学集合论的基础性矛盾，引发了数学危机。
应对数学危机，希尔伯特提出了希尔伯特计划。
他希望通过将数学理论转化为形式化的符号系统，并用明确的逻辑规则来推导数学命题，避免矛盾。
希尔伯特首先将逻辑限定在更加简洁可靠的「一阶逻辑」的范围内，用其作为数学理论的形式系统。
然后将数学问题重新描述为一阶逻辑的符号和规则。
一阶逻辑的优点在于有明确一致的语法和语义，具有清晰的推理规则和完备的模型理论。
高阶逻辑虽然表达能力远超一阶逻辑，但其复杂性不易于分析，在推理中常常需要借助人为的数学直觉。
一阶逻辑的解释规则非常清晰，所有公式都有确切的含义，具有有限的推理规则。
将数学问题转化为一阶逻辑公式之后，解答复杂的数学问题就变成了明确的一阶逻辑推理。
这样数学理论的推导就有了一个可靠的形式化基础。
为了更进一步排除推理过程中不可靠的人为因素，希尔伯特企图找到一种简单可靠的逻辑推理方法。
在这个背景下，他在1928年的《数理逻辑原理》中提出了判定问题（Decision problem）：
是否存在一种机械过程，能够在有限步骤内判断任意给定的一阶逻辑公式是否是可证明的？
因为已经将数学描述成了一阶逻辑公式，如果我们能够找到一种机械过程，去判定任意一阶逻辑公式的有效性。
那也就意味着我们找到了一个通用的算法，能够判断任意数学问题有没有解。
可以这样通俗易懂地理解「判定问题」：
存不存在这样的一台机器，我们任意输入一个数学命题，它都能告诉我们这个数学命题是有解还是无解。
2. 通用算法
希尔伯特的判定问题最终导向了「通用算法」的概念。
「算法」这一概念有着非常古老的历史了，例如可以追溯到公元前300年的求解最大公约数的欧几里得算法（辗转相除法）。
而「通用算法」的概念却是在1930年代，随着希尔伯特判定问题的提出才正式发展起来的。
数学家一直很擅长使用各种各样的算法来解决数学问题。
但希尔伯特想能找到一种更加确定的机械化的推理模式，一种更加可靠的通用算法，来充当数学逻辑中的「普遍裁判」，回答判定问题。
这种机械化的过程不依赖于某一数学家的直觉和经验，避免了人为因素或复杂步骤导致的数学矛盾。
1930年代很多人回答了判定问题，发展了可计算性理论。
在这其中图灵机的理论是最简洁、最优雅、最令人信服的。
3. 什么是计算
回答判定问题第一个困难的点在于，如何定义「机械过程」。
这一概念在当时还处于正常的数学概念之外。
希尔伯特提出了希望用更可靠的机械过程来解决数学问题的愿景，但什么是机械过程呢？
而这其实也就是可计算性理论面对的第一个问题：
什么是计算？
这是一个非常抽象的概念。
数学家在思考数学问题的时候、在进行计算的时候，到底发生了些什么？
我们要如何去描述这个计算的过程？
以及，如何从中找到最基本的、最可靠的步骤？
我们回想一下，一个数学家在进行思考时，都发生了什么。
如果是很简单的问题，或者数学家的记忆力超强，那么他只需要在脑海里思索和计算就行。
心算出结果，然后说出答案。
但人的记忆总是有限的，如果遇到比较复杂的问题，那么数学家通常需要一些额外的辅助。
那么最简单的辅助，也只需要是一张纸和一支笔。
在纸上写写画画，计算经过一些中间结果，最终得出答案。
这里的纸和笔，其实可以视为人的记忆的扩展。
哪怕其它更复杂的设备，例如算盘、手摇式计算器、打孔卡计算机等等……它们的作用其实也是如此。
借助机械的力量，这些计算器可以更快速得出结果，并储存更多的中间过程。
但如果不考虑效率，就基本的作用而言，使用计算器和让数学家用笔在纸上一行行计算是等价的。
当然我们也可以想象一个记忆力超强的天才数学家，他不需要纸和笔，只需要心算就可以计算出任何数学问题。
但这样他大脑里的计算过程对于我们来说就是一个黑盒了，无法分析。
所以我们就假设这是一个普通一点的数学家。
那么他在思索和计算数学问题时，需要的最基本的东西就只是：
一张纸、一支笔。
而这也是图灵给出的回答。
希尔伯特判定问题中「计算」的最基本步骤，只需要一张纸和一支笔。
4. 图灵机模型
图灵提出的图灵机模型非常简洁和优雅。
这一期我们先不展开其理论细节，只是简单地展示其全貌。
图灵机由以下几个基本部分组成：
（1）无限长的纸带
纸带上分为一格一格的单元，每一个格子可以储存一个符号标记；
（2）读写头
读写头可以读取纸带上当前格子的符号，也可以改写当前格子的符号；
（3）状态控制器
读写头上有一个状态控制器，其状态的数目是有限的；
（4）动作规则
读写头通过读取状态控制器当前的内部状态以及在纸带上格子的符号，来确定读写头下一步的动作：
a. 读写头写入或者擦除纸带上当前格子的标记（1表示有标记，0表示空白）；
b. 读写头在纸带上移动一格（L表示向左，R表示向右）；
c. 状态控制器转换为另一个状态；
这就是图灵机的理论模型。
这也就是图灵对于希尔伯特判定问题中「机械过程」的精确定义。
图灵宣称，这样的一台设备就能模拟人类所能进行的任何计算过程。
事实上也确实如此。
这个如此简洁的图灵机模型，就是当今的所有通用计算机的起源，也是所有人工智能的起源。
至于这到底是怎么实现的，我们后续会带大家一步一步地去理解它的原理。
（本章节完，敬请期待下一节）
By HW君 @ 2024-12-21