用 Python 写一台图灵机

上一篇文章已经写出一台最小 DTM：读取当前格，写入一个符号，移动读写头，然后停机。那台机器能展示图灵机的组成，但还不像一段程序。

本文复用同一套 Python 结构，把图灵机写成一个更接近算法的例子：对纸带上的二进制数加一。输入是 1011，输出是 1100。机器需要先移动到数字右侧的空白格，再从右向左处理进位。这个过程会经过多个状态和多次纸带改写，适合观察“有限控制 + 可变纸带”怎样形成完整计算。

二进制加一的规则

二进制加一可以拆成两个阶段。

第一阶段从最左侧开始，一直向右移动，直到读到数字后面的空白格 _。

第二阶段从空白格左移一格，开始处理进位：

当前符号	写入符号	下一步
1	0	继续向左进位
0	1	进位结束，停机
_	1	数字整体增长一位，停机

以 1011 为例，最右侧两个 1 都会变成 0，左边的 0 变成 1，结果得到 1100。

1011 + 1 = 1100

这里需要两个控制状态：

状态	含义
seek_right	向右寻找数字末尾
carry	从右向左处理进位
halt	计算完成

图灵机的状态名承担了程序阶段的作用。seek_right 类似扫描循环，carry 类似带进位的回写循环，halt 是终止条件。

纸带和配置

纸带仍然采用上一篇的焦点窗口表示：读写头左侧、当前格、读写头右侧。

from dataclasses import dataclass


State = str
TapeSymbol = str
Direction = str


@dataclass(frozen=True)
class Tape:
    left: tuple[TapeSymbol, ...]
    middle: TapeSymbol
    right: tuple[TapeSymbol, ...]
    blank: TapeSymbol

    def write(self, character: TapeSymbol) -> "Tape":
        return Tape(self.left, character, self.right, self.blank)

    def move_head_left(self) -> "Tape":
        if self.left:
            return Tape(
                self.left[:-1],
                self.left[-1],
                (self.middle,) + self.right,
                self.blank,
            )

        return Tape((), self.blank, (self.middle,) + self.right, self.blank)

    def move_head_right(self) -> "Tape":
        if self.right:
            return Tape(
                self.left + (self.middle,),
                self.right[0],
                self.right[1:],
                self.blank,
            )

        return Tape(self.left + (self.middle,), self.blank, (), self.blank)

    def contents(self) -> str:
        return "".join(self.left + (self.middle,) + self.right).strip(self.blank)

    def __str__(self) -> str:
        return "".join(self.left) + f"[{self.middle}]" + "".join(self.right)

contents 用于取出最终纸带内容，并去掉两端空白符号。__str__ 保留读写头位置，适合打印执行轨迹。

运行配置仍然只有状态和纸带两部分。

@dataclass(frozen=True)
class TMConfiguration:
    state: State
    tape: Tape

指令规则

一条图灵机规则包含五个字段：当前状态、当前符号、下一状态、写入符号、移动方向。

@dataclass(frozen=True)
class TMRule:
    state: State
    character: TapeSymbol
    next_state: State
    write_character: TapeSymbol
    direction: Direction

    def applies_to(self, configuration: TMConfiguration) -> bool:
        return (
            self.state == configuration.state
            and self.character == configuration.tape.middle
        )

    def follow(self, configuration: TMConfiguration) -> TMConfiguration:
        written_tape = configuration.tape.write(self.write_character)

        if self.direction == "left":
            next_tape = written_tape.move_head_left()
        elif self.direction == "right":
            next_tape = written_tape.move_head_right()
        else:
            raise ValueError(f"unknown direction: {self.direction!r}")

        return TMConfiguration(self.next_state, next_tape)

这段代码像一个极小的指令执行器。applies_to 负责判断当前配置是否命中指令，follow 负责写纸带、移动读写头、跳到下一状态。

规则表和运行循环

规则表根据当前配置找到唯一可用规则。若没有规则，机器无法继续；若同一配置命中多条规则，确定性被破坏。

class DTMRulebook:
    def __init__(self, rules: list[TMRule]) -> None:
        self.rules = rules

    def next_configuration(self, configuration: TMConfiguration) -> TMConfiguration:
        rule = self.rule_for(configuration)

        if rule is None:
            raise ValueError(
                f"no rule for state={configuration.state!r}, "
                f"symbol={configuration.tape.middle!r}"
            )

        return rule.follow(configuration)

    def rule_for(self, configuration: TMConfiguration) -> TMRule | None:
        matches = [rule for rule in self.rules if rule.applies_to(configuration)]

        if len(matches) > 1:
            raise ValueError("DTM rulebook must be deterministic")

        return matches[0] if matches else None

运行态机器提供 step、run 和 trace。trace 会把每一步配置打印出来，作用接近解释器调试器。

class DTM:
    def __init__(
        self,
        current_configuration: TMConfiguration,
        accept_states: set[State],
        rulebook: DTMRulebook,
    ) -> None:
        self.current_configuration = current_configuration
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return self.current_configuration.state in self.accept_states

    def step(self) -> None:
        self.current_configuration = self.rulebook.next_configuration(
            self.current_configuration
        )

    def run(self) -> None:
        while not self.accepting():
            self.step()

    def trace(self) -> None:
        print(self.current_configuration.state, self.current_configuration.tape)

        while not self.accepting():
            self.step()
            print(self.current_configuration.state, self.current_configuration.tape)

完整示例

完整代码如下。

from dataclasses import dataclass


State = str
TapeSymbol = str
Direction = str


@dataclass(frozen=True)
class Tape:
    left: tuple[TapeSymbol, ...]
    middle: TapeSymbol
    right: tuple[TapeSymbol, ...]
    blank: TapeSymbol

    def write(self, character: TapeSymbol) -> "Tape":
        return Tape(self.left, character, self.right, self.blank)

    def move_head_left(self) -> "Tape":
        if self.left:
            return Tape(
                self.left[:-1],
                self.left[-1],
                (self.middle,) + self.right,
                self.blank,
            )

        return Tape((), self.blank, (self.middle,) + self.right, self.blank)

    def move_head_right(self) -> "Tape":
        if self.right:
            return Tape(
                self.left + (self.middle,),
                self.right[0],
                self.right[1:],
                self.blank,
            )

        return Tape(self.left + (self.middle,), self.blank, (), self.blank)

    def contents(self) -> str:
        return "".join(self.left + (self.middle,) + self.right).strip(self.blank)

    def __str__(self) -> str:
        return "".join(self.left) + f"[{self.middle}]" + "".join(self.right)


@dataclass(frozen=True)
class TMConfiguration:
    state: State
    tape: Tape


@dataclass(frozen=True)
class TMRule:
    state: State
    character: TapeSymbol
    next_state: State
    write_character: TapeSymbol
    direction: Direction

    def applies_to(self, configuration: TMConfiguration) -> bool:
        return (
            self.state == configuration.state
            and self.character == configuration.tape.middle
        )

    def follow(self, configuration: TMConfiguration) -> TMConfiguration:
        written_tape = configuration.tape.write(self.write_character)

        if self.direction == "left":
            next_tape = written_tape.move_head_left()
        elif self.direction == "right":
            next_tape = written_tape.move_head_right()
        else:
            raise ValueError(f"unknown direction: {self.direction!r}")

        return TMConfiguration(self.next_state, next_tape)


class DTMRulebook:
    def __init__(self, rules: list[TMRule]) -> None:
        self.rules = rules

    def next_configuration(self, configuration: TMConfiguration) -> TMConfiguration:
        rule = self.rule_for(configuration)

        if rule is None:
            raise ValueError(
                f"no rule for state={configuration.state!r}, "
                f"symbol={configuration.tape.middle!r}"
            )

        return rule.follow(configuration)

    def rule_for(self, configuration: TMConfiguration) -> TMRule | None:
        matches = [rule for rule in self.rules if rule.applies_to(configuration)]

        if len(matches) > 1:
            raise ValueError("DTM rulebook must be deterministic")

        return matches[0] if matches else None


class DTM:
    def __init__(
        self,
        current_configuration: TMConfiguration,
        accept_states: set[State],
        rulebook: DTMRulebook,
    ) -> None:
        self.current_configuration = current_configuration
        self.accept_states = accept_states
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return self.current_configuration.state in self.accept_states

    def step(self) -> None:
        self.current_configuration = self.rulebook.next_configuration(
            self.current_configuration
        )

    def run(self) -> None:
        while not self.accepting():
            self.step()

    def trace(self) -> None:
        print(self.current_configuration.state, self.current_configuration.tape)

        while not self.accepting():
            self.step()
            print(self.current_configuration.state, self.current_configuration.tape)


rulebook = DTMRulebook(
    [
        TMRule("seek_right", "0", "seek_right", "0", "right"),
        TMRule("seek_right", "1", "seek_right", "1", "right"),
        TMRule("seek_right", "_", "carry", "_", "left"),
        TMRule("carry", "1", "carry", "0", "left"),
        TMRule("carry", "0", "halt", "1", "right"),
        TMRule("carry", "_", "halt", "1", "right"),
    ]
)

tape = Tape((), "1", ("0", "1", "1"), "_")
machine = DTM(TMConfiguration("seek_right", tape), {"halt"}, rulebook)

machine.trace()
print("result", machine.current_configuration.tape.contents())

运行结果：

seek_right [1]011
seek_right 1[0]11
seek_right 10[1]1
seek_right 101[1]
seek_right 1011[_]
carry 101[1]_
carry 10[1]0_
carry 1[0]00_
halt 11[0]0_
result 1100

读取执行轨迹

前五行都处在 seek_right 状态。机器只保持原符号，持续向右移动，直到读到空白格。

seek_right 1011[_]

读到空白格后，机器进入 carry 状态并向左移动。接着按二进制进位规则处理：

carry 101[1]_
carry 10[1]0_
carry 1[0]00_
halt 11[0]0_

两个低位 1 被写成 0，左侧的 0 被写成 1，机器进入 halt。最终结果由 contents() 取出，得到 1100。

这个轨迹展示了图灵机程序的三个层次：

层次	示例
数据	纸带上的 1011
控制阶段	seek_right、carry、halt
指令	state + symbol -> write + move + next_state

状态负责阶段切换，纸带负责保存中间结果，规则表负责把阶段和数据组合成下一步动作。

Java 程序员的迁移表

图灵机模型	Java 工程对照	迁移点
Tape	可变内存、数组、gap buffer、ArrayDeque	读写位置和存储分离
TMConfiguration	record Configuration(State state, Tape tape)	一次执行快照
TMRule	指令对象、状态转移对象	条件、写入、移动、跳转打包
DTMRulebook	dispatch table、规则引擎	根据当前状态和输入选择规则
DTM.step()	解释器单步执行	一条指令推进一次配置
DTM.trace()	调试 trace、执行日志	观察状态和存储的同步变化

把图灵机翻译成 Java 时，代码结构通常会变成三组对象：存储对象、指令对象、执行循环。虚拟机、模板解释器、工作流引擎、规则引擎都能看到这个形状。差异主要在指令集规模、存储模型和错误处理，而不是控制骨架。

模式提炼：规则表就是指令集

本文示例的规则表只有六条，但已经具备指令集的基本味道。

current_state + current_symbol -> next_state + write_symbol + movement

在工程里，这种模式常见于几类场景。

场景	当前状态	当前输入	动作
字节码解释器	指令指针	opcode	修改栈和寄存器，跳转
工作流引擎	流程节点	事件 / 条件	更新上下文，进入下一节点
parser	解析状态	token	生成节点，移动游标
规则引擎	事实集合	匹配条件	写入结论，触发后继规则

图灵机把这些结构压缩到极限：输入只有当前格符号，动作只有写入、左移、右移、跳转。正因为模型足够小，执行循环和规则表之间的边界变得清晰。

从纸带机器到函数模型

图灵机通过“读写头 + 纸带 + 指令循环”表达计算。后续文章会换一个方向：lambda 演算用“函数 + 应用 + 替换”表达计算。两者表面差异很大，但都在回答同一个问题：最少需要哪些规则，才能描述任意可执行过程。

图灵机强调可变存储和逐步执行。lambda 演算强调表达式变换和函数应用。把两条路径并排看，通用计算不再依赖某一种编程语言的语法，而依赖可机械执行的规则系统。

练习

第一，把输入改成 111，观察结果如何变成 1000。

第二，给 DTM.run() 和 DTM.trace() 增加最大步数限制，避免规则表写错时无限执行。

第三，把 contents() 改成返回读写头左侧、当前格、右侧三段，便于调试空白格。

第四，增加一组规则，把二进制数减一。需要明确输入为 0 时的处理策略。

参考资料

• Understanding Computation 官方目录
• Tom Stuart/computationbook 示例代码仓库
• Python 文档：dataclasses
• Java 文档：ArrayDeque