はじめに
この記事はFRACTRAN におけるプログラミングの続きの記事になります。
前回は FRACTRAN でいくつかプログラムを書き、大体感覚が掴めてきた所だと思います。ということで、今回は元々の目標であった、チューリングマシンの実装をやっていきます。
まずは作戦を考えましょう。
モデルと目標
まずチューリングマシンの状況とプログラムをそれぞれ FRACTRAN のそれにエンコーディングし、どんな FRACTRAN のプログラムを作ればよいか入出力を考えましょう。
今回実装するチューリングマシンの構造
- テープ
- 文字は0と1のみとし、左右両方向に無限に伸びているものとします
- 入力状態は有限個のテープのみが1であるとします
- 数式で書くなら$\{~(c_i)_{i\in\mathbb{Z}}~ |~ c_i \in \{0, 1\}, ~ \sum_{i\in\mathbb{Z}}c_i < \infty~\}$
- 状態
- 1つの自然数で表現します
- 受理状態を0、初期状態を1とします
- プログラム
- $(s, c, c', d, s') ∈ (ℕ \setminus \{0\})×\{0,1\}×\{0,1\}×\{L, R\}×ℕ$ という形のコマンドの有限個の列とします
- 「状態が s のときにヘッドの位置の文字が c なら、ヘッドの位置の文字を c' に変えて d の方向にヘッドを移動させ、状態を s' にする」という意味です
FRACTRAN上での表現
テープは左側、ヘッド、右側に分けて3つの自然数で表現することにします。先程の$(c_i)_{i\in\mathbb{Z}}$に対して、
\begin{align}
l &= \sum_{i=-1}^{-\infty}2^{-i-1}c_i \\
c &= c_0 \\
r &= \sum_{i=1}^{\infty}2^{i-1}c_i\\
\end{align}
とします。状態 s は元々自然数なのでそのまま採用して、ここまでをまとめて
$2^s×3^c×5^l×7^r$
という入力として表現することにします。
目標は、チューリングマシンのプログラム（＝コマンド列） $((s_i, c_i, c'_i, d_i, s'_i))_{i=0,1,...,n-1}$ に対して、FRACTRANのプログラム$(q_i)_{i=0,1,...,m-1}$ を対応させることになります。
チューリングマシンでの1ステップの評価は、FRACTRAN上では複数ステップでの評価になります。
実装
FRACTRANのプログラムの流れは:
- 現在の状態に対応するコマンドを選ぶ
- コマンドの内容に応じて s, c, l, r を操作する
となります。上記の手順について、順番にそれぞれ考えていきましょう。
手順1. 現在の状態に対応するコマンドを選ぶ
実はここが一番難しかったりします。
仮定: コマンドの並び順を固定する
まず、元となるチューリングマシンのプログラム $((s_i, c_i, c'_i, d_i, s'_i))_{i=0,1,...,n-1}$に対して、以下の仮定を課します:
- $s_i = i \div 2 + 1$ （※ $i\div 2$ は i を 2 で割った商）
- $c_i = i \mod 2$
これはつまり、$((1, 0, ...), (1, 1, ...), (2, 0, ...), (2, 1, ...), ...)$ という感じでコマンド列が状態と文字の辞書式順に並んでいる、という仮定です。
状態に歯抜けがあった場合は、歯抜けしている数以上の状態の数を全てデクリメントして詰めれば良いです。
文字側に歯抜けがあった場合（例えば (1, 0, ...) のコマンドはあるけど (1, 1, ...) のコマンドは無い、みたいな場合）は適当にコマンドをでっち上げて追加します。どうせ実行されない or 元々エラーなので何を追加しても問題ないはず。
上記仮定があると、状態が $s$ でヘッドの位置の文字が $c$ の時に $2(s-1)+c$ 番目のコマンドを実行すれば良いため、比較的簡単に対応するコマンドを選ぶことができるようになります。
コマンドを選ぶ処理
n個のコマンドに対して、11から順にn個の素数をとり、「そのコマンドを実行する」というマーカーにします。例えば
11 は (1, 0, ...) のコマンド、13 は (1, 1, ...) のコマンド、17 は (2, 0, ...) のコマンド、といった感じです。
2の指数(s)を1ずつ減らしながらマーカーを2つずつ移動させて、2の指数が無くなったタイミングで3の指数(c)があればマーカーを更に1つだけ移動すれば良さそうです。
$p_i$ を $i$番目($i≥0,~p_0=2, p_4=11$)の素数として、順番に気をつけて（実行順は右から左になります）、
$$
(\frac{p_{n+3}}{3×p_{n+2}}, \frac{p_{n+2}}{2×p_n}, \frac{p_{n+1}}{3×p_n}, ..., \frac{p_{2j+6}}{2×p_{2j+4}}, \frac{p_{2j+5}}{3×p_{2j+4}}, ..., \frac{p_6}{2×p_4}, \frac{p_5}{3×p_4}, \frac{11}{2})
$$
とすれば良さそうです（$j$は$0$から$(n-4)÷2$まで動いていて、最初から2~3番目の項と最後から2~3番目の項と被っています）。
これで入力は $5^l×7^r×p_{2(s-1)+c+4}$ となります。
手順2. コマンドの内容に応じて s, c, l, r を操作する
$d_i$ が L の時は
\begin{align}
l&←l \div 2\\
c&←l \mod 2\\
r&←2r+c'_i\\
s&←s'_i
\end{align}
$d_i$ が R の時は
\begin{align}
l&←2l+c'_i\\
c&←r \mod 2\\
r&←r \div 2\\
s&←s'_i
\end{align}
と更新出来れば良いです。文章にすると「進む方向のテープを２で割り、その余りを次の c にする。反対側のテープは2倍して $c'_i$ を足す。s は $s'_i$ にする」とまとめられます。
この処理のためには固定で使用する素数をいくつか追加する必要がありますね。以下のようにしましょう:
- 2, 3, 5, 7: チューリングマシンの状況（それぞれ指数の肩に s, c, l, r が乗っている）
- 11: $d_i$ が L の場合、l を半分にする時の一時メモリー
- 13: $d_i$ が R の場合、r を半分にする時の一時メモリー
- 17, 19: $d_i$ が L の時に、l を半分にしている途中であることを表すマーカー
- 23, 29: $d_i$ が R の時に、r を半分にしている途中であることを表すマーカー
- 31: $d_i$ が L の場合、r を2倍にする時の一時メモリー
- 37: $d_i$ が R の場合、l を2倍にする時の一時メモリー
- 41, 43: $d_i$ が L の時に、r を2倍にしている途中であることを表すマーカー
- 47, 53: $d_i$ が R の時に、l を2倍にしている途中であることを表すマーカー
- 59: $c'_i$ を乗せておくメモリー
- 61以降の素数: 手順1でコマンドを選ぶ時のマーカー群
先程の手順1で $p_4$ としたところが $p_{17}$ となるので、添字を+13しておきましょう。
選ばれたコマンドを表すマーカーは1つだけなので、一度使うと「どのコマンドが選ばれたか」の情報が失われます。従って、最初の処理で
- d に応じたマーカーを1にして、以降の処理の流れを決定する
- s を $s'_i$ に置き換える
- $c'_i$ を記録しておく
の3つを同時にやっておく必要があります。これに注意して、進行方向のテープを半分にする（& 次の処理に進む）処理は:
- $d_i$ が L のとき
- $(\frac{2^{s'_i}×17×59^{c'_i}}{p_{i+17}}, \frac{11×19}{5^2×17}, \frac{11×17}{5^2×19}, \frac{3×41}{5×17}, \frac{3×41}{5×19}, \frac{5}{11}, \frac{41}{17}, \frac{41}{19})$
- これで入力は $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^{r}×41×59^{c'_i}$ になります
- $d_i$ が R のとき
- $(\frac{2^{s'_i}×23×59^{c'_i}}{p_{i+17}}, \frac{13×29}{7^2×23}, \frac{13×23}{7^2×29}, \frac{3×47}{7×23}, \frac{3×47}{7×29}, \frac{7}{13}, \frac{47}{23}, \frac{47}{29})$
- これで入力は $2^{s'_i}×3^{r \mod 2}×5^l×7^{r÷2}×47×59^{c'_i}$ になります
で出来ますね。次に、進行方向と逆側のテープを2倍して$c'_i$を足す処理は
- $d_i$ が L のとき
- $(\frac{31^2}{7×41}, \frac{31^2}{7×43}, \frac{7}{41×59}, \frac{7}{43×59}, \frac{1}{41}, \frac{1}{43}, \frac{7}{31})$
- これで入力は $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^{2r+c'_i}$ になります
- $d_i$ が R のとき
- $(\frac{37^2}{5×47}, \frac{37^2}{5×53}, \frac{5}{47×59}, \frac{5}{53×59}, \frac{1}{47}, \frac{1}{53}, \frac{5}{37})$
- これで入力は $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^{2r+c'_i}$ になります
で出来ます。これで完成ですね。
完成品
改めて、プログラム全体を書き下してみましょう。順番に気をつけて並べると:
\begin{align}
(&\\
&\frac{11×19}{5^2×17}, \frac{11×17}{5^2×19}, \frac{3×41}{5×17}, \frac{3×41}{5×19}, \frac{5}{11}, \frac{41}{17}, \frac{41}{19},\\
&\frac{13×29}{7^2×23}, \frac{13×23}{7^2×29}, \frac{3×47}{7×23}, \frac{3×47}{7×29}, \frac{7}{13}, \frac{47}{23}, \frac{47}{29},\\
&\frac{31^2}{7×41}, \frac{31^2}{7×43}, \frac{7}{41×59}, \frac{7}{43×59}, \frac{1}{41}, \frac{1}{43}, \frac{7}{31}\\
&\frac{37^2}{5×47}, \frac{37^2}{5×53}, \frac{5}{47×59}, \frac{5}{53×59}, \frac{1}{47}, \frac{1}{53}, \frac{5}{37},\\
&\frac{p_{n+16}}{3×p_{n+15}}, \\
&\frac{p_{n+15}}{2×p_{n+13}}, \frac{p_{n+14}}{3×p_{n+13}}, ... , \frac{p_{19}}{2×p_{17}}, \frac{p_{18}}{3×p_{17}},\\
&\frac{2^{s'_{n-1}}×17^{1-d_{n-1}}×23^{d_{n-1}}×59^{c'_{n-1}}}{p_{n+16}}, ..., \frac{2^{s'_0}×17^{1-d_0}×23^{d_0}×59^{c'_0}}{p_{17}},\\
&\frac{p_{17}}{2}\\
)&
\end{align}
ですね（$d_i ∈ \{0, 1\}$ としました。0 が L、 1 が R です）。
トレース
一応トレースしてみましょう。入力状態は$2^s×3^c×5^l×7^r$からスタートです。
- s = 0 （受理状態）のとき、停止
- s > 0 のとき、 $\frac{p_{17}}{2}$ で $2^{s-1}×3^c×5^l×7^r×p_{17}$
- $\frac{p_{2j+19}}{2×p_{2j+17}}$ により、2の指数が0になるまで、$p$ の添字が2ずつ増える
- $3^c×5^l×7^r×p_{2(s-1)+17}$
- $\frac{p_{2j+18}}{3×p_{2j+17}}$ により、3の指数(c)が1の場合 $p$ の添字が1増える
- $5^l×7^r×p_{2(s-1)+c+17}$
- $i = 2(s-1)+c$ として $\frac{2^{s'_i}×17^{1-d_i}×23^{d_i}×59^{c'_i}}{p_{i+17}}$ が適用される
- $2^{s'_i}×5^l×7^r×17^{1-d_i}×23^{d_i}×59^{c'_i}$
- $d_i$ に応じて以下のいずれかが走る:
- $d_i = 0$ のとき
- $\frac{11×19}{5^2×17}, \frac{11×17}{5^2×19}, \frac{3×41}{5×17}, \frac{3×41}{5×19}$ より、5の指数が2ずつ減りながら11の指数は1増えつつ、17と19の指数が0と1を交互に行き来する。最後に5の指数が1残っていたら3×41が掛かり、17と19の指数は消える
- $2^{s'_i}×3^{l \mod 2}×7^r×11^{l÷2}×17^{l÷2 \mod 2}×19^{1-(l÷2 \mod 2)}×41^{l \mod2}×59^{c'_i}$
- $\frac{5}{11}$ より、11の指数が5に移動する
- $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^r×17^{(1 - (l \mod 2))× (1 - (l÷2 \mod 2))}×19^{(1 - (l \mod 2))× (l÷2 \mod 2)}×41^{l \mod2}×59^{c'_i}$
- $l \mod 2 = 0$ だったとき、$\frac{41}{17}, \frac{41}{19}$ のいずれかが適用され、17, 19 の指数が消えて41の指数が1になる
- $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^r×41×59^{c'_i}$
- $\frac{31^2}{7×41}, \frac{31^2}{7×43}$ により、7の指数が0になるまで1ずつ減り、31の指数が2ずつ増え、41と43の指数が交互に0と1を繰り返す
- $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×31^{2r}×41^{1 - (r \mod 2)}×43^{r \mod 2}×59^{c'_i}$
- $\frac{7}{41×59}, \frac{7}{43×59}, \frac{1}{41}, \frac{1}{43}$ のいずれかが適用され、41、43、59の指数が消えて7の指数が$c'_i$となる
- $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^{c'_i}×31^{2r}$
- $\frac{7}{31}$ により、31の指数が7に移動する
- $2^{s'_i}×3^{l \mod 2}×5^{l÷2}×7^{2r+c'_i}$
- $\frac{11×19}{5^2×17}, \frac{11×17}{5^2×19}, \frac{3×41}{5×17}, \frac{3×41}{5×19}$ より、5の指数が2ずつ減りながら11の指数は1増えつつ、17と19の指数が0と1を交互に行き来する。最後に5の指数が1残っていたら3×41が掛かり、17と19の指数は消える
- $d_i = 1$ のとき
- $d_i = 0$ の時と同様なので省略。
- $2^{s'_i}×3^{r \mod 2}×5^{2l+c'_i}×7^{r÷2}$ となる。
- $d_i = 0$ のとき
ちゃんとエミュレート出来ていそうですね！