通用性：一种机器怎样模拟另一种机器

前面的文章已经走过两条计算模型路线。图灵机用纸带和指令循环表达计算，lambda 演算用函数应用和表达式规约表达计算。Church 编码进一步说明，数字和布尔值也可以由函数行为构造出来。

这些模型看起来差异很大，却都能表达同一类可计算过程。通用性的核心在于：一种机器可以把另一种机器的程序和数据编码成自己的数据，然后按规则解释这份编码。

本文用一个小型寄存器机解释器展示“程序作为数据”这件事。示例不会追求指令集完整性，只展示通用解释器的基本形状。

从专用机器到通用机器

DFA、PDA、某个固定规则表的图灵机，都像专用机器。规则写死以后，它只能识别或执行某一类任务。

通用机器多了一层编码：

encoded_program + input_data + interpreter -> output_data

程序不再只是宿主语言里的代码，也可以是一段数据。解释器读取这段数据，根据其中的指令改变配置。只要编码方式足够表达指令和数据，解释器就能模拟很多不同程序。

这个结构正是虚拟机、脚本引擎和 DSL runtime 的共同骨架。

场景	程序数据	解释器
JVM	bytecode	JVM 执行引擎
JavaScript	AST / bytecode	JS 引擎
SQL	查询计划	查询执行器
工作流	流程定义	工作流引擎
图灵机	机器编码和输入纸带	通用图灵机

一个很小的寄存器机

寄存器机可以用几个整数寄存器和一段指令列表表示。本文只实现五条指令：

指令	含义
inc name	寄存器加一
dec name	寄存器减一
jump target	跳转到指定指令位置
jump_if_zero name target	寄存器为零时跳转
halt	停机

用这几条指令可以写一个加法程序：把 y 一次次减一，同时把 x 一次次加一；当 y 变成零，程序停机。初始 x=3, y=2，结束时 x=5, y=0。

while y != 0:
    y -= 1
    x += 1

程序是一段数据

指令可以定义成普通数据对象。

from dataclasses import dataclass


@dataclass(frozen=True)
class Instruction:
    opcode: str
    args: tuple[str | int, ...] = ()

加法程序就是一个列表。

program = [
    Instruction("jump_if_zero", ("y", 4)),
    Instruction("dec", ("y",)),
    Instruction("inc", ("x",)),
    Instruction("jump", (0,)),
    Instruction("halt"),
]

这里的 program 没有直接调用 Python 语句。它只是数据。真正执行它的是后面的 run 函数。

单步执行

解释器的配置由两部分组成：程序计数器 pc 和寄存器表 registers。单步执行读取 program[pc]，根据 opcode 决定下一步配置。

def step(
    program: list[Instruction],
    pc: int,
    registers: dict[str, int],
) -> tuple[int, dict[str, int], bool]:
    instruction = program[pc]
    next_registers = registers.copy()

    match instruction.opcode:
        case "inc":
            (name,) = instruction.args
            next_registers[str(name)] += 1
            return pc + 1, next_registers, False
        case "dec":
            (name,) = instruction.args
            next_registers[str(name)] -= 1
            return pc + 1, next_registers, False
        case "jump":
            (target,) = instruction.args
            return int(target), next_registers, False
        case "jump_if_zero":
            name, target = instruction.args
            if next_registers[str(name)] == 0:
                return int(target), next_registers, False
            return pc + 1, next_registers, False
        case "halt":
            return pc, next_registers, True
        case _:
            raise ValueError(f"unknown opcode: {instruction.opcode!r}")

这段代码和前面的图灵机 step 很像：

current_configuration -> next_configuration

区别在于图灵机规则表来自机器定义，寄存器机规则来自 program 这份数据。解释器的代码保持不变，换一份程序数据，就能执行另一段逻辑。

运行循环

运行循环不断调用 step，直到遇到 halt。

def render(registers: dict[str, int]) -> str:
    return " ".join(f"{name}={registers[name]}" for name in sorted(registers))


def run(program: list[Instruction], registers: dict[str, int]) -> dict[str, int]:
    pc = 0

    while True:
        print(f"pc={pc} {render(registers)}")
        pc, registers, halted = step(program, pc, registers)
        if halted:
            return registers

run 就是通用解释器的缩影。它不关心程序要做加法、减法还是循环，只关心指令编码和执行规则。

完整示例

完整代码如下。

from dataclasses import dataclass


@dataclass(frozen=True)
class Instruction:
    opcode: str
    args: tuple[str | int, ...] = ()


def render(registers: dict[str, int]) -> str:
    return " ".join(f"{name}={registers[name]}" for name in sorted(registers))


def step(
    program: list[Instruction],
    pc: int,
    registers: dict[str, int],
) -> tuple[int, dict[str, int], bool]:
    instruction = program[pc]
    next_registers = registers.copy()

    match instruction.opcode:
        case "inc":
            (name,) = instruction.args
            next_registers[str(name)] += 1
            return pc + 1, next_registers, False
        case "dec":
            (name,) = instruction.args
            next_registers[str(name)] -= 1
            return pc + 1, next_registers, False
        case "jump":
            (target,) = instruction.args
            return int(target), next_registers, False
        case "jump_if_zero":
            name, target = instruction.args
            if next_registers[str(name)] == 0:
                return int(target), next_registers, False
            return pc + 1, next_registers, False
        case "halt":
            return pc, next_registers, True
        case _:
            raise ValueError(f"unknown opcode: {instruction.opcode!r}")


def run(program: list[Instruction], registers: dict[str, int]) -> dict[str, int]:
    pc = 0

    while True:
        print(f"pc={pc} {render(registers)}")
        pc, registers, halted = step(program, pc, registers)
        if halted:
            return registers


program = [
    Instruction("jump_if_zero", ("y", 4)),
    Instruction("dec", ("y",)),
    Instruction("inc", ("x",)),
    Instruction("jump", (0,)),
    Instruction("halt"),
]

result = run(program, {"x": 3, "y": 2})
print("result", render(result))

运行结果：

pc=0 x=3 y=2
pc=1 x=3 y=2
pc=2 x=3 y=1
pc=3 x=4 y=1
pc=0 x=4 y=1
pc=1 x=4 y=1
pc=2 x=4 y=0
pc=3 x=5 y=0
pc=0 x=5 y=0
pc=4 x=5 y=0
result x=5 y=0

读取执行轨迹

pc=0 是条件检查。只要 y 不为零，就进入 dec y 和 inc x，再跳回 pc=0。

pc=0 x=3 y=2
pc=1 x=3 y=2
pc=2 x=3 y=1
pc=3 x=4 y=1

第一轮结束后，x 从 3 变成 4，y 从 2 变成 1。第二轮后，x 变成 5，y 变成 0。再次检查 pc=0 时，jump_if_zero 跳到 pc=4，程序停机。

这个小程序展示了三层结构：

层次	示例
被解释程序	program 指令列表
被解释数据	{"x": 3, "y": 2}
解释器	step 和 run

换一份 program，同一个 run 可以模拟另一段寄存器机程序。这就是通用性的入口。

和图灵机、lambda 演算的关系

图灵机可以把另一台图灵机的状态、纸带、规则表编码到自己的纸带上，再用固定规则解释这份编码。lambda 演算可以把数据和控制都编码成函数，通过规约表达执行过程。寄存器机解释器则把指令列表编码成 Python 数据，再用 run 执行。

三者共同的抽象是：

description_of_machine + input -> simulated_result

不同模型的编码细节不一样，但都依赖同一个观念：程序可以被当作数据处理，解释器可以按规则执行这些数据。

Java 程序员的迁移表

本文模型	Java 工程对照	说明
Instruction	bytecode / command object	程序编码
program	class file / script AST / workflow definition	可解释数据
registers	frame / context / environment	运行时状态
pc	instruction pointer	当前执行位置
step	bytecode dispatch	单条指令执行
run	VM loop / engine loop	通用解释循环

JVM、表达式引擎、规则引擎、工作流引擎都可以用这张表解释。工程系统会有类型检查、异常、调用栈、内存管理和优化器，但最内层仍然是“读一条编码，改一次运行配置”。

模式提炼：程序作为数据

program_as_data + interpreter -> execution

这个模式改变了扩展方式。没有解释器时，每增加一个行为都要改宿主程序。引入解释器后，宿主程序可以保持稳定，变化进入被解释的数据。

需求	无解释器	有解释器
新业务规则	改 Java 代码	改规则数据
新工作流	发版	更新流程定义
新表达式	增加分支逻辑	传入 AST
新计算过程	改执行器	传入程序编码

代价也很明确：解释器需要定义语言边界、错误处理、调试方式和资源限制。下一篇的停机问题会说明，通用性一旦出现，某些静态判断就不可能有完备算法。

练习

第一，增加 set name value 指令，用它初始化寄存器。

第二，增加 copy source target 指令，观察它怎样改变可表达程序的写法。

第三，给 run 增加最大步数限制，避免程序写成死循环。

第四，把 program 改成计算 x * y：用外层循环重复执行加法。

参考资料

• Understanding Computation 官方目录
• Tom Stuart/computationbook 示例代码仓库
• Python 文档：dataclasses
• Java 虚拟机规范：The class File Format