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