FRACTRAN
FRACTRAN(フラクトラン)はチューリング完全な難解プログラミング言語で、数学者ジョン・コンウェイによって開発された。この言語で書かれたプログラムは、正の整数nを初期値として持つ正の分数の列である。プログラムは、以下のように整数nを更新することによって実行される。
nfが整数となるようなリスト内の最初の分数fにおいて、nをnfに置換する。
nをかけて整数となるような分数がリスト内になくなるまでこれを繰り返し、停止する。
Conway 1987には、PRIMEGAME(素数ゲーム)と呼ばれる、連続する素数を探索する以下のFRACTRANプログラムがある。
n=2として始め、このFRACTRANプログラムは以下の整数列を生成する。
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (オンライン整数列大辞典の数列 A007542)
2の後、この数列は以下の2の冪乗を含む。
(オンライン整数列大辞典の数列 A034785)
これらの2のべき乗の指数部分は2, 3, 5, ...というような素数である。
以下のFRACTRANプログラム
つまり ( 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の個数を計算する。入力は2で出力13である。このプログラムを解析すると以下のようになる。