0. 引子：希尔伯特的符号游戏

1928年，数学界领袖大卫·希尔伯特提出了一个雄心勃勃的问题：是否存在一个通用的机械步骤，能够判定任意数学命题的真假？这个问题被称为“判定问题”。

希尔伯特的设想是，把整个数学变成一套纯粹的符号游戏。每一个数学命题——比如“存在无限多个素数”——被编码为一串无意义的符号。每一个推理步骤——比如“如果A蕴含B，且A成立，则B成立”——被编码为一条符号改写规则：从 A → B, A 这两个符号串，机械地推导出 B。证明一个定理，就是从一组初始符号串出发，反复应用改写规则，直到目标符号串出现。如果这一切可以形式化，那么判定一个命题是否成立，就变成了一个纯粹的符号操作问题——一台机器，只需要看着符号的形状，按规则搬运它们，不需要知道这些符号“意味着”什么。

这个设想有一个意料之外的当代回响。今天的大语言模型——GPT、Claude——在做的事情，在结构上与此如出一辙：它们接收一串符号（token），预测下一个最可能出现的符号。它们同样不知道这些符号“意味着”什么，只是在统计意义上学会了符号之间的转移规律。希尔伯特梦想的是逻辑推导的机械化，而LLM实现的是统计模式的机械化。两者追求的精确性不同，但底层的操作对象是同一个：无意义的符号，以及符号之间的变换规则。

1936年，24岁的艾伦·图灵对这个设想给出了一个否定的回答：希尔伯特想要的通用判定算法，不存在。

为了严格证明这个否定性结论，图灵必须先回答一个更基本的问题：什么叫算法？ 他发明了一个数学模型，后来被称为图灵机。请注意这个先后顺序——图灵不是在设计计算机，他是在为“机械计算”这个直觉寻找精确的数学定义。

多年以后，人们造出了电子计算机，写出了各种程序。又过了几十年，“人工智能”这个词开始流行——AlphaGo下棋，ChatGPT写文章。媒体喜欢说它们“学会了思考”，好像这些程序已经脱离了程序的范畴。

但在追问AI的本质之前，有一个更基本的问题需要先回答：算法，到底是什么？

这个问题问的是算法的本质。本质往往藏在最简单的例子里。我们从加法开始。

1. 加法与函数：算法的数学原型

1.1 从加法说起

看一个最朴素的例子：加法。

小学生在算术本上演算列式加法——纸上写两行数字，个位对齐，从右往左逐位相加，进位，得出结果。比如计算 456 + 789，我们会在纸上这样列：

    4 5 6
  + 7 8 9
  --------
  1 2 4 5

给定两个数 456 和 789，得到 1245。这件事可以这样看：存在一个对应关系，它把一对数 (456, 789) 指向了另一个数 1245。同样的对应关系也作用于其他数对：(2, 4) 指向 6，(7, 1) 指向 8，以此类推。

在数学上，这种对应关系叫映射。说“加法是一个映射”，就是把每一对输入的数对应到它们的和这个输出上。

抽掉加法的具体内容，只留下结构：有两个集合，一个叫输入集合 X，一个叫输出集合 Y。映射就是从 X 中的一些元素出发，各自指向 Y 中的某个元素。记号写为 f: X ⇸ Y。这个带斜杠的箭头表示：不一定对 X 里的每个元素都有对应。映射只关心“谁对应谁”，不关心这个对应是怎么来的。

加法这个映射有一个特点：它的对应关系不是杂乱无章的。存在一套有限的、机械的规则——个位相加、进位、十位相加——告诉你从任意两个数出发，怎么一步步算出它们的和。

当一个映射的对应关系可以由一套有限的、机械的规则来描述时，数学家叫它函数。

区别就在这里。映射只要求对应关系存在，它可以完全无规律。函数要求背后有一套法则——你可以根据这套法则，对任何输入按步骤求出输出。

函数有两个基本要素。定义域：输入的取值范围。加法的定义域是所有自然数对。值域：输出的取值范围。加法的值域是自然数。对于定义域中的每一个输入，输出唯一确定——这样的函数叫全函数，记作 f: X → Y，不带斜杠的箭头。

1.2 黑箱之外

数学家把函数看作一个黑箱：输入进去，输出出来。外部行为描述清楚了。但黑箱里面有什么？

说到这里，有一个值得停留的细节。数学家对加法有一种执念。阿贝尔群上的运算叫加法，向量空间上的运算叫加法，椭圆曲线上那个画线求交点再对称的操作也叫加法。初学者翻开密码学教材，看到“点加法”三个字，脑子里浮现的是 3 + 5 = 8，然后一头雾水。

数学家会平静地告诉你：它满足加法的所有法则——结合律、交换律、有单位元——所以它就是加法。至于你心里想的是不是算术，那不是数学关心的事。

这不是命名上的偷懒。这是一种泛化。数学家从整数加法中抽出了最核心的结构——一种满足特定法则的二元运算——然后发现，这个结构在完全不同的对象上也成立。一旦你掌握了结构的本质，你就可以把它搬到任何满足条件的地方。椭圆曲线上的“加法”和你小学做的加法，在结构上是同一件事。至于实现细节——一个是十进制逐位相加，一个是几何作图——那是第二位的。

数学不关心内容，只关心结构。它把结构从具体中剥离出来，然后泛化到一切满足条件的对象上。

图灵对“计算”做的事，正是数学家对“加法”做的事。

既然如此，我们就来拆开黑箱。一个算法的内部结构，到底是什么样的？图灵的回答是：纸、笔、符号约定、心里记着的状态——以及一套操作规则。

好，现在我们有了函数这个黑箱。接下来，拆开它。

2. 拆开黑箱：图灵机

2.1 计算的前提

在动手计算之前，有三个前提已经悄悄就位了。

纸。 一块可以写上符号、阅读符号、擦掉重写的平面。它不需要无限大——草稿纸用完可以再拿一张——但理论上必须“够用”。图灵把它理想化为一条无限长的纸带，不是因为纸不要钱，而是因为“纸用完了怎么办”不是数学问题。

笔。 一支一次只能对准一个位置的笔。它可以读当前位置写了什么，擦掉当前内容写上新的符号，然后左右移动。笔尖就是读写头。人的笔尖不可能同时写两个字，图灵的读写头一次也只操作一个格子。

约定符号。 纸上能写什么，是事先约定好的。对于列式加法，约定符号至少包括 0 到 9 十个数字、加号 +、等号 =，以及表示“这里暂时为空”的空白符 ␣。这个约定的符号表，就是字母表。

列式加法是两行数字上下对齐，但纸带只有一行。我们把两个加数并排放在纸带上，用 + 分隔，= 标记答案区域的开始。个位对齐在最右侧。比如要计算 456 + 789，纸带初始内容为：

[4][5][6][+][7][8][9][=][␣][␣][␣][␣]

读写头开始时对准最右侧的数字（个位 6），状态为“准备开始，无进位”。（标准图灵机定义中读写头初始位置通常在输入串最左侧。这里让它对准个位，是为了符合列式加法的习惯。通过转移函数调整起始位置是可行的，不影响计算能力。）

2.2 进位存在哪里

现在来看列式加法的操作过程。操作者面前摆着纸带，读写头对准个位。接下来要做的是：读取当前位的数字，心里回忆“上一把有没有进位”——如果有，把进位也算上——算出本位的结果和新的进位，把结果写在 = 右侧对应的位置，读写头左移一位，重复。直到所有位都处理完。如果最后还有进位，在答案区域补一个 1。

这里有一个关键的细节。在这个操作过程中，“进位”不是写在纸带输入区域上的。它是操作者心里记着的——“上一把有进位”或“上一把没进位”。这个记忆只有两种可能，但它决定了本位操作的结果。

图灵把这种“心里的记忆”显式化为状态。状态集记作 Q。在加法图灵机里，Q 至少包含 q_nocarry（无进位模式）和 q_carry（有进位模式）两个状态。可能还有 q_start（开始）、q_end（结束）等辅助状态。

在实际的图灵机设计中，“读这一位的两个数字”可能需要多步：先读左侧加数的当前位，记住它；移动到右侧加数的对应位，读取它；再根据两个数字和进位状态决定操作。这里为了直观，我们用“逻辑上的一次操作”来描述。

根据当前状态和当前读到的符号，决定下一步做什么——写什么、往哪移、进入什么状态。这套规则就是转移函数，记作 δ。例如：

• 状态为 q_nocarry，读到数字 5 和 3：写 8，左移，保持 q_nocarry。
• 状态为 q_carry，读到数字 9 和 8：9 + 8 + 1 = 18，写 8，左移，保持 q_carry（因为又产生了新进位）。
• 状态为 q_nocarry，读到加号左侧为空（␣）、右侧为 7：写 7，左移，保持 q_nocarry。
• 所有位处理完毕，状态为 q_nocarry：进入 q_end，停机。

2.3 七元组

有了这些直觉准备，图灵机的形式定义就可以直接亮相了。一台图灵机 M 由七个组件定义：

M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

计算的一步是这样进行的：读写头读当前格子符号 a，状态寄存器提供当前状态 q。转移函数 δ(q, a) = (q', b, D) 据此决定三件事——状态变成 q'，当前格子写入 b，读写头向 D 方向（L 左或 R 右）移一格。

仅此而已。没有理解，没有直觉，只有符号的读取、改写和状态的切换。欧几里得算法中的“用余数替换原来的数”，列式加法中的“逐位相加并进位”——都是这套规则的具体实例。

2.4 图灵机就是函数：回扣列式加法

现在，把一台图灵机 M 看作一个部分函数：

f_M: Σ* ⇸ Σ*

纸带初始内容为输入字符串 x，状态为 q₀，读写头指向指定起始位置。然后开始一步步计算。

• 如果最终进入 q_accept 并停机，纸带上的内容就是 f_M(x)——输出。
• 如果进入 q_reject 或永远不停机，则 f_M(x) 无定义。

这个对应关系很精确。函数的输入等于纸带初始内容，函数的输出等于停机时纸带内容，函数的映射法则等于转移函数 δ 规定的符号变换规则。读写头的每一次移动和改写，就是映射法则的一步规约——输入串被一步步变换，直到不可再约的答案。

我们用 456 + 789 跑一遍完整的演算过程，看看这套规则怎么“动”起来。

初始配置

纸带: [4][5][6][+][7][8][9][=][␣][␣][␣][␣]
状态: q_start（准备开始，无进位）
读写头: 对准个位（6）

约定读写头从个位开始，逐位向左处理。每一步读两个数字——一个来自第一个加数，一个来自第二个加数——以及当前进位状态，算出本位结果和新的进位，将结果写到 = 右侧对应位置。

步骤1：处理个位

当前状态: q_nocarry（无进位）
读头对准: 第一个加数个位 6，第二个加数个位 9
计算: 6 + 9 + 0 = 15 → 本位结果 5，进位 1
动作: 在 = 右侧个位写 5，读写头左移一位，状态变为 q_carry

纸带: [4][5][6][+][7][8][9][=][5][␣][␣][␣]
                                ↑
状态: q_carry

步骤2：处理十位

当前状态: q_carry（有进位）
读头对准: 第一个加数十位 5，第二个加数十位 8
计算: 5 + 8 + 1 = 14 → 本位结果 4，进位 1
动作: 在 = 右侧十位写 4，读写头左移一位，状态保持 q_carry

纸带: [4][5][6][+][7][8][9][=][4][5][␣][␣]
                            ↑
状态: q_carry

步骤3：处理百位

当前状态: q_carry（有进位）
读头对准: 第一个加数百位 4，第二个加数百位 7
计算: 4 + 7 + 1 = 12 → 本位结果 2，进位 1
动作: 在 = 右侧百位写 2，读写头左移一位，状态保持 q_carry

纸带: [4][5][6][+][7][8][9][=][2][4][5][␣]
                        ↑
状态: q_carry

步骤4：处理最后的进位

当前状态: q_carry（有进位）
读头对准: 加号左侧无更多数字（空白符 ␣），右侧也无更多数字
计算: 0 + 0 + 1 = 1 → 本位结果 1，进位 0
动作: 在 = 右侧千位写 1，读写头左移一位，状态变为 q_nocarry

纸带: [4][5][6][+][7][8][9][=][1][2][4][5]
                    ↑
状态: q_nocarry

步骤5：确认结束

当前状态: q_nocarry
读写头: 左侧已无更多数字需要处理
动作: 进入 q_accept，停机

最终纸带: [4][5][6][+][7][8][9][=][1][2][4][5]

停机时，= 右侧的内容是 1245。提取出来，正是 456 + 789 的和。

整个过程里，读写头在纸带上左右移动，读取符号，改写符号，状态在“有进位”和“无进位”之间切换。每一步都严格由转移函数 δ 决定。纸带就是草稿纸，状态就是心算时的记忆，转移函数就是操作规则。 图灵把列式加法的所有要素抽象成了数学组件。

我们刚刚用图灵机做了加法。但这台图灵机并不是加法专用的。它的每一个组件都是可以替换的：Q 里可以塞进任意多种状态，Σ 和 Γ 里可以约定任意多个符号，δ 的规则表可以任意复杂。我们恰好把状态设计为“有进位/无进位”，把符号约定为0到9，把规则写成逐位相加——就像我们在小学算术本上做的那样。但同样的结构，完全可以换上另一套状态、另一套符号、另一套转移规则，去做乘法、做排序、做文本搜索。

这正是第1节结尾所说的“泛化”。数学家从加法中抽出了阿贝尔群的结构，然后把它搬到椭圆曲线上。图灵从列式加法中抽出了机械计算的结构——纸、笔、符号、状态、转移规则——然后告诉你：任何有限步骤的机械操作，只要每一步都只依赖当前看到的符号和心里记着的状态，都可以塞进这个七元组。 他抽出的不是加法，而是计算本身。

因此，丘奇-图灵论题（丘奇的工作将在下一节介绍）断言：一个部分函数是能行可计算的，当且仅当它是图灵机可计算的。这是一个论题，不是定理。它无法被严格证明，因为它涉及“能行可计算”这个非形式化的直觉。但八十多年来，所有试图形式化“计算”的尝试，都划出了同一个函数类。

列式加法是幸运的——它对所有输入都停机，它实现的是一个全函数。但不是所有算法都如此。设想一台图灵机，检查某个偶数是否满足哥德巴赫猜想（大于2的偶数可表示为两个素数之和）：找到反例就停机，否则永远搜索。这台图灵机定义的函数，在那些不满足猜想的输入上——如果存在的话——f_M(x) 没有定义。图灵机不保证对所有输入都停机。 正因为如此，图灵机所计算的，严格地说，是一个部分函数：f_M: Σ* ⇸ Σ*。在不停机的输入上，f_M(x) 无定义。

这个观察将我们引向一个更深的结论。图灵证明了停机问题是不可判定的——不存在一个通用算法能判断任意图灵机在任意输入上是否停机。图灵机既是“可计算”的定义，也是“不可计算”的判决书。他1936年的论文，初衷就是为“机械计算”下一个精确的定义，从而证明不可计算函数的存在。

3. 等价之核：λ演算与部分递归函数

图灵在普林斯顿的导师阿隆佐·丘奇，几乎同时从另一个完全不同的方向追问同一个问题。

丘奇的工具是λ演算。它的基本直觉是：计算就是函数的代入与归约。λ演算不涉及机器或纸带，它只规定符号如何被替换。一个λ项经过一系列代入和归约，最终可能达到一个不能再归约的形式——范式。达到范式，范式就是计算结果；如果永远在归约中无法达到范式，那么这个函数在这个输入上就没有定义。λ演算的“范式”和图灵机的“停机”，是同一概念在两种语言中的不同表述。

与此同时，哥德尔和克林尼在另一个方向上探索。他们提出一般递归函数，从几个极其简单的初始函数（常数函数、后继函数等）出发，只允许通过代入和递归来构造新函数。这样定义出来的函数类，就是部分递归函数。这个体系的直觉是：复杂的可计算函数，都可以从极简的原子出发，通过有限次机械组合构造出来。

图灵机、λ演算、部分递归函数——三个独立的形式体系，来自三种完全不同的直觉：物理机器、符号代换、函数构造。但它们被证明定义了完全相同的函数类。图灵本人证明了图灵机与λ演算的等价性。克林尼证明了递归函数与λ演算的等价性。

这件事的深刻之处在于：不管你从“物理机器”、“函数代数”还是“纯符号代换”出发，最终捕捉到的都是同一个“可计算”概念。这不是巧合，而是揭示了一个事实——可计算性是一种独立于具体模型而存在的数学实体。

从希尔伯特1928年提出判定问题，到图灵和丘奇在1930年代给出答案，再到今天——我们花了近百年把这个答案消化清楚。

算法，在数学本质上，是一个部分函数的机械化实现。图灵机、λ演算、部分递归函数——三个独立的数学体系，在同一条边界上汇合。这条边界划定了可计算性的疆域：边界之内，一切可计算的函数都可以用图灵机执行；边界之外，是数学上的不可能。“所有算法都是函数求值器”，这不是一个比喻，而是刻在这条边界上的数学事实。

理解计算是什么，或许是我们讨论AI之前，最应该先做的一件事。

（上篇完）

[招生]科锐逆向工程师培训(2026年7月3日实地，远程教学同时开班, 第56期)！