16.1 图灵机
图灵机（Turing machine）是刻意精简的计算数学模型。它没有语法分析器（parser）、堆内存（heap）、操作系统（operating system）或硬件流水线（hardware pipeline），只有分成单元的无限长纸带、有限字母表（alphabet）、一个读写头（read/write head）与有限的控制状态（control states）。尽管结构极其简单，只要给予足够的时间和纸带，它可以表达现代通用可编程计算机能够表达的所有算法。因此，它非常适合在不考虑实际工程速度的前提下，专门讨论“计算在原则上能做到什么”。
确定性单带机器通常写成一个多元组（tuple）：
M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)其中 Q 是有限状态集（state set）；Σ 是不包含空格符的输入字母表（input alphabet）；Γ 是包含 Σ、空格符（blank）与工作标记符的工作纸带字母表（tape alphabet）。状态转移函数 δ（Transition function）把一个非停机状态与当前的读取符号，映射到一个新的状态、要写入的符号以及读写头的移动方向 （向左）或 （向右）。初始状态、接受状态以及拒绝状态各自承担特殊的运行时角色。
配置（Configuration）描述计算的一个瞬间
机器完整的瞬时运行状态称为配置（configuration）：包括当前的控制状态、纸带上的非空内容以及读写头的位置。每一次状态转移（transition）都仅仅改变这个 configuration。以一进制自增（unary increment）为例，输入 111 表示数值三：
δ(scan, 1) = (scan, 1, R)
δ(scan, □) = (accept, 1, R)
111□ → 111□ → 111□ → 1111
^ ^ ^ ^读写头向右越过每一个 1，再把遇到的第一个空格（blank）改为 1，随后进入接受状态。二进制自增则稍微复杂一些：从最低有效位开始，把末尾连续的 1 改为 0 并向左进位，最后把遇到的第一个 0 或最左侧的空格改为 1。
当机器到达接受状态 q_accept 时，输入被接受（accept）；到达拒绝状态 q_reject 时则被拒绝（reject）；若状态转移永远不终止，则称为发散（divergent）。发散不等于拒绝，除非机器本身是一个对任何输入都一定会停机的判定器（decider）。状态转移表可以是部分定义的（partial）；对任何未定义转移的语义必须予以明确说明，在理论上通常视为拒绝或停滞（stuck），绝不能采取静默的猜测。
程序与输入都能编码为数据
图灵机只有有限的状态与状态转移规则，所以其机器描述可以完全编码成有限长度的字符串（finite string）。给状态与纸带符号（tape symbols）进行编号，再编码每一个状态转移元组（transition tuple），并利用自定界方案（self-delimiting scheme），让数据记录与机器/输入之间的边界都可以被完美地还原出来。于是，我们就可以用符号 ⟨M,w⟩ 表示图灵机 M 及其输入数据 w 的字符串编码。
通用图灵机（universal Turing machine） U 读取编码 ⟨M,w⟩，并直接在纸带上模拟 M 在 w 上的全部执行过程。在这里，被模拟的程序就是 U 纸带上的底层数据，这与 Chapter 15 中字节码作为虚拟机的执行数据是完全同构的。这构成了著名的存储程序计算（stored-program computing）、解释器（interpreter）、模拟器（emulator）与元循环工具（metacircular tool）的数学理论核心，同时也使得自指（self-reference）成为了可能：程序的描述代码本身完全可以作为其自身的输入数据。
变体改变效率，不改变可计算能力
在可计算理论的图灵-邱奇论题（Church-Turing thesis）假设下，多带图灵机（multi-tape machine）、非确定性图灵机（nondeterministic machine）、双向无限纸带机、寄存器机（register machine）、λ 演算（lambda calculus）以及主流的通用编程语言，其本质上都在计算同一类偏函数（partial functions）。多带图灵机可能在表达上更方便、在执行上更快，但基础的单带图灵机仍能以一定的多项式模拟开销（overhead）去无缝地模拟它。在这里，我们清晰地划分了可计算性（computability）（即是否存在可行算法）与复杂度（complexity）（即算法在运行中需要耗费多少计算资源）。
图灵机并不是一种实用的编译器中间表示（compiler IR），而是一种数学抽象。若某种编译器优化遍（pass）或静态分析器（analyzer）能由普通的、保证终止的计算机程序来实现，它就一定能由图灵机来进行数学建模；同理，若某一个判定问题（decision problem）已经被在数学上严格证明对图灵机是不可能的，那么任凭采用更快的 CPU、部署更多的多线程、引入更强大的 LLVM/JIT，或者设计更丰富的高级语言，都绝对不可能为它创造出某种普适的完美算法。
该数学模型理论上仍假设底层的纸带拥有潜在无限的存储容量（storage）。尽管任何具象的物理计算机内存都是有限的，从而使得其整体的瞬时状态配置也是有限个数的，这并不能用来在实用的通用场景中侥幸宣称攻克了“任意程序分析”的理论难题：因为这个内存物理边界（bound）会随着硬件配置产生巨大变化，往往巨大到完全不可用，且实用的生产级编程语言通常不会在编译器层面给动态堆分配（allocation）与数据输入设置一个全局固定的物理上限。后续章节将用这些被编码的机器、机器模拟与自指原理，为可判定性（decidability）和静态分析（static analysis）划出精确且诚实的终极边界。