著名的图灵机

上级：turing-machines

除了busy-beaver之外，还有一些值得认识的机器，每个子节点一台。

这些机器

• busy-beaver — 一台可停机的 n 状态机器所能运行的最大步数；本身不可计算；文中附有手工推演出的 S(1)/S(2) 冠军记录。
• smallest-universal-tm — 一台通用机器能小到什么程度（Rogozhin 的 (4,6)、Wolfram 的 (2,3)）。
• langtons-ant — 一台只有 2 条规则的二维机器：先是一片混沌，随后涌现出一条"高速公路"；具有图灵完备性。
• rule-110 — 一个被证明具有通用性（Cook）的一维元胞自动机；通用性很廉价。
• foundational-machines — 显式构造的机器：分别在 ZFC 不一致 / 哥德巴赫猜想为假 / 黎曼猜想为假时停机（Yedidia–Aaronson）——因此 BB(748) 独立于 ZFC。