はじめに
皆さんは FRACTRAN をご存知でしょうか？僕も最近知ったのですが、非常にシンプルながら上手く出来ている計算モデルだと思います。
チューリング完全らしいのでチューリングマシンの実装をやってみたい所ですが、まずは FRACTRAN におけるプログラミングの感覚を掴むため、ここではいくつかプログラムを書いてみるだけに留めます。
FRACTRAN とは
- FRACTRANのプログラムは有限個の有理数の組（順序つき）で与えられます
- 入力は自然数で与えられます
- 入力に対し、掛けると自然数になる最初の有理数を掛けて、次の入力とします
- 入力に対し、掛けて自然数になるものが無くなったら終了
例えば、プログラムが $(\frac{3}{2}, \frac{5}{3})$ のとき、入力が 6 なら
$6 → 6 \times \frac{3}{2} = 9 → 9 \times \frac{5}{3} = 15 → 15 \times \frac{5}{3} = 25$
となります。
素因数分解とFRACTRAN
入力となる自然数を素因数分解して考えてみましょう。
例えば $6 = 2^1 \times 3^1$ ですが、これは「2番地のレジスターに1、3番地のレジスターに1が入っている状態」と見ることができます。
すると、FARCTRANのプログラムは「特定のレジスターの値が一定以上の場合に、その値を一定値減らし、別のレジスターの値を一定値増やす」ということを何通りか並べたもの、と捉えることができます。
先程の例 $(\frac{3}{2}, \frac{5}{3})$ なら「2番地のレジスターの値が1以上なら、1減らして3番地のレジスターの値を1増やす」「3番地のレジスターの値が1以上なら、1減らして5番地のレジスターの値を1増やす」となりますね。
このように
- 自然数 = 有限個のレジスターに自然数の値が入った状態
- 有理数 = レジスターの値を増減する操作
と解釈することで計算モデルを作っているわけです。上手いですねぇ。しかも結構汎用的に使えそうな考え方です。
プログラム例
プログラム例をいくつか見ていきながら、FRACTRANにおけるプログラミングのセンスを磨いていきましょう。
足し算
なんと、$(\frac{3}{2})$ というだけのプログラムで足し算が表現できます。
入力を $2^m \times 3^n$ として与えると、2に指数が残っている限り $\frac{3}{2}$ が掛け続けられることになり、「2の指数を1減らして3の指数を1増やす」という操作が m 回続くことになります。
結果として出力は $3^{m+n}$ になりますね。これで足し算が出来ました。
$(\frac{5}{2}, \frac{5}{3})$ としても同様に、同じ入力に対して出力が $5^{m+n}$ となって足し算ができますね。
さらに別解として、 $(\frac{81}{16}, \frac{9}{4}, \frac{3}{2})$ のようにすると計算ステップ数を減らせたりします。
min
min(m, n) は $(\frac{5}{6}, \frac{1}{2}, \frac{1}{3})$ として表現することができます。
入力を $2^m \times 3^n$ として与えると、m, n の両方が1以上である限り $\frac{5}{6}$ を掛け続けて、5の指数が min(m, n) になります。が、これだけだと出力が $2^{m-\min(m,n)}\times 3^{n-\min(m,n)}\times 5^{\min(m,n)}$ となって2, 3の指数の肩にゴミを残す可能性があるので、$\frac{1}{2}, \frac{1}{3}$ を掛け続けてゴミを掃除し、出力を $5^{\min(m,n)}$ のみにします。
$\frac{1}{2}, \frac{1}{3}$ は $\frac{5}{6}$ よりも後に配置しないといけないことには注意しましょう。
半分
「半分にする」（小数点以下切り捨て）プログラムを考えます。これは $(\frac{3}{4}, \frac{1}{2})$ で出来ます。
入力を $2^m$ とすれば、$\frac{3}{4}$ によって m が2以上のとき m を 2 減らしつつ、3の指数の肩を1つ増やします。これを続ければ、$m = 2m'$ のとき出力は $3^{m'}$ となって停止します。
一方、$m=2m'+1$のとき、$\frac{3}{4}$を掛け続けるだけだと出力は $2^1 \times 3^{m'}$ となってゴミが残ります。$\frac{1}{2}$ を後ろに置いてこれを掃除して、出力を $3^{m'}$ に調整しているわけです。
掛け算
次に掛け算を作ります。ここからプログラムらしいプログラムになってきます。
入力は $2^m\times 3^n$ で与えるとして、作戦は以下です:
- 5 の指数の肩を accumulator とする（初期値0）
- n > 0 のとき、accumulator に m を加算し、n を1減らす
- 上記の手順2を繰り返し、n = 0 になったら終わり
順番に考えていきましょう。手順1. に対しては特に何もすることはありません。
手順2. n > 0 のとき、 accumulator に m を加算し、n を1減らす
安直に $\frac{5}{6}$ みたいにやると、3の指数も一緒に減っていってしまいます。
3の指数を減らす処理は最初に一度だけ行い、その後は「2の指数の肩を5の指数の肩に加算する処理」に入りたいわけです。
そのためには、上記の処理の最中であることを表すマーカーを用意します。まず $\frac{7}{3}$ として「7 の指数の肩に数字があるうちは上記の処理中」ということにして、上記の処理は $\frac{7}{3}$ よりも前に書けば良さそうです。
しかしこのマーカーも一度消費すると消えてしまうため、7 だけでなく 11 も使って、2つの領域でマーカーを維持することにします。プログラムにすると
$(\frac{55}{14} = \frac{5×11}{2×7}, \frac{35}{22} = \frac{5×7}{2×11}, \frac{7}{3})$ ですね。これにより入力状態は
$2^m\times 3^n → 3^{n-1} \times 5^m \times 7^{1 - (m \mod 2)} \times 11^{(m \mod 2)}$
となります。
が、これは途中の状態。このままだと $\frac{7}{3}$ がまた走ってしまいます。
上記の手順2を繰り返し、n = 0 になったら終わり
手順2を繰り返すためには、再び $2^m$ を復活させれば良さそうです。
が、m が無くなってしまっています（$5^m$ というのがありますが、これは計算の過程で m よりも大きくなっていく）。
ということで、先程の処理時に、別の領域に m を保存しておくことにしましょう。新たな領域13を使い、5に加算する時、こちらも増やすようにすれば良いでしょう:
$(\frac{715}{14} = \frac{5×11×13}{2×7}, \frac{455}{22} = \frac{5×7×13}{2×11}, \frac{7}{3})$
これで入力状態は $3^{n-1} \times 5^m \times 7^{1 - (m \mod 2)} \times 11^{(m \mod 2)} \times 13^m$ となります。
次に7と11の肩にゴミが残っているので $\frac{1}{7}, \frac{1}{11}$ で掃除して、この13の指数を $\frac{2}{13}$ で2に移動させていきましょう。順番に注意して:
$(\frac{715}{14} = \frac{5×11×13}{2×7}, \frac{455}{22} = \frac{5×7×13}{2×11}, \frac{1}{7}, \frac{1}{11}, \frac{2}{13}, \frac{7}{3})$
とすれば、入力状態は $2^m \times 3^{n-1} \times 5^m$ となります。
これで、n > 1 の場合は $\frac{7}{3}$ が走って再び手順2が実行されます。n = 1だった場合はここで終了しますが、$2^m$ がゴミとして残ってしまうので、最後に $\frac{1}{2}$ で掃除して
$(\frac{715}{14} = \frac{5×11×13}{2×7}, \frac{455}{22} = \frac{5×7×13}{2×11}, \frac{1}{7}, \frac{1}{11}, \frac{2}{13}, \frac{7}{3}, \frac{1}{2})$
とすれば完成です。改めてトレースすると、
- 入力は $2^m \times 3^n$
- まず $\frac{7}{3}$ で $2^m \times 3^{n-1} \times 7$
- 次に $\frac{5×11×13}{2×7}$ と $\frac{5×7×13}{2×11}$ が合計 m 回交互に適用されて、$3^{n-1} \times 5^m \times 7^{1 - (m \mod 2)} \times 11^{(m \mod 2)} \times 13^m$
- $\frac{1}{7}$ か $\frac{1}{11}$ が適用されて $3^{n-1} \times 5^m \times 13^m$
- $\frac{2}{13}$ が m 回適用されて $2^m \times 3^{n-1} \times 5^m$
- 3 の指数の肩が残っていれば $\frac{7}{3}$ から再び繰り返し
- 3 の指数の肩は1ずつ減り、5の指数の肩はmずつ増えていく
- 3 の指数の肩が 0 になったら、 $2^m \times 5^{mn}$ に $\frac{1}{2}$ が m回適用されて $5^{mn}$
となります。
log2
次に log2（2を底とする対数をとる関数、小数点以下切り捨て）を作ってみましょう。
これは「半分にする」計算を繰り返しつつ「何回半分にできたか」をカウントしておき、1になったら終了、という流れで実装します。具体的には以下としましょう:
- $2^m$ に対して半分にする計算を行って $3^{m÷2}$ を作る（m÷2は割った商の意味です）
- 3の指数の肩が残っていれば 5 の指数を1増やす。残っていなければ終了
- 3の指数の肩を2に移動する
- 最初に戻る
手順1
これは上のほうで作ったものと同じことをすれば良いですね。$(\frac{3}{4}, \frac{1}{2})$ でOKです。
手順2
次の手順で3の指数の方を2に移動したいので、ここでついでに1つだけ移動しちゃいましょう。
ということで $(\frac{3}{4}, \frac{1}{2}, \frac{10}{3} = \frac{2×5}{3})$ とします。
手順3
3の指数を2に移動するには $\frac{2}{3}$ で済みそうなのですが、先程の $\frac{10}{3}$ とどうやっても競合してしまいます。
ということで、「3の指数を2に移動中」であることを表すマーカーを7と11に記録しましょう。
- まず手順2の時に最初のマーカーを作ります: $\frac{10}{3} → \frac{70}{3} = \frac{2×5×7}{3}$
- マーカーがあるときだけ3から2に指数を移動: $\frac{22}{21} = \frac{2×11}{3×7}, \frac{14}{33} = \frac{2×7}{3×11}$
- マーカーをクリーンアップ: $\frac{1}{7}, \frac{1}{11}$
移動している途中の2の指数に反応して手順1が走らないよう、順番に気をつけると:
$(\frac{22}{21} = \frac{2×11}{3×7}, \frac{14}{33} = \frac{2×7}{3×11}, \frac{1}{7}, \frac{1}{11}, \frac{3}{4}, \frac{1}{2}, \frac{70}{3} = \frac{2×5×7}{3})$
となります。一応トレースしてみましょう:
- 入力は $2^m$
- $\frac{3}{4}$ が m÷2回、その後 $\frac{1}{2}$ が (m mod 2) 回適用されて $3^{m÷2}$
- $m÷2 ≥ 1$ のとき $\frac{70}{3}$ が適用されて $2×3^{m÷2-1}×5×7$
- $\frac{22}{21}$ と $\frac{14}{33}$ が合計 $m÷2-1$ 回交互に適用されて $2^{m÷2}×5×7^{(m÷2 \mod 2)}×11^{1 - (m÷2 \mod 2)}$
- $\frac{1}{7}$ と $\frac{1}{11}$ のいずれかが適用されて $2^{m÷2}×5$
- 以上の2~5が繰り返され、1回の繰り返しごとに2の指数の肩は半分になり、5の指数の肩は1増える
- 2の指数の肩が1になると $\frac{1}{2}$ が適用され、$5^{\log_2 m}$ （小数点以下切り捨て）となる
所感
これで大体 FRACTRAN におけるプログラミングの感覚が掴めてきたのではないかと思います。個人的には以下がポイントかなと思いました:
- 使えるレジスターの数はプログラムごとに固定。横にスケールするようなプログラムは書けない
- 「マーカー」を使いたい時は2つの素数を使い、交互にマークする
- $\frac{1}{p}$ でゴミ掃除
- 順番に注意。「操作対象×マーカー」を分母としておけば基本大丈夫
準備は出来たと思うので、次の記事でチューリングマシンの実装をやっていきましょう。