FRACTRAN

FRACTRAN：分数を用いたチューリング完全言語

FRACTRANは、数学者ジョン・コンウェイによって考案された、チューリング完全な難解プログラミング言語です。この言語のプログラムは、正の分数のリストで表現されます。プログラムの実行は、初期値として与えられた正の整数に対して、リスト中の分数を順次適用することで行われます。

具体的には、現在の整数値 n に対して、リストの先頭から分数を順番に調べ、n に分数を掛けた結果が整数になる最初の分数 f を探します。見つかった場合、n の値を nf に置き換え、この操作を整数になる分数が見つからなくなるまで繰り返します。この繰り返し処理がプログラムの実行です。

素数ゲーム：コンウェイによるFRACTRANプログラム

コンウェイは、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) \)

初期値を2とすると、このプログラムは2のべき乗の指数部分が素数となる数列を生成します。この数列は、2, 15, 825, 725, 1925, 2275, 425,...といった値をとり、その中には2², 2³, 2⁵, 2⁷, ...といった2のべき乗が含まれ、べき乗の指数は2, 3, 5, 7,...と素数を順に辿ります。

FRACTRANプログラムの動作原理：レジスタマシン

FRACTRANプログラムは、レジスタマシンとして解釈することができます。正の整数 n は、その素因数分解によってレジスタの状態を表します。例えば、60 = 2² × 3¹ × 5¹ は、変数v2の値が2、v3とv5の値が1、それ以外の変数の値が0である状態に対応します。

プログラム中の各分数（例えば、\( f_1 = \frac{21}{20} = \frac{3 \times 7}{2^2 \times 5} \) ）は、レジスタマシンにおける命令に対応します。この分数は、変数v2とv5の値をチェックし、v2 ≥ 2 かつ v5 ≥ 1 ならば、v2から2、v5から1を引いて、v3とv7に1ずつ加えます。

FRACTRANでは、変数の値を直接チェックすることはできませんが、他の命令と組み合わせることで間接的にチェックできます。また、各命令は変数の値を消費する（減算する）点が特徴です。

簡単なFRACTRANプログラムの例

加算

最も単純なFRACTRANプログラムは、\( (\frac{3}{2}) \) という単一の分数からなるプログラムです。これは、2^a3^bという形式の入力に対して、2^a-13^b+1, 2^a-23^b+2,...と計算し、最終的に3^a+bを出力して停止します。これは、aとbの加算を実行していることになります。

乗算

乗算は、加算をループさせることで実現できます。この際、状態（ステート）の概念を導入する必要があります。例えば、2^a3^bを入力として5^abを出力する乗算器では、加算をa回繰り返す外側のループと、加算を実行する内側のループの2つの状態を管理する必要があります。FRACTRANでは、新たな変数を状態を表すインジケータとして用いることで、状態遷移を実現できます。

減算と除算

減算も、FRACTRANで実現可能です。減算を繰り返すことで、除算（商と余り）のアルゴリズムも構築できます。

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

コンウェイの素数生成アルゴリズムは、本質的に商と余りのアルゴリズムを2つのループで実行することで、素数を生成します。このアルゴリズムでは、2ⁿ7^m（ただし0 ≤ m < n）という形式の入力に対して、n+1の最大の約数kを見つける処理を行います。そして、2ⁿ⁺¹7^k-1を返し、この操作を繰り返すことで素数を生成します。

コンウェイのプログラムには、いくつかバリエーションが存在し、それぞれ生成速度が異なります。また、特定の整数Nが素数であるかチェックするのに必要なステップ数も、Nに依存する数式で表すことができます。

その他の例

FRACTRANでは、2進数におけるハミング重み（1の個数）を計算するプログラムなども作成できます。入力2^aに対して、13^H(a)を出力するプログラムがその例です。

まとめ

FRACTRANは、一見単純な分数の操作だけで、驚くほど複雑な計算を実現できる、興味深い言語です。その簡潔さとは裏腹に、その動作を完全に理解するには、素因数分解やレジスタマシンの概念などを理解する必要があります。また、プログラミングは非常に難解であり、高度な数学的知識を必要とします。

もう一度検索