第六部分 · 现代地基：连续、大小与计算

图灵机与可计算：从“证不出”到“算不出”

上一课，测度论给"大小"和概率上了锁。三块现代地基还差最后一块——计算。哥德尔刚刚证明了"真却证不出"，划清了证明的边界；而在 1936 年，一个 24 岁的年轻人图灵把同一个问题重问了一遍，只不过换成了机器的口吻：一台纯粹机械的装置，究竟能算出什么？为了回答它，他顺手发明了抽象的计算机——整个课程后半程，都要在这台机器上运行。

希尔伯特最后的问题：能不能"机械地"判定一切

希尔伯特的野心，我们在第 15 课见识过：他想给数学找一套完备、自洽、能自证清白的地基。哥德尔从"完备"和"自证"两处把这个梦炸开了。但希尔伯特的清单上，还剩一个更具体、更诱人的问题，叫判定问题（德文 Entscheidungsproblem，字面就是"判定的问题"）：

这个问题诱人，是因为它听起来像工程而不是哲学——仿佛只要够聪明，总能设计出这样一套流程。可图灵敏锐地意识到：要回答"有没有这样一套机械程序"，你首先得说清楚"机械程序"到底是什么。在他之前，"按规则一步步算"是每个人都会、却谁也没有精确定义的东西。你没法证明"某种机械程序不存在"，除非你先把"机械程序"这个概念本身钉死。图灵这一钉，钉出了一台机器。

图灵机：把“机械计算”钉死成四样东西

图灵做了一件极朴素的事：他去想象一个人用纸和笔死板地算题，然后把这个过程剥到不能再剥。剥完之后，"机械计算"只剩四样东西——

• 一条纸带：无限长，划成一格一格，每格写着一个来自有限字母表的符号（最简单就用 0 和 1，空白也算一个符号）。这就是机器的"内存"，要多长有多长。
• 一个读写头：每一刻只盯着一格。它能读这格的符号，写一个新符号覆盖它，然后向左或向右挪一格。仅此而已。
• 有限个"状态"：机器此刻的"心情/心里记着的一点点东西"，比如 A、B、C，外加一个特殊的停机状态。状态的个数是有限的——这是"机械"的关键：它记不住无限多的东西。
• 一张规则表：机器的全部"智能"。表的每一行形如"当前状态 + 读到的符号 → 写什么、往哪挪、进入哪个状态"。给定状态和读到的符号，下一步唯一确定。

就这些。没有屏幕，没有鼠标，没有 CPU。一台图灵机就是这样一个四元组：纸带、头、有限状态、规则表。它运行时做的事，简单到近乎笨拙：读当前格 → 查表 → 写、挪、换状态 → 重复，直到进入停机状态就停下。

丘奇–图灵论题：这就是“计算”的定义

图灵机把"机械可算"钉死了。可你也许会怀疑：会不会有某种更聪明的计算方式，图灵机做不到，别的模型却能做到？历史给出了一个惊人的巧合。几乎同时，逻辑学家丘奇（Alonzo Church）用一套完全不同的语言——λ-演算（把一切都看成"函数作用在函数上"）——也定义了一遍"可计算"。还有人用"递归函数"定义了第三遍。

结果三者被证明完全等价：凡图灵机能算的，λ-演算能算，递归函数也能算，反之亦然。此后人们又试了无数种计算模型（各种编程语言、各种理想机器），没有一个能超出图灵机的能力范围。于是有了这条论断：

停机问题：有些东西，算不出来

钉死了"计算"，图灵就能回答希尔伯特了——而回答的方式，正是这门课反复出现的那记杀招。先看一个具体又致命的问题，叫停机问题：

这需求太合理了——谁不想有个工具，提前告诉你代码会不会卡死？可图灵证明：这样的 H 根本不存在。证明用的，是康托尔（第 13 课）对付实数、罗素与哥德尔（第 14 课、第 15 课）对付集合与证明的同一把钥匙——对角线自指。

第一步，假设它存在。假设真有这么个万能检查器 H(P, 输入)，它总能正确答"停"或"不停"。既然程序可以把另一个程序当数据读进来（这一点下一节的通用机会兑现），我们就能拿 H 当零件，拼一个专门捣乱的新程序 D。

第二步，造一个反叛者 D。D 只接收一个程序 P（把 P 自己的代码也当作它的输入喂进去），行为故意拧着来：

D(P)：先问 H —— “P 喂给自己会不会停？”
　　若 H 说“会停” → D 就故意进入死循环（不停）；
　　若 H 说“不停” → D 就立刻停机。

（读作"D 拿到程序 P，先用检查器问'P 喂自己会不会停'，然后反着做：说会停我就不停，说不停我就停。"）注意 D 完全是用现成的 H 拼出来的，所以只要 H 存在，D 就是一个货真价实、能跑的程序。

第三步，把 D 喂给它自己。现在问一句要命的话：D(D) 会停，还是不停？——这就是对角线上那一格，让机器去评判"它自己"。两条路，都撞墙：

请把这条脉络看清楚，它是这门课思想史半程真正的主心骨：

顺带，希尔伯特的判定问题也就此有了答案：如果存在那台"数学判官"，就能用它去判定"某程序是否停机"这类命题——可停机问题不可判定，所以判定问题的答案是"不存在"。数学没有万能判官。

通用图灵机：一台机器，跑所有程序

如果本课只有坏消息，那就辜负图灵了。他最深远的贡献，恰恰是一个建设性的想法，而且它就藏在刚才那句"程序可以被当作数据读进来"里。

到目前为止，每台图灵机都专机专用：一张规则表只会干一件事（比如"给数加一"）。图灵却问：能不能造一台通用机器 U，它不为任何特定任务而造，而是——你把另一台机器 M 的规则表，当成符号写在 U 的纸带上（这叫 M 的"描述"），再在旁边写上 M 的输入，然后 U 就照着这份描述，一步步模拟出 M 的运行？

图灵证明：能。这台机器叫通用图灵机。它带来的观念转变，怎么强调都不过分：

下面这台微型图灵机，不模拟别人，而是老老实实亲自跑一个程序，让你亲眼看它一格一格地计算，然后准时停下来——一个"会停机"的活标本。

从“极限”到“机器”：转身造物

把哥德尔和图灵并排放，你会看到一对孪生兄弟。哥德尔说的是证明的极限——有真命题，永远证不出来（真却证不出）。图灵说的是计算的极限——有明确的问题，永远算不出来（问却算不出）。它们不是各说各话，而是同一件事的两张面孔：都用对角线自指，都得出"机械的确定性有一道逃不掉的边界"。哥德尔从"证"的一侧撞见这堵墙，图灵从"算"的一侧撞见同一堵墙。

可图灵这一侧，还带回了一份哥德尔那侧没有的正面大礼。看清"算不出什么"的同一套思考里，他造出了通用图灵机——那台能读程序、能模拟一切的机器。数学在这里完成了一次漂亮的转身：看清了极限，转过身，把机器本身造了出来。

常见误解

• "停机问题只是'很难判断'，用更强的电脑或更聪明的算法总能搞定。"不是难，是逻辑上不可能。图灵证明了：不存在任何程序，能对一切程序都正确判定是否停机——再快的超级计算机、再高明的 AI 也不行，因为那个"和判断反着来"的反叛者 D 永远能把它逼进矛盾。个别程序你当然能看出会不会停；不存在的是覆盖所有情况的通用判定程序。
• "图灵机是一台真实的老式机器（一堆齿轮和纸带）。"不是。它是一个抽象数学模型，为的是把"什么可被计算"定义清楚，从没打算真造出来。它反过来框定了所有真实计算机的能力上限：任何物理计算机——从最早的电子管到今天的芯片——能算的都不会超出图灵机，也同样躲不过停机问题。它不是某台机器，而是一切机器的数学蓝图。
• "哥德尔和图灵各说各的，一个讲逻辑，一个讲计算机。"不。它们是孪生兄弟，用的是同一个对角线自指：哥德尔造"我不可证"的命题限制证明，图灵造"和判断反着来"的程序限制计算。两者都是"让系统评判自己"逼出的同一堵墙，只是分别从"真/可证"和"停/不停"两侧撞上。
• "有了通用图灵机，理论上什么都能算出来。"不。"通用"只意味着它能模拟任何程序——凡是可计算的，它都能算。但它照样躲不过停机问题：你没法用通用机去判定任意程序会不会停，因为那样的判定程序根本不存在。能模拟一切可算的，不等于什么都可算。