从忙碌海狸到现代CPU：一个 1936 年的抽象如何变成你手里的硅片

发布于 2026年5月12日作者 Remy

跟图灵相关的名故事有两个。一个是 1936 年那篇定义”可计算性”的论文。另一个被讲得少得多：那台抽象机器是怎么变成你笔记本里那块温热的方形硅片的。两者之间还有一段精妙的弯路——忙碌海狸函数，它让”不可计算性”从抽象论证变成你能数得出的整数。

本文沿着完整的弧线走一遍：从可计算性理论里最”不实用”的对象出发，一路走到键盘下面正在运转的、最实用的东西。

第一部分 —— 忙碌海狸：可以触摸的不可计算性

它从哪里来

1962 年，匈牙利数学家 Tibor Radó（拉多·蒂博尔） 在俄亥俄州立大学发表了 “On non-computable functions”。他面对的是一个教学难题：在他之前，所有不可判定性结果——停机问题、Rice 定理——都是用对角化论证给出的。学生跟得上推导，但摸不到。他想造一个具体、有限、直观却仍然不可计算的函数。

他的招数几乎带着玩心：考虑所有具有 n 个状态、使用 2 个纸带符号（0 和 1）、且在空白纸带上最终会停机的图灵机。这样的机器数目有限（在状态重命名意义下），所以下面两个量定义得很好：

Σ(n) —— 这些机器停机时纸带上 1 的最大数量；
S(n) —— 这些机器在停机前最多执行的步数。

想象一只小海狸在纸带上跑来跑去，“忙碌地”在停下来之前打尽量多的洞——名字就这么来的。

为什么它不可计算

反证：假设 Σ 是一个可计算的全函数。那么给定任意 n 状态的图灵机 M，我可以先算出 Σ(n)，再把 M 模拟 Σ(n) + 1 步——如果还没停，那就永远不会停。这就解决了停机问题。但停机问题不可判定，所以 Σ 必然超出每一个可计算函数的增长速度。

事实上 Σ 长得快到超过你能写出来的任何程序所定义的函数。它是”良定义但不可计算”的教科书案例。

我们目前知道的值

把小数值钉死下来异常困难——每往后一个 n，搜索空间就翻好几个数量级：

n	Σ(n)	确认年份
1	1	1962
2	4	1962
3	6	1965
4	13	1983
5	4098	2024（bbchallenge 项目用 Coq 形式化证明）
6	≥ 10↑↑15	未解

从 Σ(5) 到 Σ(6) 不是缓步上升，而是直接跌进 Knuth 上箭头记号——Σ(6) 据猜测会比我们这个宇宙里任何能给出物理意义的数都大。

Radó 教给我们的事

你不需要造任何古怪的对象才能逃出可计算性的边界。一个有限状态机加一条纸带——图灵当年定义的那个东西本身——就已经藏着没有任何算法能钉死的函数。 计算的边界不在无穷远处，它在 n = 5 就已经露面。

记住这一点：图灵机既是最简单的非平凡计算机，又是承载这个领域最深邃的不可能性结果的容器。下面我们来问：这个对象，到底是怎么变成你的 CPU 的？

第二部分 —— 一个常见的误问：现代芯片”几状态”？

知道忙碌海狸之后，一个自然的问题是：既然图灵机可以用状态数衡量，那一颗 M3 或者 Ryzen 大概几状态？ 听起来像是有答案的。其实没有——而且不能回答的原因本身就很有教益。

误区一：状态是二维的

忙碌海狸固定符号数 = 2，让 n 变化。但图灵机本身有状态数 n 和符号数 k 两个维度。存在”3 符号忙碌海狸""4 符号忙碌海狸”等等，它们各有各的表格。(n, k) 组合之间的换算并不平凡，“状态数”单独并不是衡量复杂度的通用尺。

误区二：CPU 不是图灵机

真实的 CPU 内存有限。若全部寄存器、缓存、内存加起来有 B 比特状态，则整机至多有 2^B 种配置。它本质上是一台巨大的有限状态机——或者，若把磁盘视为有界存储，叫线性有界自动机（LBA）——而不是图灵机。缺的就是那条无限纸带。

工程上我们假装现代计算机是图灵完备的，因为那个上界远远超出实际使用，假装没有代价。但理论上：你的笔记本不是图灵机。

误区三：状态比特 ≠ 控制器状态

就算接受”有限状态机”这个框架，忙碌海狸里的”状态”对应的是机器的控制单元——一个微小的 switch-case，决定下一步动作。一颗芯片那 2^B 的配置空间，绝大部分是落在纸带那一侧（寄存器和内存）的，而不是控制器那一侧。把它们混为一谈，相当于通过”墨水所有可能的排列”来衡量一本书的复杂度。

那什么才是好问题？

如果你确实想要一个数字，先选好你关心的维度：

控制器复杂度？ → 现代 x86 的微码 ROM 大约 10⁴–10⁶ 条微指令；这是一个有意义的”控制状态数”。
晶体管数？ → 旗舰芯片约 10¹¹ 量级。
模拟开销？ → 用图灵机模拟 CPU 跑一秒大约要多少步？约 10¹⁰–10¹² 步，取决于负载。这是理论上最有意义的版本。

每个答案衡量的是一个真实的东西。“我的 CPU 几状态？“听起来很利落，但拆开就散架。从理论到硬件的映射是结构性的，不是数量性的。

第三部分 —— 图灵机的思想，究竟是怎么活在 CPU 里的

核心问题来了。图灵机有四个原语，每一个都在现代硬件里对应一个清楚的实物，同时也有一个清楚的偏离——你需要把两者都看清。

四要素对照表

图灵机	现代计算机
无限纸带	内存 + 磁盘 + 网络存储
读写头位置	内存地址（PC、栈指针、MMU 映射）
有限状态控制器	CPU 控制单元 + 微码 ROM
转移函数 δ	指令集架构（ISA）+ 译码器

这只是骨架。真正有意思的地方，是工程实现对抽象的偏离。

真正的概念跃迁：通用图灵机

图灵 1936 年的论文有两个大想法，但出名的其实是第二个：通用图灵机（UTM）。UTM 是这样一台图灵机——它把另一台图灵机的描述和那台机器的输入都写在自己的纸带上，然后模拟它运行。

这是”机器”变成”数据”的一刻。一段计算的描述，本身就是一串符号，与它要处理的数据在种类上毫无区别。这是存储程序计算机的概念种子。

冯·诺依曼 1945 年的 EDVAC 报告初稿 把这个想法落到工程上：程序和数据共享同一片内存。当年这是大胆的，那时 ENIAC 这类机器还要靠重新接线来”编程”。这一个设计选择，是现代计算机能成为通用设备的根本原因。你用过的每一颗 CPU，都是一台经过精心伪装的 UTM。

纸带 —— 把”无限”用工程办法漂亮地伪造出来

图灵机的纸带是无限的，真实计算机的内存不是。工程解法叫存储层级：

寄存器（x86-64 约 32 × 64 位）—— 亚纳秒
L1 缓存（~32 KB）—— ~1 ns
L2 缓存（~1 MB）—— ~3 ns
L3 缓存（~30 MB）—— ~10 ns
主存 DRAM（8–128 GB）—— ~100 ns
NVMe SSD（1–8 TB）—— ~100 µs
网络/云存储 —— 毫秒到秒，实际无界

每一层大约比上一层大 10 倍、慢 10 倍。“无限纸带”的幻觉之所以成立，是因为有用的程序大多有局部性——其工作集会落到层级的高层里，而更下层的后备存储按需调入。

读写头 —— 随机访问，而不是逐格滑动

图灵机的读写头每次只能移一格，到第 N 格要走 N 步。CPU 把一个地址放到地址总线上，存储子系统大约用常数时间就把那个字节给你。

这是速度上的优化，不是能力上的优化。 一台只能逐格移动的图灵机也可以模拟随机访问，只是慢得多。两者计算能力等价，差的是程序员的友好度。我们随口说的”指针”，其实就是”读写头应当去到的位置”的二进制编码。

状态 —— 拆成宏观和微观两层

图灵机的”状态”就是个标签，像 q_7。CPU 实际上有两层状态：

宏观状态 —— 程序计数器（PC）和寄存器内容。程序员眼中的那一套。这才是”读写头的逻辑位置 + 控制器的当前规则”。
微观状态 —— 流水线阶段、分支预测器表项、缓存行的 MESI 状态、重排序缓冲区、推测执行前沿。这些在抽象图灵机里根本不存在。它们是为了从每秒钟里压出更多有用工作而引入的工程机制。

关键的一点：微观状态对正确程序是不可见的。整个”as-if serial”语义就是说，不管 CPU 内部如何狂野地推测和重排，你观察到的结果就好像它是老老实实一条一条按顺序执行的。微观状态是优化，不是语义。

（Spectre 和 Meltdown 漏洞，正是这种”不可见性”被打破的时刻——微观状态泄漏到了可观察的侧信道里。）

转移函数 δ —— 指令周期

图灵机的 δ 是说：给定当前状态和当前符号，写一个符号、移动读写头、切换状态。CPU 做的是同一件事，只是粒度粗得多：

取指 (Fetch) —— 从 PC 指向的内存读出指令；
译码 (Decode) —— 把这串比特翻译成控制信号；
执行 (Execute) —— 跑 ALU / 加载 / 存储 / 分支；
写回 (Writeback) —— 更新寄存器，可能更新 PC。

每一条 x86 或 ARM 指令本质上是若干个图灵机式 δ 的宏。一条 x86 MUL 不会塞进一个 δ——它会被展开成微码 ROM 里的一段微程序，由许多更简单的 δ 组成。指令集是 API，微码是实现。

这就是为什么我们可以严肃地说 CPU”就是”一台 UTM：体系结构状态机（PC + 寄存器）扮演了通用控制器的角色，内存里的程序则扮演了被模拟机器的转移表。

第四部分 —— 图灵机没覆盖的部分

一张诚实的地图要标出自己的盲区。真实计算机里有几个特性，在原始图灵机里没有对应物，要知道它们各自换来了什么。

并行

现代芯片有多核，GPU 有上千个核。多带图灵机（多条纸带、多个读写头）在计算能力上已经被证明与单带等价——n 带能算的，单带也能算，最多多项式级慢一点。所以并行不增加可计算性，只换速度。重要的是：有的问题用多核能拿到接近线性的加速，有的完全不能——理论早就把这个区别预言出来了。

流水线和乱序执行

这些是对转移函数的调度技巧——当依赖图允许时，并发地推进多个 δ 步。它们位于抽象之下，对程序员而言语义不变。

中断和 I/O

原始图灵机没有”外部世界”的概念。它是个闭环系统，跑到停机为止。真实 CPU 会接收中断——异步的外部事件把执行流强行拽进处理函数。这是对模型的真正扩展，也是操作系统存在的理由。没有中断，CPU 只能一次跑一个程序到完成；有了中断，它才能复用、响应键盘、处理网络包——简而言之，才能有用。

虚拟内存

MMU 在物理纸带上实现了一条虚拟纸带。每个进程看到自己私有的地址空间（自己那条”纸带”），而物理内存是共享的。这是操作系统在更高一层重演 UTM 的把戏：就像 UTM 模拟别的机器，带虚拟内存的内核为每个进程模拟一台单独的计算机。

缓存与预取

它们是对读写头未来位置的预测。图灵机不预测，它只是按 δ 走。CPU 会猜程序接下来要去哪里，提前把数据/指令加载进缓存，赌的是局部性原理会兑现。它经常兑现——这就是为什么”缓存友好的代码”是个真实的、可测的关注点，而抽象模型里根本没有这个概念。

第五部分 —— 一个好用的心智模型

如果只能记住一件事，请记住下面这张图：

你的 CPU 是一台高度优化的通用图灵机。

内存里的程序，是另一台图灵机的描述；

CPU 硬件，是运行这份描述的通用模拟器；

操作系统，是跑在 CPU 这台 UTM 之上的另一台 UTM——每个进程对应一台被它模拟的图灵机；

每一个容器、每一台虚拟机，又是 UTM 套 UTM 多了一层。

每次你启动一个软件，你都在告诉一摞嵌套的通用机器：“请帮我模拟另外这台机器。” 字面意思上就是这样——一路套娃到硅片为止。这种抽象能层层嵌套，是因为图灵的原始洞察——机器可以被编码为数据——天然支持组合。

写在最后

图灵机有时被当作”纯理论模型”打发掉。它不是。它是迄今为止所有通用计算机的组织原则。 纸带是你的内存；读写头是你的地址总线；状态是你的微码；转移是你的 ISA；而通用性——一台机器能读取另一台机器的描述并扮演它——正是你能装软件、卸软件、装新软件这件事得以可能的根本原因。

1936 年那篇论文定义了体系结构。1945 年的 EDVAC 报告给出了它的工程形态。之后这九十年都是在把它做得更快、更小、更难被打破，而没有改变下面那个想法。

而每过一阵子，当你想被提醒”这套大厦里其实嵌着硬性的极限”的时候——某条无限纸带上，还是有那么一只小海狸在跑，让不可能性变得可见。