まえがき

これは以前書いた記事の続きです。TuringMachineの深淵に覗き返されたい方向け。

目的

Champernowne定数 C2 = 0.11011100101110... に見立てて
11011100101110... という出力をするTuringMachineのプログラムを作りたいと思います。
TuringMachineの定義は以前同様0と1のみの文字を使い、テープは0が左右両方向に無限に続いている状態でスタートします。無限の長さの出力を得たいので停止性は無視します。

方針

帰納的に考えます。例えば、すでに 1 10 11 100 まで出来ているものとします。(スペースは便宜上入れています)
次は 101 を右端に足したいのですが、そのためには「今100まで書いた」もしくは「次に書くべきは101」という情報をテープに書いておく必要があります。
また、その情報がどこに書いてあるのかも分かるようにしないといけません。

marker space と copied space

そこで、markerを置いておくmarker spaceと前の値(ここでは100)をコピーしておくcopied spaceというもの(勝手に名前つけた)を用意します。

11011100[1](1)[0](0)[0](0)[1]

[]で括った部分が marker space で、両端は1にしておきます。
- このspaceに1を配置することで「どこまで読んだ」とか「どこまで書いた」という情報を表します。
()で括った部分が copied space で、100を予めコピーしておきます。

このように marker space と copied space を交互に配置することで、「2つずつ移動しながら値を操作し、 marker space に 1 が現れたらそこで分岐する」ことが可能になります。

1 を足す

1を足すだけでも割と苦労します。
筆算と同様に1の位から順に考えていきます。

copied space の右端からスタートして、0が出てきたら1にして終わりです。
copied space に 1 が出てくる間は 0 にし続けます。

基本的にはこれでいいのですが、例えばcopied spaceに111が入っている場合、次の数字は1000です。そう、桁を増やさないといけません。

この場合は marker space の左端の 1 に到達するので、そこで分岐すればいいでしょう。

これで1を足すことが出来ました。
11011100[1](1)[0](0)[0](1)[1]

あとは marker space を削除すれば、
11011100101
となります。めでたしめでたし。

まだめでたくない

嘘です。こんなんじゃ終わりません。

次のステップの準備が出来ていませんよ。

コピー

ということで、次のステップのための marker space と copied space を書いておく必要があります。

まずは、前の copied space の左端のビットを読んでおいて、
11011100[1](1)[1](0)[0](1)[1][1](1)[1]
とします。
左から２番めの marker space が 1 になっていて、「ここまで読んだ」ということを表しています。こいつを read marker と呼ぶことにします。

次に、read marker の右のビット(今回は0)を読み、一番右端のmarkerの右に書き足しつつ read marker と右端のmarkerもずらします:
11011100[1](1)[0](0)[1](1)[1][1](1)[0](0)[1]

これを繰り返して read marker が左から3番目のmarkerに重なったところで終了。
11011100[1](1)[0](0)[0](1)[1][1](1)[0](0)[0](1)[1]

これでコピーが完了です。

前のmarker spaceの削除

以上で、無事
11011100[1](1)[0](0)[0](1)[1][1](1)[0](0)[0](1)[1]
とすることが出来ました。ここから左半分のmarker spaceを削除して、
11011100101[1](1)[0](0)[0](1)[1]
とできれば今度こそめでたくなります。

これは一番左端のmarkerを右にずらしながら、そこから右を全て左シフトさせていけば良いです。
11011100[1](1)[0](0)[0](1)[1][1](1)[0](0)[0](1)[1] は、まず
11011100 1 [1][0](0)[0](1)[1][1](1)[0](0)[0](1)[1] として(左端のmarkerの右の1を書いて、markerを移動させた)、
11011100 1 [1](0)[0](1)[1][1](1)[0](0)[0](1)[1] とします(左端のmarkerより右を全て左シフト)。
この手順を繰り返して
110111001[1](0)[0](1)[1][1](1)[0](0)[0](1)[1]
110111001 0 [1][0](1)[1][1](1)[0](0)[0](1)[1]
110111001 0 [1](1)[1][1](1)[0](0)[0](1)[1]
110111001 0 1 [1][1][1](1)[0](0)[0](1)[1]
ここで左端のmarkerが前のmarker spaceの終わりに到達しました。ここでもう2個ずらせばOKです。
110111001 0 1 [1](1)[0](0)[0](1)[1]

めでたしめでたし。

まだめでたくない(2nd)

帰納的に考えるとか言っときながら、最初どうするか決めてませんでした。

1[1](1)[1] で良いでしょう。

ここでラスボスが登場

なんか忘れてませんか？そうです、プログラムを書いていなかったのです。
特に左シフトなんかはサラッと書いていましたが、プログラムに書き起こすと結構えげつないですよ。地獄の業火に焼かれながら生きろ！

champernowne2.tm

# まず 1[1](1)[1]とする
0, 0, 1, R, 1
1, 0, 1, R, 2
2, 0, 1, R, 3
3, 0, 1, L, 4

# 1 を足す
4, 0, 1, L, 12 # copied space に0を見つけたら1にして終わり、左端に移動する処理に移行
4, 1, 0, L, 5  # copied space が1なら0にし続ける
5, 0, 0, L, 4  # まだ0にし続けている状態で marker space が0なら読み飛ばす
5, 1, 1, R, 6  # まだ0にし続けている状態でmarkerを見つけた => 桁を増やす処理に移行

# 桁を増やす(ここに入るときにはすでに copied space は全て0になっている)
6,  0, 1, R, 7  # 最初の1
7,  0, 1, R, 8  # read marker を置いておく
7,  1, 1, R, 10 # 1[1](1)[1]の処理のときだけここに来る。1[1](1)[1](0)[1]とするため10へ
8,  0, 0, R, 9  # copied space は読み飛ばす(copied spaceには0しかない)
9,  0, 0, R, 8  # marker space が0のうちは読み飛ばす
9,  1, 0, R, 10 # 右端のmarkerに到達。 ...[1] を ...[0](0)[1] にするためここは0にする
10, 0, 0, R, 11 # ...[0](0)
11, 0, 1, R, 24 # ...[0](0)[1] にした。コピーの準備処理に移行(この場合はcopied spaceの先頭は1であることに注意)

# 左端に移動する
12, 0, 0, L, 13 # marker space が 0 のうちは読み飛ばす
13, 0, 0, L, 12 # copied space は読み飛ばす
13, 1, 1, L, 12
12, 1, 1, R, 14 # 左端のmarkerに到達。コピーの準備処理に移行

# コピーの準備処理(最初の1ビットと新しいmarkerを置く処理)
14, 0, 0, R, 15 # 0を読んだので0をコピーする
  15, 0, 1, R, 16 # read marker を置く
  16, 0, 0, R, 17 # copied space は読み飛ばす
  16, 1, 1, R, 17
  17, 0, 0, R, 16 # marker spaceが0のうちは読み飛ばす
  17, 1, 1, R, 18 # 右端のmarkerに到達
  18, 0, 1, R, 19 # ...[1] を ...[1][1](0)[1] とするためここは1にする
  19, 0, 0, R, 20 # ...[1][1](0)
  20, 0, 1, L, 27 # ...[1][1](0)[1] とした。これでコピーの準備が完了。コピー処理に移行する
14, 1, 1, R, 21 # 1を読んだので1をコピーする。上記の処理と同様
  21, 0, 1, R, 22 # read marker を置く
  22, 0, 0, R, 23 # copied space は読み飛ばす
  22, 1, 1, R, 23
  23, 0, 0, R, 22 # marker space が0のうちは読み飛ばす
  23, 1, 1, R, 24 # 右端のmarkerに到達
  24, 0, 1, R, 25 # ...[1] を ...[1][1](1)[1] とするためここは1にする
  25, 0, 1, R, 26 # ...[1][1](1)
  26, 0, 1, L, 27 # ...[1][1](1)[1] とした。これでコピーの準備が完了。コピー処理に移行する

# コピー処理
  # まずは左端に移動
  27, 0, 0, L, 28 # new copied space は読み飛ばす
  27, 1, 1, L, 28
  28, 0, 0, L, 27 # new marker space が0のうちは読み飛ばす
  28, 1, 1, L, 29 # new marker space の左端に到達
  29, 1, 1, L, 30 # old marker space の右端
  30, 0, 0, L, 31 # old copied space は読み飛ばす
  30, 1, 1, L, 31
  31, 0, 0, L, 30 # old marker space が0のうちは読み飛ばす
  31, 1, 0, R, 32 # read marker に到達
  # 先頭のビットをコピー
  32, 0, 0, R, 33 # 0を読んだので0をコピーする
    33, 0, 1, R, 34 # read marker を置く
    33, 1, 1, R, 49 # read marker が old marker space の右端に到達。最後のコピー(0)に移行
    34, 0, 0, R, 35 # old copied space は読み飛ばす
    34, 1, 1, R, 35
    35, 0, 0, R, 34 # old marker space が0のうちは読み飛ばす
    35, 1, 1, R, 36 # old marker space の右端に到達
    36, 1, 1, R, 37 # new marker space の左端
    37, 0, 0, R, 38 # new copied space は読み飛ばす
    37, 1, 1, R, 38
    38, 0, 0, R, 37 # new marker space が0のうちは読み飛ばす
    38, 1, 0, R, 39 # new marker space の右端に到達。...[1] => ...[0](0)[1]とするためここは0にする
    39, 0, 0, R, 40 # ...[0](0)
    40, 0, 1, L, 27 # ...[0](0)[1]としたのでこのビットのコピーが完了。次のビットのコピーへ移行
  32, 1, 1, R, 41 # 1を読んだので1をコピーする。上記と同様
    41, 0, 1, R, 42 # read marker を置く
    41, 1, 1, R, 54 # read marker が old marker space の右端に到達。最後のコピー(1)に移行
    42, 0, 0, R, 43 # old copied space は読み飛ばす
    42, 1, 1, R, 43
    43, 0, 0, R, 42 # old marker space が0のうちは読み飛ばす
    43, 1, 1, R, 44 # old marker space の右端に到達
    44, 1, 1, R, 45 # new marker space の左端
    45, 0, 0, R, 46 # new copied space は読み飛ばす
    45, 1, 1, R, 46
    46, 0, 0, R, 45 # new marker space が0のうちは読み飛ばす
    46, 1, 0, R, 47 # new marker spaceの右端に到達。...[1] => ...[0](1)[1]とするためここは0にする
    47, 0, 1, R, 48 # ...[0](1)
    48, 0, 1, L, 27 # ...[0](1)[1]としたのでこのビットのコピーが完了。次のビットのコピーへ移行
  # 最後のコピー(0)
  49, 1, 1, R, 50 # new marker space の左端
  50, 0, 0, R, 51 # new copied space は読み飛ばす
  50, 1, 1, R, 51
  51, 0, 0, R, 50 # new marker space が0のうちは読み飛ばす
  51, 1, 0, R, 52 # new marker space の右端に到達。...[1] => ...[0](0)[1]とするためここは0にする
  52, 0, 0, R, 53 # ...[0](0)
  53, 0, 1, L, 59 # ...[0](0)[1]としたのでコピーが完了。old marker space の削除処理に移行
  # 最後のコピー(1)
  54, 1, 1, R, 55 # new marker space の左端
  55, 0, 0, R, 56 # new copied space は読み飛ばす
  55, 1, 1, R, 56
  56, 0, 0, R, 55 # new marker space が0のうちは読み飛ばす
  56, 1, 0, R, 57 # new marker space の右端に到達。...[1] => ...[0](1)[1]とするためここは0にする
  57, 0, 1, R, 58 # ...[0](1)
  58, 0, 1, L, 59 # ...[0](1)[1]としたのでコピーが完了。old marker space の削除処理に移行

# old marker space の削除処理
  # 左端へ移動
  59, 0, 0, L, 60 # new copied space は読み飛ばす
  59, 1, 1, L, 60
  60, 0, 0, L, 61 # new marker space が0のうちは読み飛ばす
  61, 0, 0, L, 60 # new copied space は読み飛ばす
  61, 1, 1, L, 60
  60, 1, 1, L, 62 # new marker space の左端に到達
  62, 1, 1, L, 63 # old marker space の右端
  63, 0, 0, L, 64 # old copied space は読み飛ばす
  63, 1, 1, L, 64
  64, 0, 0, L, 63 # old marker space が0のうちは読み飛ばす
  64, 1, 1, R, 65 # old marker space の左端に到達。先頭ビットの処理に移行
  # 先頭ビットの処理
  65, 0, 1, L, 66 # old copied space の先頭が0。[1](0)... => 0[1]...とするためここは1にしておく
  66, 1, 0, R, 67 # 0[1]...とした(左側のビットを0にした)
  67, 1, 1, R, 68 # 0[1]の右に移動し、左シフト処理へ移行
  65, 1, 1, R, 68 # old copied space の先頭が1。[1](1)... => 1[1]...とそのままで左シフト処理へ移行
  # 左シフト
  68, 0, 0, R, 69 # 不要な old marker space を読み飛ばす
  68, 1, 0, R, 81 # old marker space の右端に到達。最後の2個左シフト処理へ移行(ここは0にしておく)
  69, 0, 0, R, 72 # old copied space の0を読んだ => すでに左のビットは0なので次のold marker spaceを読みに行く
  69, 1, 1, L, 70 # old copied space の1を読んだ => 左のビットを1にするため左へ
  70, 0, 1, R, 71 # (1)<1>とした
  71, 1, 0, R, 72 # (1)<0>としておく。ここの<0>には意味が無いので簡単のため 69, 0 の場合と合わせておく
  72, 0, 0, R, 69 # old marker space の0を読んだ => すでに左のビットは0なので次のold copied spaceを読みに行く
  72, 1, 1, L, 73 # old marker space の1を読んだ => 左のビットを1にするため左へ
  73, 0, 1, R, 74 # [1]<1>とした
  74, 1, 1, R, 75 # [1][1]とした(次のビットはnew marker spaceの左端の1なのでこれでよい)
  75, 1, 0, R, 76 # [1][1][1] => [1][1]<0> としておいて、次のnew copied spaceを読みに行く
  76, 0, 0, R, 79 # new copied space の0を読んだ => すでに左のビットは0なので次のnew marker spaceを読みに行く
  76, 1, 1, L, 77 # new copied space の1を読んだ => 左のビットを1にするため左へ
  77, 0, 1, R, 78 # (1)<1>とした
  78, 1, 0, R, 79 # (1)<0>として次のnew marker spaceを読みに行く
  79, 0, 0, R, 76 # new marker space の0を読んだ => すでに左のビットは0なので次のnew copied spaceを読みに行く
  79, 1, 0, L, 80 # new marker space の1を読んだ => 右端に到達。ここは0にして左を1にしにいく
  80, 0, 1, L, 59 # 左を1にして完了。左端に移動する処理に戻る(ここは右端のnew marker spaceなので1つ左はnew copied space)
  # 最後の2個左シフト(ここは2桁ずつ変えていく)
  81, 1, 0, R, 82 # ...[1]<0>[1](*)[*] => ...[1]<0><0>(*)[*] とする(最初の<0>は68, 1のときに0にしたやつ)
  82, 0, 0, R, 83 # new copied space の0を読んだ
    83, 0, 0, R, 82 # (0)[0]を読んだ => すでに<0><0>(0)[0]となっているので次の2ビットを読みに行く
    83, 1, 0, L, 84 # (0)[1]を読んだ => <0><0>(0)[1] => [0](1) 0 0 とする。
      84, 0, 0, L, 85 # <0><0>(0)[0] (右から2番目を読み飛ばして左へ)
      85, 0, 1, L, 4  # (0)[1] 0  0 とした。new marker spaceが1 => 終わりなので1を足す処理に戻る
  82, 1, 1, R, 86 # new copied space の1を読んだ
    86, 0, 0, L, 87 # (1)[0]を読んだ => <0><0>(1)[0] を (1)[0]<0><0> と変えに行く
      87, 1, 0, L, 88 # <0><0>(0)[0] とした
      88, 0, 0, L, 89 # <0><0>(0)[0] (右から3番目を読み飛ばして左へ)
      89, 0, 1, R, 90 # (1)[0]<0><0> とした
      90, 0, 0, R, 82 # (1)[0]<0><0> 左から2番目を読み飛ばして右へ。ここで82に飛ぶと<0><0>を読み飛ばしてくれる
    86, 1, 0, L, 91 # (1)[1]を読んだ => <0><0>(1)[1] を (1)[1] 0 0 として終わりたいが..
      91, 1, 0, L, 92 # 0 0 0 0 とした
      92, 0, 1, L, 93 # 0 1 0 0 とした
      93, 0, 0, L, 5  # 0 1 0 0 のままで5にジャンプ。 (1)[1] 0 0 とした上で(1)に1を足し始めたことにする

(状態を53個使うと言ったな。あれは嘘だ)

何度同じコード書かされるんだ。。サブルーチンという概念のありがたみがよくわかります。

実行

Elixirで動作するシミュレータを作ったのでそれで動かします。上のコードもそれ用のフォーマットにしてあります。

$ git clone git@github.com:SekiT/ex_tm.git
$ cd ex_tm
$ mix deps.get
$ vi champernowne2.tm # 上のコードをコピペしときます
$ iex -S mix
Erlang/OTP 19 [erts-8.2] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Interactive Elixir (1.4.0) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> machine = %TuringMachine{}
%TuringMachine{accept_states: ["A"], initial_tape: &TuringMachine.zero_tape/1,
 position: 0, state: "0", tape_hash: %{}}
iex(2)> program = TuringMachine.Program.from_file("./champernowne2.tm")
[{"0", "0", "1", :right, "1"}, {"1", "0", "1", :right, "2"},
 {"2", "0", "1", :right, "3"}, {"3", "0", "1", :left, "4"},
 {"4", "0", "1", :left, "12"}, {"4", "1", "0", :left, "5"},
...
iex(3)> machine |> TuringMachine.step_times(program, 1000) |> TuringMachine.slice_tape(0, 20)
["1", "1", "0", "1", "1", "1", "0", "0", "1", "0", "1", "1", "1", "0", "1", "1",
 "1", "1", "0", "0", "0"]

見事に 110111001011101111000... という出力が得られています。

まとめ(?)

marker space と copied space を使うという手法はTuringMachineの世界では割と汎用的に使えるのではないかと思います
一箇所修正するだけで全体を直さなければならなくなるプログラミングは地獄の苦しみです。ちゃんとカプセル化しましょう
極力コメントの要らないプログラムを書くことが大事ですが、それが出来ない言語ではコメントの力は絶大です。これなしではデバッグ出来ませんでした