Turing Machine

Automaton の続きですね。automaton にstack(つまりリスト)を二つ足して。割と簡単に掛けたんですが、

　　プログラムの方法がわからない

アセンブラよりもひどいからなぁ。で、ググって、1が続いているのを反対側に倍にするってのを書いてみました。しかし、

　　Turing Machine のdebugって結構最低

なので、一ステップずつ実行するように書き直したわけですが、ようやっと動いたら

　　15 step / 5 min

おいおい。なんとかならんのと思ったんですが、1 step 実行用に挟んでいたProductをはずして tail call で書いたら

　　15 step は瞬時

になりました。ふーん。Agdaいろいろあるな。なんですが、

　　ここから、Universatl turing machineはかなり遠い

らしい。Turing は構成してみせたらしいんですが、ググっても見当たらないぞ。

たぶんテープ増やして、可変長の状態記述と可変長の状態レジスタを作るんじゃないかな。まぁ、構成して見せたところでどうなるものでもないんですが。

ちなみに、普通の計算機はメモリ有限なのでTMではテープなしでシミュレーションできます。

もう少し Universality が自明なプログラミング機械とかないのかな。

このスライドが結構面白かった。

http://tinyurl.com/yc9ob6to