数学家 John Conway 发明的 FRACTRAN 语言被证实为图灵完备

FRACTRAN 是数学家 John Conway 发明的一种图灵完备的深奥编程语言。一个 FRACTRAN 程序是一个由正分数组成的有序列表，再加上一个初始的正整数输入 n。程序的运行方式是按如下规则更新整数 n：

Conway 1987 给出了下面这个 FRACTRAN 程序，称为 PRIMEGAME，它能依次找出素数： ( 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1 )

从 n=2 开始，这个 FRACTRAN 程序生成下面这个整数序列：

在 2 之后，这个序列包含下面这些 2 的幂： 2^2 = 4, 2^3 = 8, 2^5 = 32, 2^7 = 128, 2^11 = 2048, 2^13 = 8192, 2^17 = 131072, 2^19 = 524288, … （OEIS 中的序列 A034785）

这些 2 的幂的指数部分都是素数：2、3、5 等。

一个 FRACTRAN 程序可以看作一种寄存器机，其中寄存器以自变量 n 的素数指数形式存储。

利用哥德尔编号，一个正整数 n 可以编码任意数量的、任意大的正整数变量。[注 1] 每个变量的值被编码为该整数素因数分解中某个素数的指数。例如，整数 60 = 2^2 × 3^1 × 5^1 表示一个寄存器状态，其中一个变量（我们称之为 v_2）的值为 2，另外两个变量（v_3 和 v_5）的值为 1。所有其他变量的值均为 0。

一个 FRACTRAN 程序是一个由正分数组成的有序列表。每个分数代表一条指令，它测试一个或多个变量，这些变量由其分母的素因子表示。例如： f_1 = 21/20 = (3 × 7)/(2^2 × 5^1) 测试 v_2 和 v_5。如果 v_2 ≥ 2 且 v_5 ≥ 1，那么它从 v_2 中减去 2、从 v_5 中减去 1，并向 v_3 加 1、向 v_7 加 1。例如： 60 · f_1 = 2^2 × 3^1 × 5^1 · (3 × 7)/(2^2 × 5^1) = 3^2 × 7^1

由于 FRACTRAN 程序只是一个分数列表，这些“测试—递减—递增”指令就是 FRACTRAN 语言中唯一允许的指令。此外还适用以下限制：

最简单的 FRACTRAN 程序是像下面这样的一条指令： (3/2)

这个程序可以用如下（非常简单的）算法表示：

给定形如 2^a 3^b 的初始输入，这个程序将依次计算 2^(a−1) 3^(b+1)、2^(a−2) 3^(b+2) 等，直到最终经过 a 步之后，不再剩下因子 2，且与 3/2 的乘积不再得到整数；此时程序停止，最终输出为 3^(a+b)。因此它把两个整数相加。

我们可以通过“循环”执行这个“加法器”来创建一个“乘法器”。为此，我们需要在算法中引入状态。这个算法将接收一个数 2^a 3^b，并产生 5^(ab)。

状态 B 是一个循环，它把 v_3 加到 v_5 上，同时把 v_3 移到 v_7；状态 A 是一个外层控制循环，它把状态 B 中的循环重复 v_2 次。状态 A 还会在状态 B 的循环完成后，从 v_7 恢复 v_3 的值。

我们可以用新的变量作为状态指示符来实现状态。状态 B 的状态指示符将是 v_11 和 v_13。注意，一个循环需要两个状态控制指示符：一个主标志（v_11）和一个辅助标志（v_13）。因为每个指示符在被测试时都会被消耗掉，所以我们需要一个辅助指示符来表示“继续处于当前状态”；这个辅助指示符在下一条指令中会被换回主指示符，循环便继续下去。

把 FRACTRAN 的状态指示符和指令加入乘法算法表中，我们得到：

当我们写出 FRACTRAN 指令时，必须把状态 A 的指令放在最后，因为状态 A 没有状态指示符——如果没有设置任何状态指示符，它就是默认状态。因此，作为 FRACTRAN 程序，这个乘法器变为： (455/33, 11/13, 1/11, 3/7, 11/2, 1/3)

输入 2a3b 时，这个程序产生输出 5ab。[注 2]

以类似的方式，我们可以创建一个 FRACTRAN“减法器”，而重复减法又允许我们创建如下“商与余数”算法：

写出 FRACTRAN 程序，我们得到： (91/66, 11/13, 1/33, 85/11, 57/119, 17/19, 11/17, 1/3)

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）