图灵机：纸带、读写头和最小通用计算

DFA 只有有限状态。NFA 允许同时保留多个状态。PDA 在有限状态之外加了一只栈，可以处理任意深度的嵌套。图灵机再往前走一步：它把栈换成一条可以读、写、左右移动的纸带。

这个变化很小，却足以把机器能力推到通用计算。图灵机仍然只有有限个控制状态，每一步仍然按规则机械执行；不同的是，机器可以在纸带上写下中间结果，之后再移动回来读取。程序状态和可变存储被明确分开。

本文先写一台最小确定性图灵机（Deterministic Turing Machine，DTM）。示例很小：读写头从第一个字符开始，把当前位置的符号改成 1，向右移动一格，然后停机。下一篇再用同一套结构实现一个稍微有算法味的纸带程序。

图灵机比 PDA 多了什么

PDA 的栈只能操作一端。读写都发生在栈顶，历史只能以后进先出的方式取回。图灵机的纸带更自由：读写头可以向左或向右移动，机器可以反复回到某个位置修改内容。

模型	有限控制	可增长存储	读写位置	典型能力
DFA / NFA	有	无	无	正则语言
PDA	有	栈	栈顶	嵌套结构
图灵机	有	纸带	当前格，可左右移动	通用计算

这个表里最关键的是“读写位置”。栈的访问方式受限，纸带的访问方式更接近内存。虽然纸带一次只能读写一个格子，但通过移动读写头，机器可以在任意位置保存和恢复信息。

模式提炼：控制状态和可变存储分离

control_state + mutable_storage -> computation

图灵机把计算拆成两部分：有限控制状态决定下一步规则，可变存储保存中间结果。这个拆法在工程里很常见。

场景	控制状态	可变存储
图灵机	当前状态	纸带
虚拟机	指令指针 / 执行状态	堆、栈、寄存器
解释器	AST 节点 / continuation	环境、输出、堆
工作流引擎	当前节点	流程上下文

听到“状态机需要写下东西，后面还要回来读”时，就已经离开纯有限自动机，进入“有限控制 + 可变存储”的模型。

纸带的最小表示

纸带可以看成三段：读写头左边、当前格、读写头右边。空白格用 _ 表示。

1 2	`left middle right [0] 01`

Python 里可以用 tuple 表示左右两侧。左侧 tuple 按从远到近排列，右侧 tuple 按从近到远排列。

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 __str__(self) -> str:
        return "".join(self.left) + f"[{self.middle}]" + "".join(self.right)

write 只改当前格。move_head_left 和 move_head_right 会把当前格挪到另一侧，并把相邻格变成新的当前格。如果一侧已经没有内容，就读到空白符号 _。

模式提炼：焦点窗口

left_context + focus + right_context

纸带实现用的是焦点窗口模式：把当前位置单独拿出来，左右两侧作为上下文保存。编辑器光标、流式 parser、zipper 数据结构都可以用类似表示。

场景	left_context	focus	right_context
图灵机纸带	读写头左侧	当前格	读写头右侧
文本编辑器	光标左侧文本	光标位置	光标右侧文本
parser	已读 token	当前 token	未读 token
树 zipper	父路径和左兄弟	当前节点	右兄弟和子树

焦点窗口的好处是当前位置操作很便宜，移动焦点时只需要重排局部上下文。

配置包含状态和纸带

图灵机的一次运行配置由当前状态和纸带组成。

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

状态属于有限控制。纸带保存可变数据。规则只看当前状态和当前格符号，然后决定三件事：写什么，向哪边移动，进入哪个状态。

1	`state + tape_symbol -> next_state + write_symbol + direction`

一条图灵机规则

TMRule 的字段正好对应上面的公式。

@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)

本文示例只需要一条核心规则：

1	`start + 0 -> halt + write 1 + move right`

为了让初始符号是 1 或空白时也能演示同样动作，完整代码里会补两条类似规则。

DTM 规则表和运行循环

确定性图灵机要求同一个状态和同一个纸带符号最多命中一条规则。

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()

这个 run 暴露了图灵机的核心风险：如果规则永远不进入接受状态，它就会一直运行。停机问题会在后面单独讨论。

完整示例

完整代码如下。

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 __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()


rulebook = DTMRulebook(
    [
        TMRule("start", "0", "halt", "1", "right"),
        TMRule("start", "1", "halt", "1", "right"),
        TMRule("start", "_", "halt", "1", "right"),
    ]
)

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

print(machine.current_configuration.state, machine.current_configuration.tape)
machine.run()
print(machine.current_configuration.state, machine.current_configuration.tape)

运行结果：

1 2	`start [0]01 halt 1[0]1`

初始纸带是 [0]01，读写头在第一个 0 上。机器把它写成 1，向右移动一格，然后进入 halt 状态。最终纸带显示为 1[0]1。

Java 程序员的迁移表

Python 写法	Java 对照	作用
`Tape`	可扩展数组 / 双端队列 / gap buffer	可读写存储
`TMConfiguration`	`record Configuration(State, Tape)`	当前状态和存储
`TMRule`	指令对象	读、写、移动、跳转
`DTMRulebook`	指令表 / dispatch table	根据状态和当前符号找规则
`DTM.step()`	解释器的一步执行	执行一条指令
`DTM.run()`	指令循环	持续执行直到停机

图灵机和虚拟机的距离比看起来更近。虚拟机也有当前执行位置、可变存储、指令表和循环执行过程。区别在于真实虚拟机有更丰富的指令、更高效的内存模型、更复杂的调用栈和异常机制。

从最小模型到通用计算

本文的机器只会改一个格子，不具备通用计算能力。通用性来自规则集和编码方式：只要纸带能表示程序和数据，规则能解释这些编码，机器就可以模拟其他计算过程。

这个观点会在后面继续展开。下一篇先不直接谈通用机，而是用同一套 Python 结构写一个更像程序的图灵机：在纸带上移动、寻找位置、改写符号，展示“读写头 + 可变纸带”怎样形成指令循环。

练习

第一，把示例改成“把第一个 1 改成 0，再向右移动”。

第二，把接受状态从 halt 改成 done，观察需要修改哪些规则。

第三，增加一条规则，让机器在读到 0 时向右移动但不停止，直到读到空白 _ 才写入 1 并停机。

第四，给 DTM.run() 增加最大步数限制，避免规则写错时无限循环。

参考资料

Understanding Computation 官方目录

Tom Stuart/computationbook 示例代码仓库

Python 文档：dataclasses

Java 文档：ArrayDeque