FRACTRAN

FRACTRAN（フラクトラン）はチューリング完全な難解プログラミング言語で、数学者ジョン・コンウェイによって開発された。この言語で書かれたプログラムは、正の整数nを初期値として持つ正の分数の列である。プログラムは、以下のように整数nを更新することによって実行される。

nfが整数となるようなリスト内の最初の分数fにおいて、nをnfに置換する。
nをかけて整数となるような分数がリスト内になくなるまでこれを繰り返し、停止する。

Conway 1987には、PRIMEGAME（素数ゲーム）と呼ばれる、連続する素数を探索する以下のFRACTRANプログラムがある。

\left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}\right)

n=2として始め、このFRACTRANプログラムは以下の整数列を生成する。

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... （オンライン整数列大辞典の数列 A007542）

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,\,\dots

（オンライン整数列大辞典の数列 A034785）

これらの2のべき乗の指数部分は2, 3, 5, …というような素数である。

FRACTRANプログラムを理解する

FRACTRANプログラムはレジスタが引数nの素数指数として格納されるレジスタマシンとして見ることができる。

ゲーデル数を用いて、正の整数nは任意の数の任意の大きさの正の整数の変数を符号化することができる。^{[注釈 1]} 各変数の値は、整数の素因数分解によって素数のべき乗に符号化される。例えば、整数

60=2^{2}\times 3^{1}\times 5^{1}

は、レジスタの状態が以下のようになっていることを表す。

ある変数（これをv2とする）の値が2である。
ほかの変数の2つ（これをv3とv5とする）の値が1である。
ほかの全ての変数の値が0である。

FRACTRANプログラムは、正の分数の列である。すべての分数はそれぞれ、1つ以上の変数をテストする命令を表し、それはその分母の素因数によって表される。例えば、

f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}

はv2とv5を評価する。

v_{2}\geq 2

かつ

v_{5}\geq 1

のとき、v2から2を、v5から1をそれぞれ引き、v3に1を、v7に1を加える。以下に例を挙げる。

60\cdot f_{1}=2^{2}\times 3^{1}\times 5^{1}\cdot {\frac {3\times 7}{2^{2}\times 5^{1}}}=3^{2}\times 7^{1}

FRACTRANプログラムは分数のリストに過ぎず、これらの評価・演算命令（加算・減算命令）はFRACTRAN言語において唯一許された命令である。さらに、以下の制約が適用される。

命令が実行されるごとに、評価される変数はデクリメント（減算）される。
同じ変数に対して、1つの命令でインクリメント（加算）とデクリメント（減算）を両方することはできない。（そうでなければ、その命令を表す分数が既約分数にならない。）したがって、すべてのFRACTRANの命令は変数の評価においてその変数を消費する。
FRACTRANの命令は、変数が0かどうかを直接評価することはできない。（しかし、既定の命令を作成して、それを特定の変数を評価する別の命令の後に配置することで、間接的な評価は可能である。）

簡単なプログラムの作成

加算

最も単純なFRACTRANプログラムは以下の1つの命令である。

\left({\frac {3}{2}}\right)

このプログラムは以下の単純なアルゴリズムに表される。

FRACTRAN 命令	条件	アクション
${\frac {3}{2}}$	v2 > 0	v2から1を引き、v3に1を加える
	v2 = 0	停止する

$2^{a}3^{b}$ の形で与えられた初期値に対し、このプログラムは以下の数列を計算する。

$2^{a-1}3^{b+1}$ , $2^{a-2}3^{b+2}$ , …

これを $a$ ステップ行い、最終的に2で割り切れなくなり、 ${\frac {3}{2}}$ をかけても整数とならなくなったとき、レジスタマシンは $3^{a+b}$ を出力して停止する。これにより、2つの整数が加算される。

乗算

「乗算器」は、「加算器」を「ループする」ことで作ることができる。これには、アルゴリズムにState（オブジェクト指向プログラミングにおけるデザインパターンの1つ）を導入する必要がある。このアルゴリズムは $2^{a}3^{b}$ を引数に取り、 $5^{ab}$ を生成する。

State	条件	アクション	次のState
A	v7 > 0	v7から1を引き、v3に1を加える	A
	v7 = 0 かつ v2 > 0	v2から1を引く	B
	v7 = 0 かつ v2 = 0 かつ v3 > 0	v3から1を引く	A
	v7 = 0 かつ v2 = 0 かつ v3 = 0	停止する
B	v3 > 0	v3から1を引き、v5とv7にそれぞれ1を加える	B
B	v3 = 0	なし	A

BのStateはv3とv5を加算しv3をv7に値を移すループである。また、AのStateは、BのStateをv2回繰り返す外側の制御ループである。AのStateはまた、BのStateのループが完了した後、v7からv3に値を移す（つまり、v3から一度v7に移動して、またv3に戻る）。

新しい変数をStateインジケータとして用いることで、Stateを実行することができる。B用のStateインジケータはv11とv13である。ここで、1つのループにState制御インジケータは第一のフラグ（v11）と第二のフラグ（v13）の2つが必要となることに留意されたい。なぜなら、それぞれのインジケータは評価されると消費されるため、「現在のStateを継続せよ」と言うために第二のインジケータが必要となるからである。この第二のインジケータは、次の命令で第一のインジケータに還元され、ループが継続する。

乗算アルゴリズムの表にFRACTRAN Stateインジケータと命令を追加すると以下のようになる。

FRACTRAN 命令	State	State インジケータ	条件	アクション	次のState
${\frac {3}{7}}$	A	なし	v7 > 0	v7から1を引き、v3に1を加える	A
${\frac {11}{2}}$			v7 = 0 かつ v2 > 0	v2から1を引く	B
${\frac {1}{3}}$			v7 = 0 かつv2 = 0 かつv3 > 0	v3から1を引く	A
			v7 = 0 かつv2 = 0 かつ v3 = 0	停止する
${\frac {5\cdot 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}$	B	v11, v13	v3 > 0	v3から1を引き、v5とv7にそれぞれ1を加える	B
${\frac {1}{11}}$	B	v11, v13	v3 = 0	なし	A

FRACTRAN命令を書き出すとき、最後にAのStateの命令が必要になる。AのStateにはインジケータがないからである。Stateインジケータが設定されていないのが既定のStateである。ゆえに、乗算器のFRACTRANプログラムは以下のようになる。

\left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)

入力2^a3^bに対してこのプログラムは5^abを出力する。 ^{[注釈 2]}

上記のFRACTRANプログラムで3×2を計算する（3×2は6であるから、入力は $2^{3}\times 3^{2}=72$ で、出力は $5^{6}=15625$ となる）

{\displaystyle 2^{3}\times 3^{2}=72} — 上記のFRACTRANプログラムで3×2を計算する（3×2は6であるから、入力は $2^{3}\times 3^{2}=72$ で、出力は $5^{6}=15625$ となる）

減算と除算

同様に、FRACTRAN「減算器」を作ることができる。さらに、減算を繰り返すことで、以下の「商とあまり」のアルゴリズムを作ることもできる。

FRACTRAN 命令	State	State インジケータ	条件	アクション	次のState
${\frac {7\cdot 13}{2\cdot 3\cdot 11}},{\frac {11}{13}}$	A	v11, v13	v2 > 0 かつ v3 > 0	v2とv3からそれぞれ1を引き、v7に1を加える	A
${\frac {1}{3\cdot 11}}$			v2 = 0 かつ v3 > 0	v3から1を引く	X
${\frac {5\cdot 17}{11}}$			v3 = 0	v5に1を加える	B
${\frac {3\cdot 19}{7\cdot 17}},{\frac {17}{19}}$	B	v17, v19	v7 > 0	v7から1を引き、v3に1を加える	B
${\frac {11}{17}}$	B	v17, v19	v7 = 0	なし	A
${\frac {1}{3}}$	X		v3 > 0	v3から1を引く	X
	X		v3 = 0	停止する

FRACTRANプログラムに書き出すと、以下のようになる。

\left({\frac {91}{66}},{\frac {11}{13}},{\frac {1}{33}},{\frac {85}{11}},{\frac {57}{119}},{\frac {17}{19}},{\frac {11}{17}},{\frac {1}{3}}\right)

入力2ⁿ3^d11に対して、このプログラムは5^q7^rを出力する。ここに、n = qd + r かつ 0 ≤ r < dである。

コンウェイの素数アルゴリズム

コンウェイの素数生成アルゴリズム（前述）は本質的に、２つのループ内の商とあまりのアルゴリズムである。 $2^{n}7^{m}$ （ただし0 ≤ m < n）の形で与えられた入力に対し、アルゴリズムはn+1の最大の約数kを見つけるまでn+1をnから1までの整数でそれぞれ割ろうとする。そして2ⁿ⁺¹ 7^k-1を返し、繰り返す。このアルゴリズムで生成されるStateの番号の列はkが1のとき2のべき乗を生成する（7の指数は0になる）のは、2の指数が素数のときのみである。Havil (2007)に、コンウェイのアルゴリズムの段階的な説明がある。

このプログラムにおいて、素数2, 3, 5, 7 ... を得るには、それぞれ19, 69, 281, 710, ...のステップが必要となる。（オンライン整数列大辞典の数列 A007547）

コンウェイのプログラムには前述のものより分数が2つ異なる版も存在する。^[1]

\left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{14}},{\frac {15}{2}},{\frac {55}{1}}\right)

こちらの方が少し速い。2, 3, 5, 7... を得るのには19, 69, 280, 707... のステップが必要である。（オンライン整数列大辞典の数列 A007546）このプログラムの特定の整数Nが素数であるか調べる反復には、以下の数のステップが必要である。

N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor

このとき、

b<N

は最大のNの整数の約数であり、

\lfloor x\rfloor

は床関数である。^[2]

以下は、1999年の、Devin Kilminsterによる、これより少し短い、10の命令からなるプログラムである。^[3]

\left({\frac {7}{3}},{\frac {99}{98}},{\frac {13}{49}},{\frac {39}{35}},{\frac {36}{91}},{\frac {10}{143}},{\frac {49}{13}},{\frac {7}{11}},{\frac {1}{2}},{\frac {91}{1}}\right)

初期値n = 10において、連続した素数が後続する10のべき乗によって生成される。

他の例

以下のFRACTRANプログラム

\left({\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}},{\frac {13}{2\cdot 5}},{\frac {1}{5}},{\frac {2}{3}},{\frac {2\cdot 5}{7}},{\frac {7}{2}}\right)

つまり

\left({\frac {20}{33}},{\frac {5}{11}},{\frac {13}{10}},{\frac {1}{5}},{\frac {2}{3}},{\frac {10}{7}},{\frac {7}{2}}\right)

は、2進記数法におけるaのハミング重み H(a)、すなわちaの2進数表記における1の個数を計算する。入力は2^aで出力13^H(a)である。^[4]このプログラムを解析すると以下のようになる。

FRACTRAN 命令	State	State インジケータ	条件	アクション	次のState
${\frac {3\cdot 11}{2^{2}\cdot 5}},{\frac {5}{11}}$	A	v5, v11	v2 > 1	v2から2を引き、v3に1を加える	A
${\frac {13}{2\cdot 5}}$			v2 = 1	v2から1を引き、v13に1を加える	B
${\frac {1}{5}}$			v2 = 0	なし	B
${\frac {2}{3}}$	B	None	v3 > 0	v3から1を引き、v2に1を加える	B
${\frac {2\cdot 5}{7}}$			v3 = 0 かつ v7 > 0	v7から1を引き、v2に1を加える	A
${\frac {7}{2}}$			v3 = 0 かつ v7 = 0 かつ v2 > 0	v2から1を引き、v7に1を加える	B
			v2 = 0 かつ v3 = 0 かつ v7 = 0	停止する

注釈

^ Gödel numbering ゲーデル数は、慣例が適用して、直接負の整数、浮動小数点数や文字列を間接的に表すようにすることはできるが、直接的に使用することはできない。FRACTRANに提案されている拡張機能にはFRACTRAN++（Written in English）及びBag（Written in English）などがある。
^ Esolang FRACTRAN page（Written in English）に類似した乗算器のアルゴリズムの説明がある。

参考資料

^ Guy 1983, p. 26; Conway & Guy 1996, p. 147
^ Guy 1983, p. 33
^ Havil 2007, p. 176
^ John Baez, Puzzle #4, The n-Category Café

Guy, Richard K. (1983). “Conway's Prime Producing Machine”. Mathematics Magazine (Taylor & Francis) 56 (1): 26–33. doi:10.1080/0025570X.1983.11977011. https://www.tandfonline.com/doi/abs/10.1080/0025570X.1983.11977011.
Conway, John H. (1987). “FRACTRAN: A simple universal programming language for arithmetic”. Open Problems in Communication and Computation (Springer-Verlag New York, Inc.): 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6.
Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc.. ISBN 0-387-97993-X. https://archive.org/details/bookofnumbers0000conw
Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0. https://archive.org/details/nonplussedmathem00havi
Roberts, Siobhan (2015). “Criteria of virtue”. Genius At Play - The Curious Mind of John Horton Conway. Bloomsbury. pp. 115–119. ISBN 978-1-62040-593-2