文 | HW君
系列文章：
0. 在图灵机之前
提起人工智能，人们经常会谈论「图灵测试」。
如果宣称某个AI程序非常厉害，常常会有类似「某某AI程序通过了图灵测试」的表述。
「图灵测试」是阿兰·图灵在1950年的论文《计算机与智能》中提出的一种测试人工智能的方法。
简单来说，如果人不能区分放在黑箱里的是人还是机器时，这台机器就应该被断定为有智能。
图灵在1936年发表的那篇极其重要的文章《论可计算的数》中提出了「图灵机」的概念，奠定了整个计算机科学与相关所有数学和哲学的基础。
当他在构思整个现代计算机的理论基础的时候，就已经开始思考人工智能的问题，因此提出了「图灵测试」。
不理解「图灵机」，便无法真正理解图灵为何会提出如此的一个「图灵测试」。
而这并非三言两语可以讲清，接下来的几期文章我们会一点一点清理思路。
这个过程并不容易，但却是必经之路。
这一期我们则往更早的历史溯源，探讨「可计算性」的问题，了解图灵提出这一系列议题的前置背景。
1. 罗素悖论与逻辑主义
什么是真理？
我们如何对世间的真假形成判断？
事实上我们在《逻辑 | 价值判断与事实判断》一文里有探讨过命题的分类。
自由意志的加入会使命题变得难以判断，所以这里不妨使问题简化一点，我们只讨论「数学真理」。
毕竟1+1就只会等于2，数学并不会因为你的情绪而妥协。
数学在19世纪下半叶有了伟大的进展，其部分原因在于人们发展了数理逻辑证明的方法。
数学家们对于获取数学真理也越来越有信心。
伯特兰·罗素的「逻辑主义」认为数学可以被完全归约为逻辑，成为逻辑学的一个分支。
即数学的所有定理都可以从逻辑的基本公理出发，通过逻辑推理得出。
通过逻辑推理，罗素试图为数学提供一个绝对可靠的理论基础，确保数学的逻辑一致性。
然而罗素自己在1901年提出的「罗素悖论」，却揭示了数学集合论的基础性矛盾。
考虑这么一个集合R：
R为一切不是自身元素的集合的集合。
那么R是否包含其自身？
无论R是否包含其自身，都会造成这个命题的矛盾。
罗素悖论有个通俗易懂的说法。
假设小镇上有一个理发师R：
「理发师R为所有不自己理发的人理发。」
那么这个理发师R为自己理发吗？
罗素悖论引发了数学危机，也直接否定了罗素自己基于逻辑主义试图为数学建立可靠基础的努力。
但这个危机也催生了「可计算性」理论的发展。
我们要如何才能获得不会出错的数学真理呢？
2. 希尔伯特计划与形式主义
1900年巴黎国际数学家大会上，数学家大卫·希尔伯特提出了著名的23个数学问题。
这些问题表达了他为数学建立公理化体系、解决数学基础问题的愿景。
此后为应对罗素悖论引发的数学危机，希尔伯特基于「形式主义」提出了「希尔伯特计划」。
希尔伯特试图将数学形式化，通过证明一致性来解决逻辑矛盾。
希尔伯特计划的思想是，将所有数学理论转化为一个严格的公理系统。
这个系统具有以下等方面的特点：
形式化、一致性、完备性、可判定性
（1）「形式化」是希望所有数学理论都转化为公理化的形式体系，数学表达仅依赖符号和逻辑规则，而非直觉或经验。
即所有数学定理都可以通过公理和形式化推理得出。
（2）「一致性」是指该数学公理体系没有矛盾，是自洽的。
即在这个形式化的数学公理体系内，不会同时导出某个命题和它的否定。
（3）「完备性」是指在该数学公理体系中，任何数学命题都可以被证明为真或为假。
即任何数学问题都可以通过形式化方式得到解决，不存在未知真假的命题。
（4）「可判定性」是指存在一种通用的算法，能够在有限步骤内判定任何数学命题的真假。
即找到一种通用算法，为数学问题提供机械化的解决工具。
形式主义的希尔伯特计划不依赖于逻辑的还原，而是着眼于用有限的手段证明数学系统的无矛盾性。
如果计划成功实现，那么数学理论就获得了可靠的基础，我们也就可以从这个形式化系统得到所有的数学真理。
3. 哥德尔不完备定理
1931年数学家库尔特·哥德尔提出了「哥德尔不完备定理」，宣告希尔伯特计划是不可能实现的。
哥德尔利用递归函数将「数学公式、证明步骤、逻辑操作」都编码成自然数，描述成一个形式化系统。
然后再构造一个自指命题G，这个命题G是一个无法被证明但为真的命题。
于是可以得到两个结论：
（1）第一不完备定理：在任何一个足够强大的形式化系统中，总会存在某些真命题，但这些命题既不能被证明为真，也不能被证明为假。
（2）第二不完备定理：在任何一个足够强大的形式化系统中，系统的一致性不能在系统内部证明。
这里的「足够强大」是指「能够表达和处理自然数的基本算术运算」，例如「蕴含皮亚诺公理」。
可以用一个通俗易懂的版本来描述哥德尔不完备定理：
（1）第一不完备定理：有一本百科全书，宣称记录下所有的知识，那么我们总能找到一些知识是这本书没有记录下来的。
（2）第二不完备定理：这本百科全书无法通过书中已有的知识，证明它的知识不会出现错误。
第一不完备定理关注系统的完备性：即使是非常强大的系统，也总有无法覆盖的真命题。
第二不完备定理关注系统的一致性：系统无法通过自身来证明其自身没有矛盾。
也就是希尔伯特计划想要实现的「完备性」和「一致性」，无法在同一形式化系统里被满足。
哥德尔不完备定理说明了，数学和逻辑虽然看似完美，但有一些天然的局限。
不可能存在一个「万能」的数学系统，它能回答所有问题，且保证自己永远正确。
希尔伯特计划无法实现，数学真理无法一劳永逸地获取。
4. 丘奇-图灵论题
罗素悖论引发了数学危机。
希尔伯特提出希尔伯特计划，企图寻找到确保数学一致性和完备性的方法。
而哥德尔用递归函数提出哥德尔不完备定理，宣告了该计划的失败。
哥德尔给出了希尔伯特第2问题的否定回答：
「完备性」和「一致性」无法在同一形式化系统里被满足。
阿隆佐·丘奇在1935年也提出了「λ演算」，否定了希尔伯特计划所追求的「可判定性」。
丘奇给出了希尔伯特第10问题（判定问题）的否定回答：
无法找到一种通用的算法，能够在有限步骤内判定任何数学命题的真假。
丘奇同时也提出了「丘奇论题」，证明了λ演算和哥德尔的递归函数是等价的。
1936年图灵完成了《论可计算的数》论文，图灵在剑桥的导师看到了丘奇的λ演算的文章，就把图灵推荐到丘奇的门下读博士。
丘奇马上意识到了图灵理论的重要性，1937年丘奇在撰写对《论可计算的数》文章的评论时，首次使用了「图灵机」一词。
后来丘奇也将原来的「丘奇论题」改为如今的「丘奇-图灵论题」。
「丘奇-图灵论题」表述的是：
所有功能足够强大的计算装置的计算能力都等价于图灵机。
即这些数学家和逻辑学家想出的各种计算装置，它们都可以互相模拟，是等价的。
例如：
哥德尔的递归函数、
丘奇的λ演算、
波斯特的POST系统、
乔姆斯基的0型文法、
冯诺依曼的细胞自动机
……
它们都可以等价于图灵的图灵机。
而在这几种等价、可互相模拟的计算模型中，图灵机是最简洁、最优雅、最令人信服的。
5. 可计算性与图灵机
从如何获取数学真理出发，顺着「可计算性」理论的发展脉络，我们终于抵达了「图灵机」。
而这也是现代计算机和人工智能诞生的前夜。
理解了图灵机，才能理解图灵为什么会提出如此的一个图灵测试。
因为图灵测试隐含着的一个逻辑就是，人类也是图灵机。
所以同为图灵机的计算机可以模拟人类的思考。
我们向来不会在文章里过多地讨论繁琐的理论细节，而是希望能够俯瞰知识的全景。
但唯独图灵机，值得一步一个脚印地去理解它细枝末节的原理。
这将会是接下来的几期里要着重讨论的内容。
可以说，理解图灵机是HW君在哲学上从幼稚走向成熟的标志之一，另一个则是理解信息论。
只有理解了图灵机，我们才能够真正意义上理解人工智能。
（本章节完，敬请期待下一节）
By HW君 @ 2024-12-08