波仔

📄 一句话概括

图灵机不是一台机器，是一个思想实验：一条无限长的纸带 + 一个只会"读、写、挪一格"的读写头 + 一本规则表。就这么个简陋设定，图灵用它定义了"什么是可计算的"——既证明了一切有明确步骤的问题机器都能算（通用机器，软件的种子），也证明了有些问题任何机器都永远算不了（计算的边界）。

1. 为什么值得单开一篇番外

08 篇说图灵"领先机器十年"。领先在哪？别人在琢磨怎么造计算机时，他在琢磨一个更根本的问题：

1930 年代，数学家们在追问："计算"到底是什么？有没有办法事先判断一个问题能不能算出来？

图灵（24 岁）的回答方式很工程师：既然要定义"计算"，那就造一台最简陋、但能力拉满的假想机器——凡是它能算的，就叫"可计算"。这台假想机器就是图灵机。

2. 三件套：纸带、读写头、规则表

部件 是什么 能做的全部动作
纸带 一条无限长的格子带，每格放一个符号（0、1 或空白） ——（只是躺着被读写）
读写头 对准某一格的"笔尖" 读当前格、写/擦当前格、左移或右移一格（只能一格！）
规则表 一本有限的查表手册 按"当前状态 + 读到的符号"决定：写什么、往哪挪、变什么状态

每一步都是死板的三连：读格子 → 查规则表 → 写/挪/变状态。没有任何一步需要"灵光一现"。

📝 三个看似奇怪的设定，各有深意
  • 纸带无限长 → 保证不是"内存不够"卡住算法，只研究算法本身
  • 读写头一次只能挪一格 → 能力上够用了（多挪几步顶多慢点），设定越简，结论越硬
  • 规则表有限 → 机器的"程序"必须能被完整写下来——这是它能被"描述"的前提，后面有大用

3. 实战：用图灵机算 1101 + 1

规则表只需两条 + 一个停机状态：

状态 A 读到 1 → 写 0，左移（还在 A）
状态 A 读到 0 → 写 1，右移，进入状态 B
状态 B       → 停机

三步走完（对话里的演示器可以亲手点一遍）：

步 纸带 头在哪 发生了什么
0 1101 最右的 1 起点，状态 A
1 1100 左一格 读到 1 → 写 0、左移（退位，进位没完）
2 1110 回到原位 读到 0 → 写 1、进状态 B → 停机

没有加法器、没有电路、没有进位标志——一台只会查表的傻机器，算出了正确答案。而且图灵证明了：任何"有明确步骤的问题"，都能写成这样一本规则表。

4. 两个改变世界的推论

推论一：通用图灵机——"软件"的种子

图灵进一步问：能不能造一台万能图灵机？可以——只要把"别的图灵机的规则表"当成数据写在纸带上喂给它。它读入规则表，就扮演那台机器。

翻译成今天的语言：规则表 = 程序，纸带 = 内存，"读入规则表去执行" = 运行软件。

推论二：停机问题——机器也有"永远做不到"的事

图灵还证明了一个反面的结论：不存在一台万能判定机，能判断"任意一个程序在任意输入下会不会停下来"（停机问题）。

想写个插件自动检查"所有代码有没有死循环"？图灵 1936 年就证明：这活儿在原理上不可能——不是技术不够，是逻辑上无解。

这是人类第一次给"计算"划出边界：能算的，图灵机都能算；算不了的，再强的机器（再快的 CPU、再大的内存）也永远算不了。 这叫丘奇-图灵论题，是整个计算机科学的地基。

5. 图灵机 vs 你的电脑：一一对应

图灵机 真实计算机
纸带 内存（纸带 = 一条超长的一维内存）
读写头 CPU
规则表 程序
当前状态 + 头的位置 寄存器 + 程序计数器（06 篇的"书签"）
停机状态 程序退出

差别只剩工程细节：真机器把纸带换成随机访问的内存（快）、把一步三连流水线化（07 篇）、把规则表换成编译好的机器码。灵魂配置 1936 年就定型了。

6. 图灵其人：天才、战争与迟来的道歉

7. 常见误区

⚠️ 误区一：图灵机是一台真实的机器

从来没有造出来过，也不需要造——它是定义。作用相当于"用一把绝对直的尺子定义什么叫直"，用来回答"什么是可计算"。 [!warning] 误区二：图灵机太简陋，能力不如现代电脑 恰相反：可以证明，任何现代电脑能算的，图灵机都能算（顶多慢）。加再多的核、再大的内存，也不改变"能算什么"，只改变"算多快"。 [!warning] 误区三：停机问题是"还没解决的技术难题" 不是难题，是已被证明无解——逻辑上不存在那样的判定机。和"三等分角"一样，属于"永远做不成"而非"暂时做不到"。 [!warning] 误区四：通用图灵机就是"多功能的机器" 关键不在多功能，而在"把别的机器的规则表当数据读进来"——程序是数据。这是从"一台机器一个用途"到"一台机器无限用途"的那道门。 [!warning] 误区五：图灵机只能算 0 和 1 符号随便定，0/1、字母都行。选二进制只是因为最简，而且和真实电路（01 篇）最搭。

8. 可折叠自测题

❓ - Q1. 图灵机有哪三件套？每步的动作固定是什么？

纸带（无限长格子带）、读写头（读/写/挪一格）、规则表（查表手册）。每步固定三连：读格子 → 查规则表 → 写/挪/变状态。 [!question]- Q2. 通用图灵机是怎么"变成别的机器"的？ 把目标机器的规则表当数据写在纸带上读入。对应今天：程序是数据、软件可被加载——你装 App 就是给通用机"喂规则表"。 [!question]- Q3. 停机问题说明了什么？ 存在任何机器都永远无法解决的问题（如判定任意程序是否停机）。图灵机既给出了"可计算"的天花板（一切有明确步骤的问题），也划出了边界。 [!question]- Q4. 为什么说"再快的电脑也超不出图灵机"？ 电脑能算的图灵机都能算，只是慢——加 CPU、加内存只改变速度，不改变能力边界。能力边界由逻辑决定，不由硬件决定。 [!question]- Q5. 图灵机里的"书签"和"寄存器"各对应真实计算机的什么？ 读写头的位置 ≈ 程序计数器（06 篇的书签，记着下一步处理哪格）；当前状态 ≈ 寄存器组里保存的少量上下文。规则表 ≈ 程序本体。

9. 下一步学什么

10. 相关笔记