←講義のツボメニューへ
情報学基礎Ａ
【2000.10.26,31,11.2】 【第７〜９回】 【佐々木 博隆】
チューリング機械
（１）〜（３）
１．チューリング機械（基本）
- テープ
左右無限長で等しい大きさのマス目があり、各マス目には記号を１つ書くことができる。
- ヘッド
一度に１つのマス目の記号を読み取って記号を書き込むことができる。
- プログラム
マス目に書き込む記号やヘッドの移動方向などを決める規則。（関数として記述されている。）
- コントローラ
プログラムを内蔵し、いくつかの状態を記憶することができる。そして、プログラムにしたがってヘッドを制御する。
２．チューリング機械の動作
- 動作開始時
テープにはあらかじめ記号列が書かれており、ヘッドはそのうちの１つのマス目のところにいる。
- 動作中
以下の動作を繰り返す。
- ヘッドのマス目を読む。
- プログラムにしたがって、
- マス目に記号を書く。
- ヘッドを左右どちらか一方に変える。
- 状態を新しい状態に変える。
- 動作の停止
状態が特別な状態（停止状態）になった時、チューリング機械は停止する。
[動作の具体例]
- 括弧の左右の対応を調べるチューリング機械
- 括弧の対応が取れているなら”１”を、取れていないないのなら”０”を書いて停止する。
- 記号の種類
b,(,),*,0,1→６種類（b:ブランク。空白。）
- プログラム
- Step-1
・読み取り記号が")"ならば"*"を書き、ヘッドを左へ動かし、Step-2へ。
・読み取り記号が"b"ならば"b"を書き、ヘッドを左へ動かし、Step-3へ。
・これら以外ならば、読み取った記号と同じ記号を書きヘッドを右へ動かし、Step-1を繰り返す。
- Step-2
・読み取り記号が"("ならば"*"を書き、ヘッドを右へ動かし、Step-1へ。
・読み取り記号が"b"ならば"0"を書き、ヘッドを右へ動かし、Step-4へ。
・これら以外ならば、読み取った記号と同じ記号を書きヘッドを左へ動かし、Step-2を繰り返す。
- Step-3
・読み取り記号が"("ならば"0"を書き、ヘッドを右へ動かし、Step-4へ。
・読み取り記号が"b"ならば"1"を書き、ヘッドを右へ動かし、Step-4へ。
・これら以外ならば、読み取った記号と同じ記号を書きヘッドを左へ動かし、Step-3を繰り返す。
- Step-4
・動作を停止する。