通用图灵机

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

一次模拟循环先从工作带读出被模拟状态 $q$ 和头下符号 $a$，在输入携带的转移表中查找 $(q,a)$，然后更新被模拟带的一个格子、头位置和状态。假设查到 $\delta (q,1)=(r,0,R)$，那么快照 (q,101,头在首位) 变为 (r,001,头在第二位)；通用机可能为这一个被模拟步骤执行许多自己的步骤，但必须保持这项配置对应。

现代解释器把源程序或字节码连同输入交给同一个运行时，结构上类似 $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每个总可计算的程序代码变换都存在一个与其变换结果计算同一偏函数的程序索引。再由自应用构造语义固定点。停机问题、对角化与自解释器由此有统一索引语言；复杂性理论若关心资源，还需另行指定高效通用模拟器。