株式会社ACCESSの關(セキ)と申します。
この記事はACCESS Advent Calendar 2016の7日目の記事です。
動機
ある日、ふと思って調べてみると
0.1234567891011121314...
が超越数であることを知った。そういう日もあるよね。
Champernowne定数とかいう名前までついていて御大層なものである。まあそれはいいとして、この定数、二進法のバージョンまであるようだ。
0.110111001011101111000...
これを見て、Turing Machine freak の私なら当然こう思うはずだ。
「こんな感じの超越数をTuring Machineで生成出来ないだろうか」と。
条件、前提
私の思う Turing Machine は
- テープの長さは左右両方向に無限で、最初は zero fill されている
- 1つのテープにread/write両方を行う
- 文字は
0と1のみ、空白はなし - ヘッドは1つ。変な外部機器とかはついてない
-
<state0, bit0, bit1, direction, state1>の形のコマンドの有限個の集まりでプログラムが書かれる
(例:<2, 0, 1, R, 3>で「状態2のときビット0を読んだらそこを1にして右に進み、状態を3にする」という意味。次にビットを読むときは状態3) - マシンの初期状態は
0 - 無限の長さの出力を得たいので、停止性は無視します
(注意: Turing Machineの定義は割とバリエーションがあります。「文字は0と1のみ」というのはあまり一般的ではないと思いますが面白いので採用しています)
また、いきなり超越数というのはハードルが高い(証明するのがめんどい)ので、少なくとも無理数を生成できれば良いものとします。 要は周期的でないパターンを生成できればいいです。
そこで、周期的でないパターンの中で最も簡単そうな101001000100001000001... という出力を生成することを目標にします。
(0.101001000100001000001... のつもり)
そもそも可能なのか？
例えば決定性有限オートマトンでは、起こりうる状態の個数が有限個なので、その個数回以上状態遷移を行うと同じ状態が再び現れ、ループしてしまう。
これと同じことが起こらないだろうか？プログラムの長さは有限、つまり使用するマシンの状態は有限個なのである。
しかし安心して欲しい。テープの長さは無限なのである。したがって、テープの状態が変わり続ける限り、「全く同じ状況」は発生しない。
逆に言えば、周期的でないパターンを生成するためには、すでにテープに出力したビットを利用することが鍵となるのだ。
カウンタが無い
基本的に左から順に書いていくのだが、問題は「0をこの後何個並べればよいか」である。
Turing Machine にはカウンタなどという上等なものは付いていないのでこれが結構厄介。
通常(?)、n個の0のあとに1を出力したかったら、<i, 0, 0, R, i+1> というコマンドを i = 0 から n - 1 まで実行し、最後に <n, 0, 1, R, A> で終了する。つまり状態をカウンタとして利用するのであるが、今回はその手は使えない。なぜなら状態は有限個しか使えないからだ。出力したい数にはいくらでも長い0の並びが存在する。
したがって、先述の通りテープをうまく利用するしか無いのである。
テープに目印をつける
仮に
101001000100001 という出力がすでに出来ていて、今右端の1を見ているものとする。
これから左に進んで0を読みつつ右端に0を追加していきたいのだが、使える状態の数が有限なので「どこまで読んだか/書いたか」ということをマシンは覚えておくことが出来ない。勿論ヘッドが2つあるわけでもないしワープ機能があるわけでもない。
そこで、テープに「ここまで読んだ/書いた」ということを記録しておく。
例えば
101001000100(1)010[1] というように、「(1)のところまで読んであり、[1]のところまで書いた」という目印となる1をテープに書いておくのである(()とか[]とかはここでの説明のための記号で、テープには書かれません)。ここから(1)を左に、[1]を右に進めていけば
10100100010(1)00100[1]
1010010001(1)0001000[1] となって、(1)が左の1とぶつかる。これが「読み終わった」状態。
読み終わったら、(1)は0に戻して、[1]は2つ右にずらして
10100100010000100000[1]
これで0を1つ左の4個より1個多く並べることが出来た。今までの手順を再度走らせるために、
101001000100001000(1)1[1] としておけば完成である。一応もう一度同じ手順を踏むと、
10100100010000100(1)010[1]
1010010001000010(1)00100[1]
101001000100001(1)0001000[1]
101001000100001000001000000[1]
10100100010000100000100000(1)1[1]
となる。
最初は、
1(1)1[1] とすれば良いだろう。
アルゴリズム
以上を踏まえると次のようになる:
- まずテープを
1111の状態にする。(1(1)1[1]) -
1を２回見つけるまで左に進む。((1)まで進む) - 見つけた2つめの
1は0にしておき、更にもう1つ左に進み、そこのビットが
-
0の場合(まだ読み途中)- そこのビットを
1に変える -
1を２回見つけるまで右に進む([1]まで進む) - 見つけた2つめの
1のところから01とする -
- の手順に戻る
- そこのビットを
-
1の場合(読み終わった)- そこのビットはそのままにして、
1を２回見つけるまで右に進む([1]まで進む) - 見つけた2つめの
1のところから0111とする。 -
- の手順に戻る
- そこのビットはそのままにして、
トレースすると以下のようになります(<>で括ってるところがヘッドの位置)。
111<1> # 1. の手順
1<1>11 # 2. の手順
<1>011 # 3. の条件分岐の最中
101<1> # 3. の「`1`の場合」の1つめの手順
101011<1> # 3. の「`1`の場合」の2つめの手順
1010<1>11 # 2. の手順
101<0>011 # 3. の条件分岐の最中
101<1>011 # 3. の「`0`の場合」の1つめの手順
101101<1> # 3. の「`0`の場合」の2つめの手順
1011010<1> # 3. の「`0`の場合」の3つめの手順
101<1>0101 # 2. の手順
10<1>00101 # 3. の条件分岐の最中
1010010<1> # 3. の「`1`の場合」の1つめの手順
1010010011<1> # 3. の「`1`の場合」の2つめの手順
...
プログラム
以上を踏まえて、プログラムを書いてみます。
# 1. `1111` に初期化
<0, 0, 1, R, 1>
<1, 0, 1, R, 2>
<2, 0, 1, R, 3>
<3, 0, 1, L, 4>
# 2. `1` を2回見つけるまで左に進み、見つけたら2つめの`1`を`0`にしておく
<4, 0, 0, L, 4>
<4, 1, 1, L, 5>
<5, 0, 0, L, 5>
<5, 1, 0, L, 6>
# 3. `0`の場合: そこを`1`にする。2回`1`を見つけるまで右に進む。見つけたところから`01`にして、 2. に戻る
<6, 0, 1, R, 7>
<7, 0, 0, R, 7>
<7, 1, 1, R, 8>
<8, 0, 0, R, 8>
<8, 1, 0, R, 9>
<9, 0, 1, L, 4>
# 3. `1`の場合: 2回`1`を見つけるまで右に進み、2つめの`1`のところから`0111`とする(最後の処理は 1. の処理と同じなのでそこに飛ぶ)
<6 , 1, 1, R, 10>
<10, 0, 0, R, 10>
<10, 1, 1, R, 11>
<11, 0, 0, R, 11>
<11, 1, 0, R, 1 >
実行
動かなきゃ正義じゃない。ということで探したらエミュレータありました。
http://tsujimotter.info/works/turing/
微妙にプログラムの形式が違ったので直して:
q_0, 0, 1, R, q_1
q_1, 0, 1, R, q_2
q_2, 0, 1, R, q_3
q_3, 0, 1, L, q_4
q_4, 0, 0, L, q_4
q_4, 1, 1, L, q_5
q_5, 0, 0, L, q_5
q_5, 1, 0, L, q_6
q_6, 0, 1, R, q_7
q_7, 0, 0, R, q_7
q_7, 1, 1, R, q_8
q_8, 0, 0, R, q_8
q_8, 1, 0, R, q_9
q_9, 0, 1, L, q_4
q_6 , 1, 1, R, q_10
q_10, 0, 0, R, q_10
q_10, 1, 1, R, q_11
q_11, 0, 0, R, q_11
q_11, 1, 0, R, q_1
↑をコピペすると動きます。テープがzero fillされてないので input には000000000000とかを入力しておいて下さい。
めでたく101001000... を生成することが出来ました。実はChampernowne定数 C2 を生成する方法も見つけたのですが、状態を53個も使う大作になってしまったので割愛。
##まとめ
(私の思う)Turing Machine で 10100100010000... という出力を得る方法を紹介しました。
明日のACCESS Advent Calendar 2016の記事は @magicant さんです。