計算機を作ろう その⑥

続きです。

前回はこちら

uso-800-plus-alpha.hatenablog.com

今回は、もう一例構成してみます。

 お題はこちら

Wolfram 2,3 Turing Machine Research Prize

より

解説すると、テープ記号がオレンジ＆黄色＆白の3つ、内部状態が↑＆↓の2つというチューリングマシンです。上の段が書き換え前で、下の段が書き換え後を表しています。例えば一番左のブロックの場合は、「テープ記号：オレンジ・内部状態：↑」でスタートしたことを表していて、書き換え後「テープ記号：黄色、内部状態：↑、移動先：左という結果になるよ」という意味です。

これを取り上げた理由は、このチューリングマシンが、最小の万能チューリングマシンだと言われているためです。

つまり、コレさえ構成可能であれば、詰将棋で任意の計算が行えることにな･･･

･･･りません。よく見ると、このチューリングマシンには、停止状態が存在しません。

ウルフラムも解説記事で、"Note that there is no halt state for this Turing machine."と言っています。したがって、詰将棋として構成しようとしても、「王手が延々と続くけれど、いつまで経っても詰みにならない」というシロモノになってしまいます。

以上！解散！

･･･ひとまず例題として作ってみました。こんな感じです。

※今回もわかりやすいように、スイッチ下部を色分けしてあります。

今回は合流数が3だったり2だったりするため、それぞれのルートで2枚ないし1枚の識別用持駒を持たせるようにしています。それ以外は、おおむね前回と同じような構成方法を用いている（と思います）。

？？？「2-状態, 3-記号の万能チューリングマシンが詰将棋に適さないならば、別の万能チューリングマシンを探せばよいじゃないか！」

確かにそうです。

では、計算終了時にちゃんと停止する最小の万能チューリングマシンは、何状態, 何記号マシンでしょうか？

例えば、Rogozhinの4-状態, 6-記号チューリングマシンが、ある種最小の万能チューリングマシンとされています。しかし、上記のように6分岐でもだいぶ巨大化しているのに、24分岐なんて作って大丈夫なのでしょうか（私が）？

その①で「細かい言い訳が大量にある」と書きましたが、これはその中のひとつです。逆に言えば、主要な部分は書き終えたことを意味しています。

という訳で、まずは文献表を整理するところから始めたいと思います。

続く

uso-800-plus-alpha.hatenablog.com