最小通用图灵机
universal computation 到底需要多少结构？这是一场持续了数十年的竞赛，目标是压缩通用图灵机的 (states, symbols)（状态数与符号数）。
- Rogozhin（1996）： 给出了一族小型通用机器，包括一个 (4, 6)——4 个状态、6 个符号——以及其他微小的组合（
(2,18)、(3,9)、(5,5)、……）。 - Wolfram 的 (2, 3) 机器： 在《A New Kind of Science》中被猜想为通用机；Alex Smith（2007）证明了它确实是通用的——但用的是一种非标准的输入编码（一条无限、非周期的初始纸带），因此它是否算"真正"通用仍有争议。
教训是：通用性很廉价——它出现在几乎小到做不了什么事的机器里，这也是为什么它如此难以避免（也是为什么如此多的系统会意外地图灵完备）。"通用"与"非通用"之间的边界本身就很微妙——正是在这里，编码约定开始变得重要。