計算機を作ろう その④
続きです。
前回はこちら
uso-800-plus-alpha.hatenablog.com
今回は、チューリングマシンとの対応関係を示します。
２．計算機の構成
さて、チューリングマシンには、「内部状態」と「テープ記号」の2つの状態が必要になります。言い回しというか呼び名が色々あり、媒体により違ったりするのですが、面倒なので統一しません。適宜読み替えてください。
まずは、次のチューリングマシンをお題としましょう。
| A | B | |
|---|---|---|
| 0 | 1,R,B | 1,R,B |
| 1 | 1,L,B | 1,R,H |
の2-状態, 2-記号の優勝者です。
ここでは0, 1はテープ記号、A, Bは内部状態です。
例えば、(0, A)の欄の"1, R, B"は、「テープを"1"に書き換えて、右("R"ight)へ。その際内部状態は"B"に変化する」という意味です。
なお、H記号はHalt(停止)を意味し、この状態になった場合は、計算終了とします。
まずは作成した図面を提示しておきます。
これで、チューリングマシンの1マス分です。これが左右に無限に繋がっているものと考えてください。
（つまり、
こんなです）
終端部には、「右へ」・「左へ」・「詰み」と記載がありますが、それぞれ「右のマスのスタートへ移動」・「左のマスのスタートへ移動」・「詰み」とします。
以下では、チューリングマシンと詰将棋の対応付けの方法について書いていきます。
(a) 内部状態の対応
スタート地点での攻方の持駒を内部状態とします。
今回は2-状態チューリングマシンなので、2つの状態が識別できればよいことになります。
という訳で、
A・・・持駒 桂
B・・・持駒 歩
とします。
これが4-状態チューリングマシンならば、
A・・・持駒 桂桂桂
B・・・持駒 桂桂歩
C・・・持駒 桂歩歩
D・・・持駒 歩歩歩
のように対応させます。
(b) テープ記号
スタート地点でのスイッチのON・OFFで表現します。
例題の場合は、2-記号チューリングマシンなので、スイッチを2つ並べています。
その中の1つのみをONとし、それ以外が全てOFFとなるように設定し、テープ記号と対応させます。2-記号の場合は、
0・・・ON, OFF
1・・・OFF, ON
というイメージです。
なので、上図は0の記号が書き込まれているということになります。
（※スイッチ下部に、0とか1とか書いてありますが、見やすくするためのもので、特に機能はありません。なので、無くてもよいものですし、将棋盤で表現するときには存在しない情報になります）
なお、4-記号チューリングマシンの場合は、
0・・・ON, OFF, OFF, OFF
1・・・OFF, ON, OFF, OFF
2・・・OFF, OFF, ON, OFF
3・・・OFF, OFF, OFF, ON
のような感じです。
続く
uso-800-plus-alpha.hatenablog.com
※一切書くのを忘れていましたが、受方の持駒は「桂×たくさん」、「歩×たくさん」くらいに考えてください。ちゃんと作れば、「全種×たくさん」に出来ると思いますが、分かりにくくなるので･･････
