タグシステムとチューリングマシンの変換
Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15–20, 1964. PDF テープに0か1しか書けない2シンボルチューリングマシン
扱いやすいように処理の順番が少し変わっている。まず書く、そして動いて、読んで、状態遷移する。
https://gyazo.com/6aa532eb91ba83783114bc7b3927c99c
テープ
https://gyazo.com/255f33e35d70524c80ed24698fb6f048
無限に長いテープを一つの整数の二進法表記だとみなす
ヘッドを動かす処理がこう書ける
https://gyazo.com/ae438265c9b51b7f8a41158e762673e6
タグシステム
キューの先頭文字によって決まる文字列をキューの末尾に追加し、キューの先頭2つを取り除く仕組み
チューリングマシンのテープの内容を「2文字の繰り返しがN回続いた文字列」で表現する
(テープの長さの指数関数オーダーの文字列になるな…)
具体的にどのような変換をするかは、論文の自然言語での記述をここで自然言語でやり直してもわかりやすくならない。
チューリングマシンの一つの状態が16個のタグルールに変換される
論文に書いてあったRの場合は正しく動いているように見える
一歩右に動いてテープを読んで分岐するだけのチューリングマシンから作られたタグシステムのルール
code::
>> convert({"Q0": (0, "R", "Q1", "Q2")})
0だけのテープで実行すると、確かにQ1に遷移することがわかる
code::
>> run_tag_system({"Q0": (0, "R", "Q1", "Q2")}, "Q0", [], [])
右のテープに1を書き込んでおくとQ2に遷移する
code::
>> run_tag_system({"Q0": (0, "R", "Q1", "Q2")}, "Q0", [], 1) axやbxの繰り返し個数でテープの状態が表現されている
移動して読んだ時に1であるかどうかは、この繰り返し回数が奇数かどうかと一致する
右に移動する時はB x b x b x ...
B -> S, b -> sの変換ルールでここの長さが半分になる
テープが0のときS D1 D0, 1のとき S s D1 D0になる
先頭の2トークンを削ると、先頭がD0とD1になる
左に移動する時は?
https://gyazo.com/fd60f1d5c87f52c04f2d014ae77765df
「変更すべきところを変更せよ」
どこを変更すべきなのか書いてよ…
単純にAとaで詰むトークンを半分にすれば良いか?
Bで再生されるトークンが半分ズレて読まれる可能性が出てくる
右に進む時のルール生成
code::
if move == "R":
if write:
add_rule("A", "C x c x")
else:
add_rule("A", "C x")
add_rule("a", "c x c x")
add_rule("B", "S")
add_rule("b", "s")
...
これを反転したものを左にすると…
code::
elif move == "L": # incorrect impl.
add_rule("A", "C")
add_rule("a", "c")
if write:
add_rule("B", "S x s x")
else:
add_rule("B", "S x")
add_rule("b", "s x")
読まれるべきでないxを読んでしまう
code::
run_tag_system({"Q0": (1, "L", "Q1", "Q2")}, "Q0", [], [])
あ、まずAをBの後ろに回すだけの処理をすれば良いか?
状態が2つ増えてしまうけどそれでできそう、テストは通った