两种回答——图灵机与λ演算

第一章我们说清了“编程是什么”。这一章再往深挖一层：电脑到底在干什么？这个问题，1930 年代有两个数学家给了两个绝妙的回答——你今天写的每一行代码，都是这两个回答的后代。

这一章是选读。它不讲任何 Racket 语法，也不教你怎么写程序。它只做一件事：带你看清“计算”这件事的本质——剥掉所有具体的语言、具体的机器，剩下最纯粹的内核是什么。

为什么值得读？因为你后面学的每一个概念——函数、递归、变量、循环——都不是某个人拍脑袋发明的，它们都长在一棵有九十年树龄的根上。看清这棵根，你就能理解为什么编程语言是这个样子、为什么有些设计是对的、有些是历史包袱。读不懂也没关系，这一章不影响你继续往下学，等你学到卷三亲手实现 λ 演算时，自然会回来重读。

一个朴素的问题，难倒了整个数学界

故事要从 1900 年说起。那一年，伟大的数学家希尔伯特提出了一个雄心勃勃的问题：数学能不能做到完全机械化？也就是说，能不能找到一套明确的、机械的步骤，任何数学问题丢进去，它都能告诉你“对”还是“错”，不会有歧义、不需要灵感，只要一步步算下去。

这个梦想后来叫“希尔伯特计划”。如果它成立，数学就变成了一个纯粹的计算问题——任何真理都能被机器算出来。

1931 年，哥德尔用不完备性定理给了它毁灭性一击：任何足够强的形式系统，都必然包含它自己无法证明的真命题。也就是说，数学不可能被完全机械化，总有一些真理是机器够不着的。

但这个打击反而逼出了一个更根本的问题：到底什么是“能被机械地算出来”？什么算“可计算”，什么算“不可计算”？要回答这个问题，你得先给“计算”一个精确的定义——不能靠直觉，得像定义几何公理那样严格。

就是这个要求，催生了两个绝妙的回答。

第一个回答：图灵机

1936 年，24 岁的英国数学家阿兰·图灵给出了他的回答。他的思路出奇地物理：把“人在算东西”这件事，拆到最简单的机械动作。

他设想了一台机器，叫图灵机。它只有三个部件：

• 一条无限长的纸带，上面分成一格一格，每格能写一个符号
• 一个读写头，能读出当前格的符号、能改写它、能左右移动一格
• 一套有限的规则，告诉读写头“读到什么符号、就在什么状态下、改写成什么、往哪移、进入什么状态”

就这三样，没有别的。没有屏幕、没有键盘、没有我们今天熟悉的任何东西。图灵论证说，人做的任何计算——无论是加法、乘法、解方程——都能分解成这样一台机器在纸带上一步步读写移动的动作。

这台机器简陋到显然能造出实物，却又强大到令人震惊。图灵证明了：存在一种“通用图灵机”，它能模拟任何其他图灵机。你只要把那台机器的规则写在纸带上，通用图灵机就能照着它运行——这正是“软件”概念的起源。你今天手机里的每一个 App，本质上都是纸带上的一串规则，跑在一台通用机器上。

图灵还证明了一件更惊人的事：有些问题是图灵机也算不出来的。最著名的就是“停机问题”——给你一台图灵机和它的输入，你没法用一套机械的方法判断它会不会停下来。计算是有边界的，这个边界是数学的铁律，不是技术不够。

第二个回答：λ 演算

几乎同一时间，普林斯顿的数学家阿隆佐·丘奇走了完全不同的另一条路。

图灵从“机器”出发，丘奇从“函数”出发。他设想了一套叫 λ 演算（lambda calculus）的形式系统，整个系统只有三种东西：

• 变量：x
• 函数抽象：λx. M，定义一个参数是 x、函数体是 M 的函数
• 函数应用：M N，把函数 M 作用到参数 N 上

没有数字、没有布尔、没有 if、没有循环——什么都没有，只有函数。但丘奇证明了，这套极简的系统足以表达一切可计算的东西。数字怎么办？用函数造。布尔怎么办？用函数造。条件判断怎么办？还是用函数造。

这听起来像变魔术，但它是真的。这本书的卷三第 20 章会带你亲手在 Racket 里把布尔、自然数、加减法全部用函数造出来——你能跑、能验证，不是空谈。那时候你会真正体会到 λ 演算的力量。

丘奇也从他的 λ 演算出发，独立证明了和图灵一样的结论：存在不可计算的问题。两条完全不同的路，抵达了同一个答案。

两条路汇成一条：Church-Turing 论题

1936 年，奇迹发生了。图灵证明了他的图灵机和丘奇的 λ 演算能力完全相同——凡是图灵机能算的，λ 演算都能算，反之亦然。两个从截然不同的角度出发的数学家，独立地给出了“计算”的定义，结果殊途同归。

这件事重要到有了一个名字：Church-Turing 论题。它的核心断言是：凡是能被机械地计算的，都能用图灵机算出来，也都能用 λ 演算表达出来。 这三种直觉——“可计算”、图灵可计算、λ 可计算——是同一件事。

[架构图：两种计算模型的对照与汇合。左侧图灵机：纸带+读写头+有限状态规则，箭头向下指向“计算机硬件 / C 语言 / 命令式编程”。右侧 λ 演算：变量+函数抽象+函数应用，箭头向下指向“Lisp / 函数式编程”。两条线在底部汇于一点标注“Church-Turing 论题：能力完全等价”]

为什么这个论题如此重要？因为它意味着“计算”有一个客观的、不依赖于具体实现的本质。不管你用的是纸带和读写头，还是函数和应用，不管未来发明什么新机器、新语言，能算的东西就是那些，算不了的就是算不了。九十年来的所有技术进步，没有一件事突破这个边界。

后来图灵去普林斯顿跟着丘奇读博士，两个人成了师徒。这段历史被一些人解读为“逻辑与语言”（丘奇）和“物理与机器”（图灵）的相遇——而今天的计算机科学，正是这两种视角共同的后代。

这两条路，怎样长成了今天的编程

你可能觉得这些离编程很远。其实近得不能再近。

图灵机那条路，长出了计算机硬件和机器语言。CPU、内存、指令集——这些是图灵机的纸带和读写头的物理化身。C 语言、操作系统、汇编语言，都根植在这条线上。今天的“命令式编程”——一步一步改变状态、用循环、用变量——本质上就是在写图灵机的规则。

λ 演算那条路，长出了函数式编程。1958 年，约翰·麦卡锡受丘奇启发创造了 Lisp——历史上第二古老的高级语言，把 λ 演算直接变成了能跑的程序。

Lisp 里的 lambda 关键字、函数作为一等公民、递归代替循环，全部来自 λ 演算。Scheme、Haskell、ML，甚至 Python 和 JavaScript 里的匿名函数，都是这条线的后代。

而 Racket，正是 Lisp 家族的直系后裔。所以当你学 Racket，你不是在学一门孤立的语言——你是在亲手触摸 λ 演算这条九十年前的根，看它怎样长成一门活生生的、能造产品的工程语言。

为什么要费这个劲

到这里你可能会问：我又不搞理论，知道这些有什么用？

用处是隐性的，但很实在。理解了“计算的本质只有两种等价的模型”，你就能看穿很多表面的复杂。

为什么有的语言重视函数，有的重视状态？因为它们分别继承了 λ 演算和图灵机两条血脉。为什么递归和循环能互相改写？因为它们是同一种计算的两个面。为什么说“函数是一等公民”很重要？因为它回到了 λ 演算最根本的设计——函数就是计算的基本单位。

这些洞察不会让你马上写出更快的代码，但会让你在学任何新语言、新框架时，多一层“它为什么这么设计”的理解。这恰恰是这本书想给你的——不只是会用，而是真正懂。

如果这一章你读得有点吃力，别担心。记住 λ 演算这个概念，等你学到卷三第 20 章，我们会把它从抽象的数学符号变成你能亲手运行的代码——到那时，一切会豁然开朗。

下一篇，我们回到地面：把 Racket 装进你的电脑，认出 DrRacket 的两扇窗，跑出第一行真正的代码。理论的路先走到这儿，接下来是动手的路。