本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成29年度 技術士第二次試験問題【必須科目】

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を書き込み、内部状態が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、内部状態:h、ヘッド左

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

T−12 目次 T−14