平成29年度 技術士第二次試験問題【必須科目】
【16】情報工学部門
T−13
チューリングマシンのシミュレータにおいて、オートマトンとテープが与えられている。
これを実行して停止状態になったときのテープの値として、最も適切なものは
どれか。ここで、文字 b は空白を、状態 h は停止を意味し、最初のへッド位置と
内部状態は図に示すとおりとする。

[オートマトン]

┌─────┬─────┬─────┬─────┬─────┐
│ 現在の │ 現在の │ テープに │  次の  │  移動  │
│ 内部状態 │テープの値│ 書込む値 │ 内部状態 │  方向  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  b  │  1  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  0  │  1  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  1  │  0  │  0  │  L  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  b  │  b  │  h  │  L  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  0  │  0  │  1  │  R  │
├─────┼─────┼─────┼─────┼─────┤
│  1  │  1  │  1  │  1  │  R  │
└─────┴─────┴─────┴─────┴─────┘

[テープ]

 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┐
 │b│b│b│1│1│1│1│b│b│
 └─┴─┴─┴─┴─┴─┴─┴─┴─┘
              △
             ┌─┐
             │0│
             └─┘
             ヘッド

 @ b b b 0 0 0 0 b b
 A b b b 1 1 1 0 b b
 B b b b 0 1 1 1 b b
 C b b 1 0 0 0 0 b b
 D b b 1 1 1 1 0 b b



【正解】 C

最初の状態は、
現在の内部状態が0、現在のテープの値1であるので、
オートマトンに従って、テープに
を書き込み、内部状態が0となり
ヘッドは、L、すなわち、左に動く。
以降、順に
内部状態:0、テープ値:1 → テープ:
、内部状態:0、ヘッド左
内部状態:0、テープ値:1 → テープ:
、内部状態:0、ヘッド左
内部状態:0、テープ値:1 → テープ:
、内部状態:0、ヘッド左
内部状態:0、テープ値:b → テープ:
、内部状態:1、ヘッド右
内部状態:1、テープ値:
 → テープ:、内部状態:1、ヘッド右
内部状態:1、テープ値: → テープ:、内部状態:1、ヘッド右
内部状態:1、テープ値: → テープ:、内部状態:1、ヘッド右
内部状態:1、テープ値:b → テープ:b、内部状態:h、ヘッド左

この結果テープの値は以下のとおりとなる。
 b b
b b

EXCEL VBAのご相談なら ファーストマクロ 



T−12 目次 T−14
ファーストマクロ TOPページ