图灵机——实例详解

上级：turing-machines

这些是可以手工逐步演算的具体机器。每个子条目都给出该机器完整的七元组 (Q, Γ, b, Σ, δ, q₀, F)，然后逐步追踪纸带，说明每一步是哪个组件在起作用。

示例

• binary-successor ——n ↦ n+1，对照七元组逐位追踪（最清晰的入门示例）。
• anbn-recognizer ——通过逐对划掉符号来识别 { 0ⁿ1ⁿ }；把纸带用作无界内存（有限自动机做不到这一点）。
• universal-machine ——U(⟨M⟩, x)：转移表本身就存在于纸带上——数据即程序。