なんとなく早起きしてしまったので探しもの。
Automaton の授業で Turing Machine までは書いたんだけど、Universal まではできなくて。
非構成的なエンコードで最小状態なんてのもあるらしいですがね。Turing 先生が書いたのもあるはずなんだが。
自分で書こうとすると結構めんどい。なのでググる。と、SLiTeXで書いたのがWikipediaから link されてる。なになに?
0 TM は、こうエンコードする
i 入力をコピーする
ii 遷移条件を線形サーチで見つける
...
などなどの6ステップで1 cycle廻るらしい。移動する時に alphabet を変更して読み込んだマークを付けるらしい。なるほど。
で、その Turing Machine はどこ? まさか、自分で書けって課題? うう。確かに、step 毎は書けそう。自分で課題で出すか?
なんですが、手でURLの後ろ削って上に上がったら UTM のコードを見つけました。74行。割と短い。じゃ、動かしてみるか。
(read0, *, read1, *, L), (read0, ?, read0, ?, R),
(read1, ?, read2, @, R),
(read2, ^, read3, ^, R), (read2, ?, read2, ?, R),
(read3, 0, read4, 0, L), (read3, 1, read5, 1, L), (read3, b, read6, b, L),
(read4, @, loc0, 0, R), (read4, ?, read4, ?, L),
(read5, @, loc0, 1, R), (read5, ?, read5, ?, L),
(read6, @, loc0, B, R), (read6, ?, read6, ?, L),
(loc0, 0, loc0, X, L), (loc0, 1, loc0, Y, L), (loc0, B, loc0, Z, L),
(loc0, $, loc1, $, R), (loc0, ?, loc0, ?, L),
(loc1, X, loc2, 0, R), (loc1, Y, loc3, 1, R), (loc1, Z, loc4, B, R),
(loc1, *, fetch0, *, R), (loc1, ?, loc1, ?, R),
(loc2, 0, loc5, X, R), (loc2, 1, loc6, Y, R), (loc2, B, loc6, Z, R),
(loc2, ?, loc2, ?, R),
(loc3, 1, loc5, Y, R), (loc3, 0, loc6, X, R), (loc3, B, loc6, Z, R),
(loc3, ?, loc3, ?, R),
(loc4, B, loc5, Z, R), (loc4, 0, loc6, X, R), (loc4, 1, loc6, Y, R),
(loc4, ?, loc4, ?, R),
(loc5, $, loc1, $, R), (loc5, ?, loc5, ?, L),
(loc6, $, halt, $, R), (loc6, *, loc0, *, L), (loc6, ?, loc6, ?, R),
(fetch0, 0, fetch1, X, L), (fetch0, 1, fetch2, Y, L),
(fetch0, B, fetch3, Z, L), (fetch0, ?, fetch0, ?, R),
(fetch1, $, fetch4, $, R), (fetch1, ?, fetch1, ?, L),
(fetch2, $, fetch5, $, R), (fetch2, ?, fetch2, ?, L),
(fetch3, $, fetch6, $, R), (fetch3, ?, fetch3, ?, L),
(fetch4, 0, fetch7, X, R), (fetch4, 1, fetch7, X, R),
(fetch4, B, fetch7, X, R), (fetch4, *, print0, *, L),
(fetch4, ?, fetch4, ?, R),
(fetch5, 0, fetch7, Y, R), (fetch5, 1, fetch7, Y, R),
(fetch5, B, fetch7, Y, R), (fetch5, *, print0, *, L),
(fetch5, ?, fetch5, ?, R),
(fetch6, 0, fetch7, Z, R), (fetch6, 1, fetch7, Z, R),
(fetch6, B, fetch7, Z, R), (fetch6, *, print0, *, L),
(fetch6, ?, fetch6, ?, R),
(fetch7, *, fetch0, *, R), (fetch7, ?, fetch7, ?, R),
(print0, X, print1, X, R), (print0, Y, print2, Y, R),
(print0, Z, print3, Z, R),
(print1, ^, print4, ^, R), (print1, ?, print1, ?, R),
(print2, ^, print5, ^, R), (print2, ?, print2, ?, R),
(print3, ^, print6, ^, R), (print3, ?, print3, ?, R),
(print4, ?, print7, 0, L),
(print5, ?, print7, 1, L),
(print6, ?, print7, B, L),
(print7, X, move0, X, R), (print7, Y, move1, Y, R),
(print7, ?, print7, ?, L),
(move0, ^, move2, ^, L), (move0, ?, move0, ?, R),
(move1, ^, move3, ^, R), (move1, ?, move1, ?, R),
(move2, 0, move4, ^, R), (move2, 1, move5, ^, R), (move2, B, move6, ^, R),
(move3, 0, move4, ^, L), (move3, 1, move5, ^, L), (move3, B, move6, ^, L),
(move4, ^, tidy0, 0, L),
(move5, ^, tidy0, 1, L),
(move6, ^, tidy0, B, L),
(tidy0, $, tidy1, $, L), (tidy0, ?, tidy0, ?, L),
(tidy1, X, tidy1, 0, L), (tidy1, Y, tidy1, 1, L), (tidy1, Z, tidy1, B, L),
(tidy1, $, read0, $, R)*, (tidy1, ?, tidy1, ?, L)
Oxford の Rahul Santhanam という人が書いたらしいです。
http://www.inf.ed.ac.uk/teaching/courses/ci/documents/slides05.pdf
普天間のユニゾンカフェのカレーなんですが...
やっぱり、集合論で Kunen 読んでないのまずいよな、なんですが、
