FRACTRAN

FRACTRAN（フラクトラン）はチューリング完全な難解プログラミング言語で、数学者ジョン・コンウェイによって開発された。この言語で書かれたプログラムは、正の整数nを初期値として持つ正の分数の列である。プログラムは、以下のように整数nを更新することによって実行される。 nfが整数となるようなリスト内の最初の分数fにおいて、nをnfに置換する。 nをかけて整数となるような分数がリスト内になくなるまでこれを繰り返し、停止する。 Conway 1987には、PRIMEGAME（素数ゲーム）と呼ばれる、連続する素数を探索する以下のFRACTRANプログラムがある。 ( 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 ) {\displaystyle \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 , … {\displaystyle 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プログラムはレジスタが引数nの素数指数として格納されるレジスタマシンとして見ることができる。 ゲーデル数を用いて、正の整数nは任意の数の任意の大きさの正の整数の変数を符号化することができる。 各変数の値は、整数の素因数分解によって素数のべき乗に符号化される。例えば、整数 60 = 2 2 × 3 1 × 5 1 {\displaystyle 60=2^{2}\times 3^{1}\times 5^{1}} は、レジスタの状態が以下のようになっていることを表す。 ある変数（これをv2とする）の値が2である。 ほかの変数の2つ（これをv3とv5とする）の値が1である。 ほかの全ての変数の値が0である。 FRACTRANプログラムは、正の分数の列である。すべての分数はそれぞれ、1つ以上の変数をテストする命令を表し、それはその分母の素因数によって表される。例えば、 f 1 = 21 20 = 3 × 7 2 2 × 5 1 {\displaystyle f_{1}={\frac {21}{20}}={\frac {3\times 7}{2^{2}\times 5^{1}}}} はv2とv5を評価する。 v 2 ≥ 2 {\displaystyle v_{2}\geq 2} かつ v 5 ≥ 1 {\displaystyle v_{5}\geq 1} のとき、v2から2を、v5から1をそれぞれ引き、v3に1を、v7に1を加える。以下に例を挙げる。 60 ⋅ f 1 = 2 2 × 3 1 × 5 1 ⋅ 3 × 7 2 2 × 5 1 = 3 2 × 7 1 {\displaystyle 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つの命令である。 ( 3 2 ) {\displaystyle \left({\frac {3}{2}}\right)} このプログラムは以下の単純なアルゴリズムに表される。 2 a 3 b {\displaystyle 2^{a}3^{b}} の形で与えられた初期値に対し、このプログラムは以下の数列を計算する。 2 a − 1 3 b + 1 {\displaystyle 2^{a-1}3^{b+1}} , 2 a − 2 3 b + 2 {\displaystyle 2^{a-2}3^{b+2}} , … これを a {\displaystyle a} ステップ行い、最終的に2で割り切れなくなり、 3 2 {\displaystyle {\frac {3}{2}}} をかけても整数とならなくなったとき、レジスタマシンは 3 a + b {\displaystyle 3^{a+b}} を出力して停止する。これにより、2つの整数が加算される。 「乗算器」は、「加算器」を「ループする」ことで作ることができる。これには、アルゴリズムにState（オブジェクト指向プログラミングにおけるデザインパターンの1つ）を導入する必要がある。このアルゴリズムは 2 a 3 b {\displaystyle 2^{a}3^{b}} を引数に取り、 5 a b {\displaystyle 5^{ab}} を生成する。 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命令を書き出すとき、最後にAのStateの命令が必要になる。AのStateにはインジケータがないからである。Stateインジケータが設定されていないのが既定のStateである。ゆえに、乗算器のFRACTRANプログラムは以下のようになる。 ( 455 33 , 11 13 , 1 11 , 3 7 , 11 2 , 1 3 ) {\displaystyle \left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)} 入力2a3bに対してこのプログラムは5abを出力する。 同様に、FRACTRAN「減算器」を作ることができる。さらに、減算を繰り返すことで、以下の「商とあまり」のアルゴリズムを作ることもできる。 FRACTRANプログラムに書き出すと、以下のようになる。 ( 91 66 , 11 13 , 1 33 , 85 11 , 57 119 , 17 19 , 11 17 , 1 3 ) {\displaystyle \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)} 入力2n3d11に対して、このプログラムは5q7rを出力する。ここに、n = qd + r かつ 0 ≤ r < dである。 コンウェイの素数生成アルゴリズム（前述）は本質的に、２つのループ内の商とあまりのアルゴリズムである。 2 n 7 m {\displaystyle 2^{n}7^{m}} （ただし0 ≤ m < n）の形で与えられた入力に対し、アルゴリズムはn+1の最大の約数kを見つけるまでn+1をnから1までの整数でそれぞれ割ろうとする。そして2n+1 7k-1を返し、繰り返す。このアルゴリズムで生成されるStateの番号の列はkが1のとき2のべき乗を生成する（7の指数は0になる）のは、2の指数が素数のときのみである。Havil (2007)に、コンウェイのアルゴリズムの段階的な説明がある。 このプログラムにおいて、素数2, 3, 5, 7 ... を得るには、それぞれ19, 69, 281, 710, ...のステップが必要となる。（オンライン整数列大辞典の数列 A007547） コンウェイのプログラムには前述のものより分数が2つ異なる版も存在する。 ( 17 91 , 78 85 , 19 51 , 23 38 , 29 33 , 77 29 , 95 23 , 77 19 , 1 17 , 11 13 , 13 11 , 15 14 , 15 2 , 55 1 ) {\displaystyle \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 + ( 6 N + 2 ) ( N − b ) + 2 ∑ d = b N − 1 ⌊ N d ⌋ {\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor } このとき、 b < N {\displaystyle b<N} は最大のNの整数の約数であり、 ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } は床関数である。 以下は、1999年の、Devin Kilminsterによる、これより少し短い、10の命令からなるプログラムである。 ( 7 3 , 99 98 , 13 49 , 39 35 , 36 91 , 10 143 , 49 13 , 7 11 , 1 2 , 91 1 ) {\displaystyle \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プログラム ( 3 ⋅ 11 2 2 ⋅ 5 , 5 11 , 13 2 ⋅ 5 , 1 5 , 2 3 , 2 ⋅ 5 7 , 7 2 ) {\displaystyle \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)} つまり ( 20 33 , 5 11 , 13 10 , 1 5 , 2 3 , 10 7 , 7 2 ) {\displaystyle \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の個数を計算する。入力は2aで出力13H(a)である。このプログラムを解析すると以下のようになる。