581
0摘要：在所有计算机和AI诞生之前，一位24岁的天才，仅用一篇论文，就定义了它们的过去、现在和未来。本期《白话大模型》，我们将深入阿兰·图灵的传奇：为了解决数学领域的终极难题，他如何构想出了所有现代计算机的理论原型——“图灵机”？我们将用一个连高中生都能看懂的思想实验，带你一步步解开著名的判定问题，亲眼见证图灵是如何为计算划定边界。
一、计算机科学与人工智能之父
上一期，我们见证了AI思想史上的第一次伟大飞跃：亚里士多德画出了思想的蓝图，布尔则为它装上了计算的引擎。这个让“用机器来模拟思维”第一次有了现实的根基。
那今天呢，我们将走进一位重量级的AI奠基人—— 阿兰·图灵。可以说，图灵为计算机科学奠定了理论的基础，也为人工智能开启了最初的大门。没有图灵，我们通往智能时代的探索，肯定会在黑暗中徘徊更久。
说起图灵，大家肯定都想到了图灵机、图灵测试。但是，图灵对一道世界级的数学难题——“判定问题”（Entscheidungsproblem）的证明，知道的人就不多了。像哥德巴赫猜想、费马猜想、黎曼猜想这些数学难题，它们的推演远远超出了普通人的认知。但在所有的世界级数学难题当中，“判定问题”可能是唯一的一个，虽然曾经难住了很多大数学家，但是图灵对它的证明过程，即使是中学生都完全看得懂。今天这一期的重点之一，就是我们会一起来证明一下这道世界级的数学难题。
好，话不多说，让我们请出今天的主角——阿兰·图灵。
二、终极问题与图灵机的诞生
阿兰·图灵是一位特立独行的英国数学家、逻辑学家，也是我们公认的现代计算机科学与人工智能之父。他的一生，是天才智慧与时代悲剧的交响。图灵从小就内向独立，甚至有些孤僻，但这让他更早地沉浸在自己的精神世界里。他对科学，尤其是机械和密码学，有着近乎痴迷的兴趣。
在剑桥大学，年仅24岁的图灵对“判定问题”产生了兴趣。这是伟大的德国大数学家大卫·希尔伯特在1928年提出的一个著名猜想。通俗地解释是：对于任何一个形式化的数学命题，我们能否找到一个确定的、机械化的程序或者算法，它能够在有限的步骤里，来判定这个命题是真还是假？
“判定问题”，我觉得更准确的应该叫“判定猜想”。如果这个猜想成立的话，那么在理论上就存在一个“终极判定机”，能够对任何数学猜想是否成立做出判断，哥德巴赫猜想、四色地图猜想、费马猜想、黎曼猜想都不在话下。是不是特别吸引人？
但是，“判定问题”本身是否成立，还没人知道。所以这个问题一经提出，就吸引了全世界数学家的兴趣，可以说是当时数学领域的圣杯。但是，包括希尔伯特本人在内的众多顶尖数学家都解决不了，对这个难题都束手无策。直到1936年，年仅24岁的图灵完成了一个精巧的证明。
但其实，当时图灵的目的不是要解决这个“判定问题”，他是为了方便他对机械化过程和计算本质进行探讨，构建了一个后世称之为“图灵机”的抽象计算设备。在这个过程当中，图灵“顺便”完成了对“判定问题”的证明。真是彪悍的人生不需要解释啊！
我们还是先来看一下图灵机。这是图灵构想出的一台极简的抽象机器，它并非是一台具体的物理机器，而是一个纯粹的数学模型，由4个简单的部分组成：
- 一条无限长的纸带：纸带被划分成一个一个方格，每个方格可以记录符号（0、1或者空白）。
- 一个读写头：可以在纸带上左右移动，读取或者写入方格上的符号。
- 一个状态控制器：记录机器当时所处的状态。
- 一套指令表：根据当前状态和读写头所读到的符号，决定下一步的操作——是写入符号、是移动读写头还是改变状态。
那这个看似简陋的模型，就是我们今天所有的电脑、手机的理论老祖宗。图灵也证明了，任何“可计算的”问题——也就是任何可以用明确的、有限步骤描述的计算过程——原则上都可以由一台图灵机来完成计算。
这可以说是一个开天辟地的时刻。图灵首次为“可计算性”提供了一个严格的、形式化的界定，把“计算”这个概念从具体的物理装置当中解放了出来。计算的本质不一定需要算盘，不一定需要纸笔，也不需要齿轮，也不是电路，而是一种可以脱离任何物理实体存在的、抽象的符号操作过程。
三、唯一一道中学生都能看懂证明的世界级数学难题
好，在定义了什么是“计算”之后，图灵接下来用一个名为“停机问题”的反证法，完成了对“判定问题”的证伪过程。
希尔伯特想知道的是，是否在理论上存在一个算法可以对任何数学猜想的真伪做出判断。那这个问题，难住了很多的大数学家，我想我们看到这个问题其实也都会觉得无处下手。图灵用了一个非常聪明的反证法，他假定“判定问题”这个猜想是成立的，那么我们也一定能够解决另外一个“停机问题”。
“停机问题”是图灵构建的一个难题。它说的是：如果“判定问题”为真，那么我们一定能够写出一个强大的万能函数，它叫 Halt。这个Halt函数接受两个输入项：一个是程序P，另外一个是输入参数x。Halt函数的功能就是，对于任何P跟x，只要你把它输入到Halt这个程序当中，Halt都能准确地告诉你 P(x)——也就是把x作为输入项输入给程序P之后，P是会陷入无限循环，还是最终会停止运行（无论是正常的停止还是报错）。它的一个特例就是，如果我们把P本身作为一个参数x传给P之后，那Halt(P, P)就会返回P(P)是否会停机。
接下来，图灵构建了一个“捣蛋程序”，名字叫做Paradox（悖论）。这个Paradox程序接受另外一个程序P作为输入，它的计算逻辑非常简单，分成三步：
- 函数
Paradox(P)直接调用Halt(P, P)，看它运行结果怎么样。 - 我们知道，
Halt(P, P)返回的是P(P)是否会停机。 - 得到这个结果之后，函数
Paradox总是对这个结果进行取反，作为最终的计算结果。
对有一点编程基础的同学来说，可能看程序会更加简单，这里是一个非常简单的Python示例程序。
从这里我们可以清楚看到逻辑，就是Paradox(P)直接去调用Halt(P, P)，得到结果之后直接取反，所以它的结果始终跟Halt(P, P)的结果是相反的。这个就是这个“捣蛋程序”的运行逻辑。
有了这些之后，最后图灵提出了终极的一个悖论问题。他问的是：如果把Paradox这个程序作为输入项，传给Paradox自己，它的计算结果会是什么？
我们知道了Paradox的计算逻辑是分三步。首先，根据它的定义，它会直接去调用Halt(Paradox, Paradox)。调用这个结果，其实也就获得Paradox(Paradox)的计算结果，无非是“无限循环”，或者“停止运行”。得了这个结果之后，第三步，根据Paradox这个程序本身的定义，它会对第二步当中的结果进行取反，然后作为Paradox(Paradox)的计算结果返回给用户。
好，到了这一步，你是不是觉得哪里不对？没错，在这里面，第三步的Paradox(Paradox)它的结果总是与第二步的计算结果——也就是Paradox(Paradox)本身——是相反的啊！如果需要的话，你可以对这段视频做个暂停看一下。这个结果是无论如何不可能的。
这就说明，我们最初的那个假设——就是“判定猜想”成立的这个假设——是错误的。所以通过这种方法，一个非常聪明的反证法，图灵就完成了对大数学家提出的“判定问题”的证明。
图灵的这个证明是不是特别精巧？是不是咱们普通人也都能够完全理解这个计算过程？当然了，这个短视频可能不是最好的讨论这道题的方式，所以我建议呢，你将来可以直接购买《白话大模型》这本书。
（硬广之后，我们继续）
图灵对“判定问题”的证伪，就像是投向平静湖面的一块巨石。我们第一次从数学上证明了“计算”它是有极限的，一定存在一些逻辑上清晰、但是任何算法都无法解决的问题。图灵在90年前就证明了，任何基于计算的智能，包括我们今天说的AI在内，它的能力都不是无限的，而是有着一定的能力边界。这就为所有关于“超级智能”的讨论，提供了一个冷静的、科学的边界。
图灵的传奇需要2期节目来讲述，今天的这一期就到这里。下一期我们将继续讲述阿兰·图灵传奇的下半场：从战争英雄，到世纪之问，再到时代悲剧。
请关注《白话大模型》，我们下周见。
