通用图灵机

机器本身也能表示成数据。通用机把“硬件规则固定、程序作为输入”这一现代存储程序计算机观念形式化：一个固定解释器读取另一台机器的有限编码和输入，维护被模拟带、状态与头位置并逐步解释每条转移，就能执行任意可编码算法。程序与数据采用同一种有限字符串表示，也是自指、编译器和可计算性极限得以出现的根源。

给定 $⟨M,w⟩$，通用机 $U$ 模拟 $M$ 在 $w$ 上的每一步：若 $M$ 接受、拒绝或循环，$U$ 分别具有同样行为。现代解释器把源程序或字节码连同输入交给同一个运行时，结构上类似 $U(⟨M,w⟩)$；但具体解释器只覆盖某种语法，而通用图灵机的编码可包含任意图灵机转移表。若编码不是可判定、可解析的合法机器描述，所谓模拟问题本身就没有固定形式。

通用性不表示有限设备能实际保存无穷带，也不保证高效或常数开销：朴素模拟可能产生多项式甚至更大的时间开销。它同样不保证模拟机能预知被模拟程序何时停机。恰恰因为 $U$ 能接受自身及其他程序编码，才可构造 $⟨M,M⟩$ 一类自指输入；这不是编码歧义，而是模型的预期能力。

通用机建立在 图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。 可有效编码的事实上，使“程序分析另一个程序”得到形式化。程序编号与可接受编号公理库程序编号与可接受编号Program indexing · Acceptable numbering · Gödel numbering对部分可计算函数进行有效枚举，并要求编号支持通用解释与有效参数编译。把这种解释能力组织成有效枚举，$s$-$m$-$n$ 定理公理库s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。把部分实参固化进新程序代码，Kleene 递归定理公理库Kleene 递归定理Kleene recursion theorem每个总可计算的程序代码变换都存在一个与其变换结果计算同一偏函数的程序索引。再由自应用构造语义固定点。停机问题、对角化与自解释器由此有统一索引语言；复杂性理论若关心资源，还需另行指定高效通用模拟器。