图灵机

上级：logic

"算法"的形式化模型。（为什么它长成这个样子 → history；经典机器 → examples、busy-beaver。）

图灵机

一个七元组 (Q, Γ, b, Σ, δ, q₀, F)：

• Q — 一个有限的状态集；q₀ ∈ Q 是起始状态，F ⊆ Q 是停机状态集；
• Γ — 一个有限的带字母表；b ∈ Γ 是空白符号；Σ ⊆ Γ∖{b} 是输入字母表；
• δ : (Q∖F) × Γ → Q × Γ × {L,R} — 转移函数。 再加上一条双向无限的纸带（每个格子存放 Γ 中的一个符号）和一个位于某一格上的读写头。

运行。 一个格局（configuration）就是 (状态, 纸带内容, 读写头位置)。每一步：读取当前扫描到的符号 a；若 δ(q,a)=(q',a',D)，就写入 a'，将读写头沿 D∈{L,R} 方向移动一格，并进入状态 q'。到达 F 即停机（δ 无定义处同样停机）。若 M 从纸带写有 x 出发运行，最终停机时纸带上写着 f(x)，就称 M 计算了 f。

要点

• 对变体稳健。 多带、二维带、k 符号、非确定性——都计算同一个类（相互模拟，最坏情况下只有多项式开销）。正是这种稳健性，才使这个模型成为那个定义，而不是一个随意的选择。
• 通用机器。 存在一台单独的图灵机 U，给定一段描述 ⟨M⟩ 和输入 x，它就能模拟出 M(x)。数据 = 程序——存储程序计算机的雏形。
• 判定 vs 识别。 若 M 对每一个输入都停机并给出是/否的答案，就称它判定了一个集合；若它恰好在为是的实例上停机，就称它识别（半判定）了这个集合。这个单边的缺口，正是undecidability所在之处（停机问题是可识别的，但不可判定）。

子级

• history — 这个定义是被逼出来的：希尔伯特的判定问题 → 图灵对一名人类计算者的分析 → Church/Kleene → 邱奇－图灵论题。
• halting-problem — 第一个不可判定问题（对角线法）；Rice 定理；归约。
• examples — 可以手动逐步追踪的小型具体机器（后继函数、0ⁿ1ⁿ、通用机器）。
• famous-machines — busy-beaver、最小通用机、Langton 蚂蚁、Rule 110、以及编码了基础性问题（ZFC / 哥德巴赫猜想 / 黎曼猜想）的机器。