2014　岩手県立大学　前期総合思考力試験MathJax

【３】　次の文章を読み，あとの問いに答えなさい．

　ヘッドがテープに数字を書き込みながら移動する機械の制御を考える．

　この機械では，ヘッドは${\mathrm{S}}_1\text{〜}{\mathrm{S}}_n$のいずれか$1$つの状態をとり，それぞれの状態のときにルールに基づきテープ上のヘッドが位置する場所に数字を書き込み，左か右に$1$つ場所を移動したのち，状態が変化する．テープ上の各場所の数字は$0$か$1$のいずれかで，$0$のときに$1\text{，}$もしくは$1$のときに$0$を書き込むことを反転，$0$のときに$0\text{，}$もしくは$1$のときに$1$を書き込むことを保持とよぶ．

　状態${\mathrm{S}}_i$のときのルールの書き方を次のように定める．

${\mathrm{S}}_i\text{：}$（書き込み方法，移動方向，次の状態）

　書き込み方法は「反転」，「保持」のいずれか，移動方向は「右」か「左」のいずれか，次の状態は${\mathrm{S}}_1\text{〜}{\mathrm{S}}_n$のいずれかをとる．また，この機械はテープに数字がなにも書かれていない場所にヘッドが移動した場合，動作を停止し，終了状況となる．

　例えば，図１のように，テープの“場所１”にヘッドがあり，ヘッドの状態が${\mathrm{S}}_1\text{，}$“場所１”から“場所６”までのテープの数字が$0$の状況にあるとき，

${\mathrm{S}}_1\text{：}$（反転，右，$S_2$）

というルールに従った動作では，テープの“場所１”の数字に$1$を書き込み，ヘッドを$1$つ右の“場所２”に移動させ，状態を${\mathrm{S}}_2$に変更する．

　図１の状況の機械を，以下の$2$つのルールによって構成されるルール群に従って動作させると，終了状況は図２のようになる．

$\text{ルール群}\{\begin{array}{c}{\mathrm{S}}_1\text{：（反転，右，}{\mathrm{S}}_2\text{）}\\ {\mathrm{S}}_2\text{：（保持，右，}{\mathrm{S}}_1\text{）}\end{array}$

[問１]　図１が開始状況であるとき，機械を以下の$3$つのルールによって構成されるルール群に従って動作させ，終了状況になったときのテープ上の数字，ヘッドの位置と状態を図示しなさい．

$\text{ルール群}\{\begin{array}{c}{\mathrm{S}}_1\text{：（反転，右，}{\mathrm{S}}_2\text{）}\\ {\mathrm{S}}_2\text{：（保持，右，}{\mathrm{S}}_3\text{）}\\ {\mathrm{S}}_3\text{：（反転，左，}{\mathrm{S}}_1\text{）}\end{array}$

[問２]　図３の開始状況のとき，図４を終了状況とするルール群について，次の問いに答えなさい．

(a)　ルール群を校正するルールの数が$6$つ，終了状況におけるヘッドの状態が${\mathrm{S}}_1$であるとき，このルール群を答えなさい．

(b)　ルール群を構成するルールの数が$4$つであるとき，このルール群を答えなさい．ただし終了状況におけるヘッドの状態は${\mathrm{S}}_1\text{〜}{\mathrm{S}}_4$のいずれでもよい．

図３：機械の開始状況	図４：機械の終了状況

[問３]　図５の開始状況のとき，図６を終了状況とするルール群を答えなさい．ただし，ルール群を構成するルールの数は最大$4$つまでとし，終了状況におけるヘッドの状態は${\mathrm{S}}_1\text{〜}{\mathrm{S}}_4$のいずれでもよい．