グーグル：チューリングマシン　解法

グーグル：チューリングマシン　解法

TOPへ戻る

第1ステージ
	青丸の再生ボタンを１回押してスタート。ボタン横の赤い数字は、押した回数。ボタンを押した後、再生ボタンを押す。 ×や／印のボタンは、押さなくて良い。解法の原理の誤りはあしからず。

テープ内の２進数「０００１０」を、「０１０１１」に書き替えよ、と言う問題です。押すたびに、０と１に変わるボタンが２つ有ります。　　左向きの矢印１つと、右向きが３つ有ります。再生ボタンを押すと、０を示した中央のヘッドは、まず左矢印に従いヘッドより１つ左の数字である「０」に移動します。（この時のテープは右回転）問題の２進数は「０１０１１」だから、ヘッドより１つ左の数字は、「１」でなくてはいけません。　左側のボタンを１回押して「１」に変えます。左矢印に従いヘッドより１つ左の数字に移動した後は、その位置から３つの右矢印に従い右側３つ目の位置（１つ目は０、２つ目は１、３つ目は０）に移動します。右に３つ移動した値は０だとダメなので、右側のボタンを１回押して「１」に書き替えます。再生時の動作は、指示図の左から右へ。

１つのボタンがあり、押すたびに「□」内の数字が１、空っぽ、０に変わります。左矢印に従いヘッドより１つ左にテープが移動すると、そこは何もなく空っぽです。ボタン下の数字は「０」だから、空っぽの時は「０」を書き込む指示を与えるため、ボタンを２回押します。このボタンは、条件を与える指示です。状態が？ならば、ボタン内の矢印が記す方向に書かれた動作を行う。テープが左に１つ移動した値は空っぽだから、ボタンを２回押して□にすることで、「空っぽの時は、ボタン下には０と書かれているから、そのとおりに０を書き込む」動作を行うように指示を与える。

ヘッドの値は０だから、「条件：１ならば・・・・」は３つとも合致しません。左矢印により、左に１つ移動。　この時のヘッド数値は、「１」豚の鼻の様なボタンがあります。　押すたびに上に伸びている横棒が移動します。初期の状態では、条件：「□」内の数字が１を記した位置にあります。　この状態だと、ヘッドより１つ左に移動したときのテープ数字は「１」だから、「１」ならば右に２つ移動で終ります。ボタンを１回押せば横棒が１つ移動します。　条件：「□」内の数字が１を記しています。　ヘッドより１つ左に移動したときの数字は「１」だから、「１」ならば右に３つ移動で終ります。ボタンを２回押せば横棒が２つ移動します。　同様に条件：「□」内の数字が１を記しています。　ヘッドより１つ左に移動したときの数字は「１」だから、「１」ならば「０」に書き替え、右に３つ移動して終了します。

左矢印により、左に１つ移動。　この時のヘッド数値は、「１」条件ボタンの「□」内が１だと、ヘッドより１つ左に移動したときのテープ数字は「１」だから、「１」だと右に１つ移動し、その数字を０にします。「□」内が空っぽだと、ヘッドより１つ左に移動したときの数字は空っぽではないから、ボタン右側の豚の鼻のような記号上に伸びる横線が左矢印に伸びているため、テープは左移動を繰り返し空っぽのテープ位置を見つけます。３つ移動すれば空っぽのテープ位置があり、その位置に来れば右に１つ移動して、その位置の数字「１」を「０」に書き替えます。豚の鼻のようなものは、条件を満たすまで指示された動作（この場合は左移動）を繰り返す命令です。ちなみに、条件ボタンを「０」にすればどうなるでしょうか？ヘッドより１つ左に移動したときの数字は０ではないから、繰り返しによって「０」を探し続ける無限ループに陥ります。　実際に試すと、「０」を探し続ける動作を行い、数秒して停止します。

左矢印が２つ有るから、テープが２つ移動したときの値は「０」です。条件ボタンの「□」内が０だと「１」に書き替えられるから間違いです。　さらに繰り返し命令にて、他の０も１に変えてしまいます。（右に２回移動した数値０は１に書き替えられ、下段条件、数値１の時は右移動で残りの０も１に書き替え）条件ボタンの「□」内が１だと「１」に書き替える指示は、テープの値「０」に対しては無意味で、繰り返し命令にても他の０も１に変えることは出来ません。ボタンの「□」内を空っぽにします。テープが２つ移動したときの値は「０」だから、ボタンの「□」内が空っぽにすれば条件が合いません。ただし、繰り返し命令によって空っぽの部分を１に変える動作を行います。　下段条件、数値１の時は右移動。　移動後の数字は空っぽではなく０だからそのまま。　空っぽのテープを見つけるまで右移動を繰り返すが、次の数値も０だからそのまま。　右端の数値は１、さらに空っぽのテープを探す繰り返しを行うと思いきや、上段繰り返し指示の左に条件、数値１ならば空の丸（動作終了）

下段のボタンを変更します。左矢印が２つ有るから、テープが２つ移動したときの値は「０」です。下段０ボタンを１にすることで、条件より０の値は「１」に書き替えられます。繰り返しにより０の時は１に書き替える動作を繰り返しますが、残りの数字はすべて「１」です。この残りの１を「０」にしなくてはいけないので、下段条件ボタンの「□」内０を「１」にします。上段０ボタンがあるから、下段ボタンの「□」内０を「１」にすることで、「１」ならば右移動、かつ「１」を「０」に書き替える動作を続けます。　最終空っぽのテープを見つけると終了。＊＊上段の「□」内０のボタンを□１にして、０のボタンを１にしても良いでしょう。＊＊この場合は、テープが２つ移動したときの値「０」を「１」に変更したボタンの影響で「１」に書き替えます。　□１に変更したボタンにて条件１を０に変える動作を繰り返す。　下段条件０の時は右に移動。　　最終空っぽのテープを見つけると終了。
第2ステージ（解法はボタン操作を行った後のもの）

上段繰り返し命令にて左移動を繰り返す。　上段条件、テープが空の時は右移動して「０」に書き替える。（繰り返しで３コマ移動すると空っぽだから、下段を参照し、右に1つ移動して１を０に書き替える）さらに下段参照にて右に１つ移動。　下段繰り返しにて、下段条件、「空っぽなら左移動」に合致するまで右移動。右端の0の隣の空っぽまで移動すると条件に合致するから、テープは左に移動して、上段を参照しその位置の０を「１」に書き替え。

上段、「条件：1なら何もしない」に見合うまで左移動。１つ左に移動すると条件に合致した１が有るから何もしない。下段参照、１を「０」に書き替え。下段参照、「条件：１ならば左移動」まで右移動を繰り返し。テープ右端の数値は「１」だから条件に合致して１つ左移動。上段参照、左移動した数値「０」を「１」に書き替え。上段参照、さらに左移動して「空っぽ」の部分に「０」を書き込む。

上段、再生ボタンのすぐ右の「条件：空っぽならば１を書き込む」は、条件に満たないからそのまま。上段、「１に書き替え」は、現テープ数値が１だから「１」を「１」に書き替える結果に。上段、左に1つ移動。上段、「条件：０ならば０を書き込む」は、左移動した数値は０だから同「０」に書き替える結果に。下段、右に1つ移動。下段、「条件：空っぽならば左に1つ移動」は、条件に満たない。下段、０に書き替え（現テープ数値１を０に書き替え）下段、「条件：空っぽならば１を書き込む」は、条件に満たない。

下段、２つの「条件：空っぽならば何もしない」は、条件に満たない。上段、２つの「条件：空っぽならば何もしない」は、条件に満たない。上段、左に１つ、右に1つ各移動。上段、左に１つ、右に1つ各移動。

上段、2つの左矢印にて、左に２つ移動。上段、「条件：０ならば空っぽならば？？？」条件同士が衝突し合って意味がわからない。下段、「条件：空っぽならば０ならば？？？」に見合うまで右移動。　１つ右移動すると空のテープがある。上段、空のテープに「１」を書き込む。上段、右に1つ移動。上段、「条件：空っぽの時は何もしない」は、条件に満たない。上段、繰り返し。上段、「条件：０ならば空っぽならば？？？」条件同士が衝突し合って意味がわからない。下段、「条件：空っぽならば０ならば？？？」に見合うまで右移動。　２つ右移動すると空のテープがある。上段、空のテープに「１」を書き込む。上段、右に1つ移動。上段、「条件：空っぽの時は何もしない」で終了。

上段、「条件：１の時は０を書き込む」は、条件に満たない。上段、右に1つ移動上段、「条件：空っぽの時は左１つ移動」は、条件に満たない。上段、繰り返し上段、「条件：１の時は０を書き込む」は、条件に満たない。上段、右に1つ移動上段、「条件：空っぽの時は左１つ移動」は、条件に満たない。上段、繰り返し上段、「条件：１の時は０を書き込む」は、この時点で合致。下段、左に1つ移動して１に書き替え。下段、左に1つ移動。下段、「条件：０の時は動作を繰り返し」は、この時点でのテープは０だから条件に合致。繰り返し動作にて数値が書き替えられて終了。
	完成

第1ステージ
	青丸の再生ボタンを１回押してスタート。ボタン横の赤い数字は、押した回数。ボタンを押した後、再生ボタンを押す。 ×や／印のボタンは、押さなくて良い。解法の原理の誤りはあしからず。

テープ内の２進数「０００１０」を、「０１０１１」に書き替えよ、と言う問題です。押すたびに、０と１に変わるボタンが２つ有ります。　　左向きの矢印１つと、右向きが３つ有ります。再生ボタンを押すと、０を示した中央のヘッドは、まず左矢印に従いヘッドより１つ左の数字である「０」に移動します。（この時のテープは右回転）問題の２進数は「０１０１１」だから、ヘッドより１つ左の数字は、「１」でなくてはいけません。　左側のボタンを１回押して「１」に変えます。左矢印に従いヘッドより１つ左の数字に移動した後は、その位置から３つの右矢印に従い右側３つ目の位置（１つ目は０、２つ目は１、３つ目は０）に移動します。右に３つ移動した値は０だとダメなので、右側のボタンを１回押して「１」に書き替えます。再生時の動作は、指示図の左から右へ。

１つのボタンがあり、押すたびに「□」内の数字が１、空っぽ、０に変わります。左矢印に従いヘッドより１つ左にテープが移動すると、そこは何もなく空っぽです。ボタン下の数字は「０」だから、空っぽの時は「０」を書き込む指示を与えるため、ボタンを２回押します。このボタンは、条件を与える指示です。状態が？ならば、ボタン内の矢印が記す方向に書かれた動作を行う。テープが左に１つ移動した値は空っぽだから、ボタンを２回押して□にすることで、「空っぽの時は、ボタン下には０と書かれているから、そのとおりに０を書き込む」動作を行うように指示を与える。

ヘッドの値は０だから、「条件：１ならば・・・・」は３つとも合致しません。左矢印により、左に１つ移動。　この時のヘッド数値は、「１」豚の鼻の様なボタンがあります。　押すたびに上に伸びている横棒が移動します。初期の状態では、条件：「□」内の数字が１を記した位置にあります。　この状態だと、ヘッドより１つ左に移動したときのテープ数字は「１」だから、「１」ならば右に２つ移動で終ります。ボタンを１回押せば横棒が１つ移動します。　条件：「□」内の数字が１を記しています。　ヘッドより１つ左に移動したときの数字は「１」だから、「１」ならば右に３つ移動で終ります。ボタンを２回押せば横棒が２つ移動します。　同様に条件：「□」内の数字が１を記しています。　ヘッドより１つ左に移動したときの数字は「１」だから、「１」ならば「０」に書き替え、右に３つ移動して終了します。

左矢印により、左に１つ移動。　この時のヘッド数値は、「１」条件ボタンの「□」内が１だと、ヘッドより１つ左に移動したときのテープ数字は「１」だから、「１」だと右に１つ移動し、その数字を０にします。「□」内が空っぽだと、ヘッドより１つ左に移動したときの数字は空っぽではないから、ボタン右側の豚の鼻のような記号上に伸びる横線が左矢印に伸びているため、テープは左移動を繰り返し空っぽのテープ位置を見つけます。３つ移動すれば空っぽのテープ位置があり、その位置に来れば右に１つ移動して、その位置の数字「１」を「０」に書き替えます。豚の鼻のようなものは、条件を満たすまで指示された動作（この場合は左移動）を繰り返す命令です。ちなみに、条件ボタンを「０」にすればどうなるでしょうか？ヘッドより１つ左に移動したときの数字は０ではないから、繰り返しによって「０」を探し続ける無限ループに陥ります。　実際に試すと、「０」を探し続ける動作を行い、数秒して停止します。

左矢印が２つ有るから、テープが２つ移動したときの値は「０」です。条件ボタンの「□」内が０だと「１」に書き替えられるから間違いです。　さらに繰り返し命令にて、他の０も１に変えてしまいます。（右に２回移動した数値０は１に書き替えられ、下段条件、数値１の時は右移動で残りの０も１に書き替え）条件ボタンの「□」内が１だと「１」に書き替える指示は、テープの値「０」に対しては無意味で、繰り返し命令にても他の０も１に変えることは出来ません。ボタンの「□」内を空っぽにします。テープが２つ移動したときの値は「０」だから、ボタンの「□」内が空っぽにすれば条件が合いません。ただし、繰り返し命令によって空っぽの部分を１に変える動作を行います。　下段条件、数値１の時は右移動。　移動後の数字は空っぽではなく０だからそのまま。　空っぽのテープを見つけるまで右移動を繰り返すが、次の数値も０だからそのまま。　右端の数値は１、さらに空っぽのテープを探す繰り返しを行うと思いきや、上段繰り返し指示の左に条件、数値１ならば空の丸（動作終了）

下段のボタンを変更します。左矢印が２つ有るから、テープが２つ移動したときの値は「０」です。下段０ボタンを１にすることで、条件より０の値は「１」に書き替えられます。繰り返しにより０の時は１に書き替える動作を繰り返しますが、残りの数字はすべて「１」です。この残りの１を「０」にしなくてはいけないので、下段条件ボタンの「□」内０を「１」にします。上段０ボタンがあるから、下段ボタンの「□」内０を「１」にすることで、「１」ならば右移動、かつ「１」を「０」に書き替える動作を続けます。　最終空っぽのテープを見つけると終了。＊＊上段の「□」内０のボタンを□１にして、０のボタンを１にしても良いでしょう。＊＊この場合は、テープが２つ移動したときの値「０」を「１」に変更したボタンの影響で「１」に書き替えます。　□１に変更したボタンにて条件１を０に変える動作を繰り返す。　下段条件０の時は右に移動。　　最終空っぽのテープを見つけると終了。
第2ステージ（解法はボタン操作を行った後のもの）

上段繰り返し命令にて左移動を繰り返す。　上段条件、テープが空の時は右移動して「０」に書き替える。（繰り返しで３コマ移動すると空っぽだから、下段を参照し、右に1つ移動して１を０に書き替える）さらに下段参照にて右に１つ移動。　下段繰り返しにて、下段条件、「空っぽなら左移動」に合致するまで右移動。右端の0の隣の空っぽまで移動すると条件に合致するから、テープは左に移動して、上段を参照しその位置の０を「１」に書き替え。

上段、「条件：1なら何もしない」に見合うまで左移動。１つ左に移動すると条件に合致した１が有るから何もしない。下段参照、１を「０」に書き替え。下段参照、「条件：１ならば左移動」まで右移動を繰り返し。テープ右端の数値は「１」だから条件に合致して１つ左移動。上段参照、左移動した数値「０」を「１」に書き替え。上段参照、さらに左移動して「空っぽ」の部分に「０」を書き込む。

上段、再生ボタンのすぐ右の「条件：空っぽならば１を書き込む」は、条件に満たないからそのまま。上段、「１に書き替え」は、現テープ数値が１だから「１」を「１」に書き替える結果に。上段、左に1つ移動。上段、「条件：０ならば０を書き込む」は、左移動した数値は０だから同「０」に書き替える結果に。下段、右に1つ移動。下段、「条件：空っぽならば左に1つ移動」は、条件に満たない。下段、０に書き替え（現テープ数値１を０に書き替え）下段、「条件：空っぽならば１を書き込む」は、条件に満たない。

下段、２つの「条件：空っぽならば何もしない」は、条件に満たない。上段、２つの「条件：空っぽならば何もしない」は、条件に満たない。上段、左に１つ、右に1つ各移動。上段、左に１つ、右に1つ各移動。

上段、2つの左矢印にて、左に２つ移動。上段、「条件：０ならば空っぽならば？？？」条件同士が衝突し合って意味がわからない。下段、「条件：空っぽならば０ならば？？？」に見合うまで右移動。　１つ右移動すると空のテープがある。上段、空のテープに「１」を書き込む。上段、右に1つ移動。上段、「条件：空っぽの時は何もしない」は、条件に満たない。上段、繰り返し。上段、「条件：０ならば空っぽならば？？？」条件同士が衝突し合って意味がわからない。下段、「条件：空っぽならば０ならば？？？」に見合うまで右移動。　２つ右移動すると空のテープがある。上段、空のテープに「１」を書き込む。上段、右に1つ移動。上段、「条件：空っぽの時は何もしない」で終了。

上段、「条件：１の時は０を書き込む」は、条件に満たない。上段、右に1つ移動上段、「条件：空っぽの時は左１つ移動」は、条件に満たない。上段、繰り返し上段、「条件：１の時は０を書き込む」は、条件に満たない。上段、右に1つ移動上段、「条件：空っぽの時は左１つ移動」は、条件に満たない。上段、繰り返し上段、「条件：１の時は０を書き込む」は、この時点で合致。下段、左に1つ移動して１に書き替え。下段、左に1つ移動。下段、「条件：０の時は動作を繰り返し」は、この時点でのテープは０だから条件に合致。繰り返し動作にて数値が書き替えられて終了。
	完成