Universal Turing Machine

なんとなく早起きしてしまったので探しもの。

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