FRACTRAN

ウィキペディア

FRACTRAN

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/02/25 19:03 UTC 版)

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

1. nfが整数となるようなリスト内の最初の分数fにおいて、nをnfに置換する。
2. 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)$$

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