チューリングマシンのシミュレータにおいて、オートマトンとテープが与えられている。
これを実行して停止状態になったときのテープの値として、最も適切なものは
どれか。ここで、文字 b は空白を、状態 h は停止を意味し、最初のへッド位置と
内部状態は図に示すとおりとする。
［オートマトン］
┌─────┬─────┬─────┬─────┬─────┐
│ 現在の │ 現在の │ テープに │ 次の │ 移動 │
│ 内部状態 │テープの値│ 書込む値 │ 内部状態 │ 方向 │
├─────┼─────┼─────┼─────┼─────┤
│ ０ │ ｂ │ １ │ １ │ Ｒ │
├─────┼─────┼─────┼─────┼─────┤
│ ０ │ ０ │ １ │ １ │ Ｒ │
├─────┼─────┼─────┼─────┼─────┤
│ ０ │ １ │ ０ │ ０ │ Ｌ │
├─────┼─────┼─────┼─────┼─────┤
│ １ │ ｂ │ ｂ │ ｈ │ Ｌ │
├─────┼─────┼─────┼─────┼─────┤
│ １ │ ０ │ ０ │ １ │ Ｒ │
├─────┼─────┼─────┼─────┼─────┤
│ １ │ １ │ １ │ １ │ Ｒ │
└─────┴─────┴─────┴─────┴─────┘
［テープ］
┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ｂ│ｂ│ｂ│１│１│１│１│ｂ│ｂ│
└─┴─┴─┴─┴─┴─┴─┴─┴─┘
△
┌─┐
│０│
└─┘
ヘッド
① ｂ ｂ ｂ ０ ０ ０ ０ ｂ ｂ
② ｂ ｂ ｂ １ １ １ ０ ｂ ｂ
③ ｂ ｂ ｂ ０ １ １ １ ｂ ｂ
④ ｂ ｂ １ ０ ０ ０ ０ ｂ ｂ
⑤ ｂ ｂ １ １ １ １ ０ ｂ ｂ
最初の状態は、
現在の内部状態が０、現在のテープの値１であるので、
オートマトンに従って、テープに０を書き込み、内部状態が０となり
ヘッドは、Ｌ、すなわち、左に動く。
以降、順に
内部状態：０、テープ値：１ → テープ：０、内部状態：０、ヘッド左
内部状態：０、テープ値：１ → テープ：０、内部状態：０、ヘッド左
内部状態：０、テープ値：１ → テープ：０、内部状態：０、ヘッド左
内部状態：０、テープ値：ｂ → テープ：１、内部状態：１、ヘッド右
内部状態：１、テープ値：０ → テープ：０、内部状態：１、ヘッド右
内部状態：１、テープ値：０ → テープ：０、内部状態：１、ヘッド右
内部状態：１、テープ値：０ → テープ：０、内部状態：１、ヘッド右
内部状態：１、テープ値：ｂ → テープ：ｂ、内部状態：ｈ、ヘッド左
この結果テープの値は以下のとおりとなる。
ｂ ｂ １ ０ ０ ０ ０ ｂ ｂ
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：オートマトン
