計算機を作ろう その⑤
続きです。
前回はこちら
uso-800-plus-alpha.hatenablog.com
今回は、経路分けについて考えます。実質最終回です。
まずは、下図の赤枠のところを考えてみます。
この図では0（=スイッチON, OFF）ですが、1（=スイッチOFF, ON）のときも含めて、それぞれの場合で何が起こるのかを確かめてみます。
(a) 攻方持駒：桂、スイッチON, OFFの場合
スタート地点から出発し、スイッチ0かスイッチ1に上から進入します。
このとき、OFFであるスイッチ1に進入すると不詰となってしまうので、攻方はスイッチ0を選択して進入します。
次に、桂ーと歩ーの選択ですが、持駒に歩が無いので、桂ーのほうへ入ることになります。
つまり、(a)では一番左のルートが選択されることになります。
(b) 攻方持駒：歩、スイッチON, OFFの場合
同様に考えると、(b)では左から2番目のルートを選ぶしかありません。
(c) 攻方持駒：桂、スイッチOFF, ONの場合
同様に考えると、(c)では左から3番目のルートを選ぶしかありません。
(d) 攻方持駒：歩、スイッチOFF, ONの場合
同様に考えると、(d)では一番右のルートを選ぶしかありません。
これで、内部状態とテープ記号の全ての組み合わせに対してルート分岐を用意することができました。
この瞬間、(a)～(d)全てで、全スイッチがOFFの状態になっています。この後はテープ記号の書き換えに対応したスイッチをONにしに行きます。
（そうすれば、「ひとつだけONで残りはOFF」の状態を維持することができます）
今回お題としたチューリングマシンをよく見ると、全パターンでテープ記号を1に書き換えています。つまり、全4ルートが、それぞれスイッチ1をONにしに行くということになります。
スイッチをONにするには、下から進入しなければなりません。が、スイッチ下部に入口はひとつしか無いため、一旦分岐させた4ルートをひとつに集めてやる必要が出てきます。
せっかく分岐させたので、その情報は失いたくありません。そのため、こうします。
今回は4ルートが合流するため、
1ルート目：桂桂桂
2ルート目：桂桂歩
3ルート目：桂歩歩
4ルート目：歩歩歩
のように、識別用持駒を与えてやります。そうすれば合流しても、どの分岐から来たのか分かるようになります。
そうして、スイッチ1を無事ONにした後に、
識別用持駒を吐き出させて、再度分岐させます。
その後は、次の内部状態用の持駒を渡して、次の行き先へ移動させてやれば完成です。
「詰み」の部分について、Wikipediaでは"1, R, H"と記載してありますが、右マス（=Right）へ渡す理由が分からなかったので、そのまま詰ましています。たぶん議論に影響は出ないんじゃないかと思います。
要するに、「分岐、合流、スイッチON・OFF、持駒による識別を駆使すればよい」という話なのだと思います。
･･･で終わってもたぶん問題ないでしょうが、もう一例挙げてみたいと思います。
続く
