フラクトラン

FRACTRAN は、数学者ジョン・コンウェイによって発明されたチューリング完全な 難解なプログラミング言語です。FRACTRAN プログラムは、最初の正の整数入力nを伴う正の分数の順序付きリストです。プログラムは、次のように整数n を更新することで実行されます。

1. リスト内のnfが整数である最初の分数fについては、 nをnfに置き換える
2. リスト内の分数をn倍したときに整数にならないまでこの規則を繰り返し、その後停止します。

Conway 1987 は、連続する素数を見つける PRIMEGAME と呼ばれる次の FRACTRAN プログラムを提供しています。

$${\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)}$$

このFRACTRANプログラムは、 n =2から始めて、次の整数のシーケンスを生成します。

• 2、15、825、725、1925、2275、425、390、330、290、770、...（OEISの配列A007542）

このシーケンスには、2 の後に次の 2 の累乗が含まれます。

$${\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 }$$（OEISの配列A034785）

これらの 2 の累乗の指数部分は素数、2、3、5 などです。

FRACTRAN プログラムは、レジスタが引数の素指数に格納されるレジスタ マシンの一種として考えることができます。 ${\displaystyle n}$

ゲーデル数を用いると、正の整数は任意の数の任意の大きさの正の整数変数をエンコードすることができる。^{[注 1]各変数の値は、整数の}素因数分解における素数の指数としてエンコードされる。例えば、整数 ${\displaystyle n}$

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

は、1 つの変数 ( と呼ぶ) が値 2 を保持し、他の 2 つの変数 (および) が値 1 を保持するレジスタ状態を表します。他のすべての変数は値 0 を保持します。 ${\displaystyle v_{2}}$${\displaystyle v_{3}}$${\displaystyle v_{5}}$

FRACTRAN プログラムは、正の分数の順序付きリストです。各分数は、分母の素因数で表される 1 つ以上の変数をテストする命令を表します。例:

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

は、と をテストします。 かつ の場合、から 2 を減算し、 から 1 を減算し、 v3 に 1 を加算し、 に 1 を加算します。 例: ${\displaystyle v_{2}}$${\displaystyle v_{5}}$${\displaystyle v_{2}\geq 2}$${\displaystyle v_{5}\geq 1}$${\displaystyle v_{2}}$${\displaystyle v_{5}}$${\displaystyle v_{7}}$

$${\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プログラムは、次のような単一の命令です。

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

このプログラムは、次のような（非常に単純な）アルゴリズムとして表すことができます。

という形式の初期入力が与えられると、このプログラムは、などのシーケンスを計算し、最終的に、ステップ の後に 2 の因数がなくなり、 との積が整数にならなくなるまで計算します。その後、マシンは という最終出力で停止します。つまり、2 つの整数を加算することになります。 ${\displaystyle 2^{a}3^{b}}$${\displaystyle 2^{a-1}3^{b+1}}$${\displaystyle 2^{a-2}3^{b+2}}$${\displaystyle a}$${\displaystyle {\frac {3}{2}}}$${\displaystyle 3^{a+b}}$

「加算器」を「ループ」することで「乗算器」を作成できます。これを行うには、アルゴリズムに状態を​​導入する必要があります。このアルゴリズムは数値を受け取り、次を生成します。 ${\displaystyle 2^{a}3^{b}}$${\displaystyle 5^{ab}}$

状態 B はを加算して に移動するループであり、状態 A は状態 B のループを 回繰り返す外部制御ループです。状態 A は、状態 B のループが完了した後、 の値をから復元します。 ${\displaystyle v_{3}}$${\displaystyle v_{5}}$${\displaystyle v_{3}}$${\displaystyle v_{7}}$${\displaystyle v_{2}}$${\displaystyle v_{3}}$${\displaystyle v_{7}}$

新しい変数を状態インジケータとして使用して状態を実装できます。状態 B の状態インジケータは、およびになります。1 つのループに 2 つの状態制御インジケータ (プライマリ フラグ ( ) とセカンダリ フラグ ( ) ) が必要であることに注意してください。各インジケータはテストされるたびに消費されるため、「現在の状態で続行する」ことを示すセカンダリ インジケータが必要です。このセカンダリ インジケータは次の命令でプライマリ インジケータにスワップバックされ、ループが続行されます。 ${\displaystyle v_{11}}$${\displaystyle v_{13}}$${\displaystyle v_{11}}$${\displaystyle v_{13}}$

乗算アルゴリズム テーブルに FRACTRAN 状態インジケーターと命令を追加すると、次のようになります。

FRACTRAN 命令を書き出すときは、状態 A 命令を最後に置く必要があります。状態 A には状態インジケータがないため、状態 A 命令を最後に置く必要があります。状態インジケータが設定されていない場合は、これがデフォルトの状態になります。したがって、FRACTRAN プログラムでは、乗数は次のようになります。

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

^{入力2 a} 3 ^bに対してこのプログラムは出力5 ^abを生成します。^{[注 2]}

同様の方法で、FRACTRAN「減算器」を作成し、減算を繰り返すことで、次のように「商と余り」アルゴリズムを作成できます。

FRACTRAN プログラムを書き出すと、次のようになります。

$${\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)}$$

入力2 ⁿ 3 ^d 11は出力5 ^q 7 ^rを生成します。ここでn = qd + rかつ0 ≤ r < dです。

上記の Conway の素数生成アルゴリズムは、本質的には 2 つのループ内の商と剰余のアルゴリズムです。0 ≤ m < nの形式の入力が与えられると、アルゴリズムはn +1 をnから1 までの各数値で割り、 n +1の約数となる最大の数値k を見つけます。次に、2 ^{n +1} 7 ^{k -1 を}返して繰り返します。アルゴリズムによって生成される状態数のシーケンスが 2 の累乗を生成するのは、kが 1 のとき (つまり 7 の指数が 0 のとき) のみで、これは 2 の指数が素数である場合にのみ発生します。Conway のアルゴリズムのステップごとの説明は、Havil (2007) に記載されています。 ${\displaystyle 2^{n}7^{m}}$

このプログラムでは、素数 2、3、5、7... に到達するには、それぞれ 19、69、281、710、... のステップが必要です ( OEISのシーケンスA007547 )。

コンウェイのプログラムの変種も存在し、^[1]これは上記のバージョンとは2つの点で異なります。 $${\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... ステップかかります ( OEISのシーケンスA007546 )。このプログラムを 1 回繰り返して、特定の数N が素数であるかどうかをチェックすると、次のステップ数がかかります。 ここで、はNの最大の整数約数で、は床関数です。^[2]$${\displaystyle N-1+(6N+2)(N-b)+2\sum \limits _{d=b}^{N-1}\left\lfloor {\frac {N}{d}}\right\rfloor ,}$$${\displaystyle b<N}$${\displaystyle \lfloor x\rfloor }$

1999年、デヴィン・キルミンスターはより短い10命令のプログラムを実証しました。^[3] 初期入力n = 10に対して、連続する素数は10の累乗によって生成されます。 $${\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).}$$

次の FRACTRAN プログラム:

$${\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)}$$

aの2進展開のハミング重みH( a )、つまりaの2進展開における1の数を計算します。^[4]入力2aに対して^、出力は13H ^{( a )}です。プログラムは次のように分析できます。

• 1命令セットコンピュータ
• コラッツ予想

ウィキメディア・コモンズには、 Fractran (プログラミング言語)に関連するメディアがあります。

• ジョン・コンウェイの講演：「Fractran: ばかげた論理言語」
• 「素数病理学：フラクトラン」
• Weisstein、Eric W.「FRACTRAN」。MathWorld。
• 素数病理学
• FRACTRAN - (エソラン ウィキ)
• Rubyの実装とサンプルプログラム
• プロジェクトオイラー問題308
• 「Fractran で Fizzbuzz をゼロから構築する」
• Chris Lomont、「FRACTRAN のユニバーサル FRACTRAN インタープリタ」