turing machine · halting · brainfuck · rule 110

从一条纸带到「万物皆可计算」

1936 年图灵为回答一个纯数学问题（Entscheidungsproblem，判定性问题），设计了一台异常精简的机器：一条无限长纸带、一个读写头、一张「读到什么就执行什么」的指令表。出人意料的是，只要这台机器能实现，任何可计算的问题它都能算。今天所有主流编程语言本质上都与它算力等价，这种等价就称为图灵完备 (Turing completeness)。

本页从机器本身出发，逐步走到它的能力边界与各种意外的实现形式，五节依次是图灵机、停机问题、Brainfuck、Rule 110、意外图灵完备。文中会用有限状态机 (DFA) 作对比，可参考 automata 系列。

1 · 图灵机：一条纸带就够了

1936 年图灵提出的这台机器只有五个组成部分：一条无限长纸带，分成一格格，每格写至多一个字符（空格记作 ␣）；一个读写头，指着某一格，能读、擦、写，还能向左或向右挪一格；一组有限的 state，即当前所处的内部状态；一个特殊的停机 state；一张指令表 $\delta$ 。指令表就是它的全部程序，每一条形如「在 state $q$ 、读到字符 $c$ ：写下 $c'$ 、向左或向右移一格、切到 state $q'$ 」。

图 1-1 · 读写头读当前格，在右侧指令表里找到对应规则（高亮），执行擦写、移动、切换 state，直到进入停机 state。可换机器、改输入、单步执行。「二进制 +1」演示进位如何沿纸带逐格左传；「回文判定」则是 DFA 做不到的任务——DFA 需要记住任意长的前半段，而图灵机靠来回擦写纸带即可。

它没有加减乘、没有变量，却能完成任意可计算的任务。图灵由此证明了一个重要结论：凡是人类能按某套明确步骤算出来的问题，这台机器都能算，反之亦然，这就是 Church–Turing thesis。于是「可计算」不再是模糊的直觉，而有了精确含义——能被某台图灵机算出来。

警示 · 无限纸带是这套论断的关键前提。真实算盘和电脑内存都是有限的，所以严格说它们是有限状态机而非图灵机；内存够用时两者表现一致，内存耗尽时差异才显现。正是这条无限存储假设，让图灵机能完成 DFA 无法完成的任务，例如识别任意长的回文。

2 · 停机问题的硬边界

图灵机能算的东西多到惊人，但它不是万能的。最著名的反例是停机问题：给定任意一段程序和它的输入，判断它最终会停下来，还是会永远跑下去。听上去该有办法，图灵却证明了不存在任何通用程序能对所有输入正确回答这个问题——它是不可判定 (undecidable) 的。

为什么不能直接运行一遍观察？因为如果它确实会死循环，就永远等不到「它不会停」的结论，只能一直等下去。

图 2-1 · 扮演判定器：设定一个步数预算 B 并运行 B 步。程序在预算内停下时能下结论，一旦跑满 B 步仍在运行就无法做出任何判断。可点「构造反例」看预算被绕过。

警示 · 无论把预算 $B$ 设成多大，总能构造一个恰好跑 $B+1$ 步才停的程序绕过它，所以没有任何固定预算适用。那么让预算无限大是否可行？对确实会死循环的程序，这会永远运行下去、得不到答案。Collatz 更隐蔽：数学家至今无法证明它对所有起点都会停（Collatz 猜想），运行再多步也只能说明「还没停」，而非「不会停」。

2.1 · 对角线反证

图灵的证明使用对角线法 (diagonalization)：假设判定器存在，就能构造一台让它自相矛盾的机器。

图 2-2 · 反证的逐步展开。可单步推进，看矛盾如何从「假设 halts 存在」这一步生出来。

矛盾源于假设 halts 存在，因此该假设不成立，通用停机判定器不可能存在。更进一步的是 Rice 定理：程序的任何非平凡语义性质（是否输出 42、是否访问网络、是否为恶意代码）都不可判定。

这对工程的含义见意外图灵完备一节——它说明了为什么「完美的编译器优化、零误报零漏报的死代码检测、永远正确的杀毒引擎、能拦截所有死循环的 linter」在原理上不可能存在，工程上只能用保守近似加超时加启发式来逼近。

3 · Brainfuck：用 8 个符号理解图灵完备

1993 年 Urban Müller 设计了一门只有 8 个有效字符的语言。它与图灵机高度对应：一条整数数组充当纸带（初值全 0）、一个数据指针充当读写头、[ ] 是唯一的控制流，其余字符均视为注释。仅凭这些，它就是完整的图灵完备语言，任何可计算的任务它都能完成，尽管编写相当繁琐。

图 3-1 · 指针在数组上移动、当前指令高亮、字符逐个输出到终端。重点看第一个例子 +++++[>+++++++++++++<-]>.——它没有乘法指令，却用外层循环 5 次、每次给相邻格加 13 算出 65，而 65 正是字符 A 的 ASCII 码，末尾的 >. 将其输出。

更复杂的计算只是把「加法、循环、搬运」组合得更细。这正是图灵完备的直觉：有了无限的存储格、能加减、能按格子是否为 0 进行循环，就已足够。

把 Brainfuck 与图灵机逐项对上，图灵完备这件事就不再抽象：数据数组对应纸带，+ 与 - 对应在当前格擦写，> 与 < 对应读写头左右移，[ ] 对应「判断当前格是否为 0」来决定下一 state，也就是指令表里的条件转移。能模拟图灵机，即图灵完备；反向同样成立，可以用图灵机模拟任意 Brainfuck 程序。

警示 · 图灵完备不等于易用。Brainfuck 能完成任意计算，但实现一个「打印 Hello World」就需要上百个字符。图灵完备只关心能否计算，不关心编写是否方便、运行是否高效。这也是存在上千种编程语言的原因——它们算力相同，区别在于表达力、安全、性能、生态这些图灵完备之外的维度。

4 · Rule 110：涂格子的通用计算

把一排格子（细胞）排成一行，每个非黑 (1) 即白 (0)。下一代怎么算？每个细胞只看自己和左右两个邻居这 3 格，凑成一个 3-bit 的小图案（共 $2^3 = 8$ 种），查一张只有 8 条的规则表，决定自己下一代是黑是白。没有内存、没有变量、没有循环、没有指令，简单得就像在格子上涂色。

一张 8 条的规则表本身就是个 8-bit 数，所以一共只有 $2^8 = 256$ 条基本规则，编号 0 到 255。其中编号 110 的这一条，经 Stephen Wolfram 猜想、Matthew Cook 证明（结果于 2004 年正式发表）确为图灵完备：理论上能模拟任意计算。一个涂格子游戏，其计算能力等同于一台通用计算机。

图 4-1 · 规则表的 8 个小盒里，上面 3 格是「左·中·右」邻居图案，下面 1 格是该细胞下一代的颜色。可点画布顶行涂出起始细胞再逐代演化；默认的「单个细胞居中」种子会生成会移动、会碰撞的斜纹结构，计算就蕴含在这些碰撞之中。拖动规则号还能对比 30（混沌）、90（Sierpinski 分形）、184（车流模型）。

这一结论真正的价值在于把图灵完备的门槛降到了极低：不需要 CPU、不需要编程语言，只要一条极简的局部规则反复作用在一排格子上，就能涌现出通用计算。这也是 Wolfram 计算等价原理的代表例证——自然界中大量看似简单的系统（反应扩散、贝壳花纹、神经元）可能都蕴含这种计算能力。

图灵完备是关于能力上限的论断，不是关于可用性的。Rule 110 若真要用来计算 $1+1$ ，需把数据和程序编码成一长串精心设计的背景花纹与滑翔机 (glider)，复杂到不会有人真正用它编程。它证明的是原理上可行，而非实用——这一点与 Brainfuck 相同。

5 · 意外图灵完备与图灵陷阱

前面四节给出一个反直觉的结论：达到图灵完备的门槛极低，8 个字符、一维涂格子都能做到。门槛之低，使得大量并非为编程设计的系统在无意中跨过了这条线，这称为意外图灵完备 (accidental Turing completeness)。

5.1 · 三个要素

图 5-1 · 图灵完备只需要三个要素。可逐个勾选，观察在哪一步跨过这条线。

5.2 · 那些意外图灵完备的系统

表 5-1 · 一批并非为编程设计、却跨过了图灵完备这条线的系统。
系统	本来的用途	为何图灵完备
Conway 生命游戏	二维细胞演化规则	用 glider 滑翔机当信号、glider gun 当时钟，组合出逻辑门与存储，可构造通用计算机
Rule 110	一维涂格子规则	Cook 证明：背景花纹加滑翔机碰撞即可模拟 cyclic tag system（见 Rule 110）
万智牌 MtG	集换式卡牌游戏	特定牌组配合下，对局的强制步骤可编码图灵机；一局棋的胜负可能不可判定
HTML + CSS	网页排版样式	纯 CSS（配 `:checked`、动画与用户点击）能实现 Rule 110，无需任何 JS
x86 `mov` 指令	CPU 里搬运数据	movfuscator 几乎只用 `mov` 就能编译任意 C 程序——寻址即计算
SQL 递归 CTE	查询关系数据库	`WITH RECURSIVE` 提供无界递归加条件，足以模拟通用计算
PowerPoint 动画	做幻灯片	触发器加动画路径可搭出逻辑门，有人用它实现了图灵机
Minecraft 红石	沙盒游戏里的电路方块	红石就是数字逻辑元件，玩家造出过完整的 CPU 与计算机
TeX / sendmail.cf	排版 / 邮件路由配置	宏展开加重写规则带来无界递归，双双意外图灵完备

注 · 表里 mov 那条常被传成「只用一条指令」，实际留了一个尾巴：movfuscator 生成的程序里仍有一条 jmp，用来在末尾跳回开头形成主循环，其余指令确实全是 mov。Dolan 那篇《mov is Turing-complete》讨论的也是这个模型——mov 负责全部计算，跳转只负责让程序不停下来。

意外图灵完备的案例远不止这些——只要无意中提供了「无限存储加分支加无界循环」，就跨过了这条线。

5.3 · 刻意避开图灵完备的设计

这正是停机问题在工程中的体现。图灵完备的代价是无法预先知道一段代码会不会停、要运行多久、是否会失控（Rice 定理：任何非平凡语义性质都不可判定）。在许多场景这是不可接受的风险，于是人们刻意设计能力受限的语言。

智能合约 · gas 机制——以太坊 EVM 图灵完备，但每步收取 gas、超额即回滚，用经济手段为死循环设置上限。比特币 Script 则刻意非图灵完备（无循环），从根本上杜绝。
配置语言 · Dhall / JSON / YAML——配置必须能在有限步内求值完成、不能死循环，所以 JSON 本身不可计算，Dhall 则是刻意非图灵完备（保证 total、必然终止）的可编程配置。
内核里的 eBPF——跑在 Linux 内核里的用户程序，verifier 会拒绝带无界循环的代码，内核绝不能被一段死循环卡死，所以只允许保证终止的子集。
total 函数式语言 · Coq / Agda——证明助手要求每个函数都能终止，否则能「证明」假命题，于是放弃图灵完备，换来每段代码必然停机的铁保证。

这套权衡可以一句话收束：图灵完备提供「能计算一切」的能力，但同时放弃了「预知其行为」的能力。所以良好的工程实践往往是主体逻辑用图灵完备的通用语言编写，而把那些不容失控的部分（配置、过滤器、合约、查询）交给刻意受限的语言。能力与可控性之间，是一项有意识的取舍。

6 · 主线串联

图灵机定义了「可计算」的极限，它能算的就是人类按算法能算的。停机问题划出这个极限的硬边界：有些问题任何机器都算不出。图灵完备表示某套规则的算力达到了图灵机这条上限；而 Brainfuck 与 Rule 110 说明这条上限的门槛极低，仅需 8 个字符、仅需涂格子规则就能达到。因此它在现实中随处可见，要避开反而需要刻意设计。