turing machine · halting · brainfuck · rule 110

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

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

本系列从机器本身出发，逐步走到它的能力边界与各种意外的实现形式： $图灵机 \to 停机问题 \to Brainfuck \to Rule 110 \to 图灵陷阱$ 。每节都能修改输入、单步执行，观察纸带推进、内存格亮灭、细胞演化——把抽象的「可计算」转化为能逐格观察的过程。本系列会用到有限状态机 (DFA) 作对比，可参考 automata 系列。四节：图灵机 → 停机问题 → Brainfuck → Rule 110 → 应用实例。

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

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

选一台机器、修改输入，点「下一步」：读写头读当前格，在右侧指令表里找到对应规则（高亮），执行擦写、移动、切换 state。如此循环，直到进入停机 state。它没有加减乘、没有变量，却能完成任意可计算的任务。二进制 +1 演示进位如何沿纸带逐格左传，回文判定则展示了 DFA 无法完成的任务（DFA 需要记住任意长的前半段），而图灵机靠来回擦写纸带即可实现。

这就是「可计算」的定义。图灵证明了一个重要结论：凡是人类能按某套明确步骤算出来的问题，这台机器都能算（反之亦然），这就是 Church–Turing thesis。于是「可计算」不再是模糊的直觉，而有了精确含义：能被某台图灵机算出来。Brainfuck 与 Rule 110 两节会说明，达到这条上限所需的工具极其简单。

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

2 · 停机问题：连图灵机都算不出的问题

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

为什么不能「直接运行一遍观察」？因为如果它确实会死循环，就永远等不到「它不会停」的结论——只能一直等下去。下面的工具让你扮演判定器：设定一个步数预算 B，运行 B 步。可以看到：程序在预算内停下时能下结论，但一旦跑满 B 步仍在运行，就无法做出任何判断。

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

2.1 · 为什么不可能？——对角线反证

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

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

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

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

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

选择一个程序、点「下一步」，观察指针在数组上移动、当前指令高亮、字符逐个输出到终端。重点看第一个例子 +++++[>+++++++++++++<-]>.：它没有乘法指令，却用「外层循环 5 次、每次给相邻格加 13」计算出 5×13 = 65，而 65 正是 'A' 的 ASCII 码——>. 将其输出。更复杂的计算只是把这种「加法 + 循环 + 搬运」组合得更细。这正是图灵完备的直觉：有了无限的存储格、能加减、能按格子是否为 0 进行循环，就已足够。

它与图灵机几乎一一对应：数据数组 ↔ 纸带，+ - ↔ 在当前格擦写，> < ↔ 读写头左右移，[ ] ↔「判断当前格是否为 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 年严格证明：它图灵完备——理论上能模拟任意计算。一个「涂格子」游戏，其计算能力等同于一台通用计算机。

下面是 Rule 110 的规则表（8 个小盒：上面 3 格是「左·中·右」邻居图案，下面 1 格是该细胞下一代的颜色）。点画布顶行涂出起始细胞，再点「下一步」逐代演化。默认的「单个细胞居中」种子即可验证：可以看到它既不是一片静止、也不是纯随机噪声，而是在秩序与混沌的边缘生成会移动、会碰撞的斜纹结构——计算就蕴含在这些碰撞之中。拖动「规则号」还能对比 30（混沌）、90（Sierpinski 分形）、184（车流模型）。

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

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

5 · 应用实例：意外图灵完备 & 图灵陷阱

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

5.1 · 先动手：你的系统图灵完备吗？

图灵完备只需要具备三个要素。逐个勾选，观察何时跨过这条线：

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

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

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

5.3 · 反向：为什么有人刻意避开图灵完备？

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

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

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

5.4 · 回到起点

图灵机定义了可计算的极限，停机问题划出它的硬边界，图灵完备说明这条上限的门槛极低、因而在现实中随处可见。下次遇到一个「只是配置 / 只是模板 / 只是游戏」的小系统，不妨多想一步：它是否在无意中，已经具备了与通用计算机等同的算力？

6 · 主线串联

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