| テューリング機械とは, 計算とは何かという 問題について考察するために "計算する" という人間の行為を抽象化して Alan Turing が考案した仮想的な機械です. |
| 足し算するテューリング機械や掛け算するテューリング機械など 一つ一つの計算を行うテューリング機械が考えられる他, あらゆる計算を行う万能テューリング機械 (universal Turing machine) の 存在することをテューリングは示しています. |
| テューリング機械は実用をめざしたものではなく, 電子回路で作ったとしても働きが効率的でなくて実用には向きません. しかし, 万能テューリング機械の概念はコンピューターの原理と 深くかかわっています. その意味でテューリング機械の考えは大切です. |
| テューリング機械はすべて本体, ヘッド, テープ の三つの部分からなります. |
| ○ テープはます目に区切ってあって一ますに記号を一つだけ書けます. テープ上の記号は書き替えることができます. テープは無限に長いとします. |
| ○ ヘッドは本体に制御されて, テープから記号を読みとったり, テープに記号を書き込んだり, テープ上を移動したりします. ヘッドの移動は, 現在位置にとどまるか, 左へ一ます動くか, 右へ一ます動くかのいずれかに限ります. |
| ○ 本体には内部状態があり, 内部状態に応じてヘッドの動きを制御したり内部状態を変えたりします. |
| テープに書くことの出来る記号の種類はあらかじめ有限個決めておきます. なお, 空白も記号の一種と考えて, 何も書いてないのは空白が書いてあるとみなします. |
| 本体の取り得る内部状態もあらかじめ有限個決めておきます. そして内部状態の一つを "初期状態" と決めておきます. |
| 本体の現在の内部状態と現在の位置でヘッドが読みとった記号とに対応して, ヘッドがテープの現在位置にどの記号を書き込み, 本体の内部状態をどの内部状態にして, ヘッドをどれだけ移動させるか, すべての場合についてあらかじめ決めておきます. 時間は離散的に進むと考えます. つまり, ある瞬間の状態から次の瞬間の状態が確定します. |
| 機械の動作はつぎのとおりです: 最初は本体の内部状態を初期状態で, ヘッドをテープ上のある位置に置きます. 各瞬間に, 本体の内部状態とヘッドが読んだ記号とに対応して, あらかじめ決められた規則に従ってテープに記号を書き本体の内部状態を変え ヘッドを移動させます. このことをくり返していきます. |
| テープから読んだのと同じ記号を書き, 内部状態を変えず, ヘッドが現在位置にとどまる場合を停止と考えます. |
| 簡単なテューリング機械の例を挙げます. 記号は空白, 0, 1の三種類とします. 本体の取り得る内部状態は q1, q2, q3の三つで, q1が初期状態であるとします. 機械の動作の規則は右の表のとおりとします. 表の左の見出しは本体の内部状態, 上の見出しは読んだ記号です. 表の各項目は, テープの現在位置に書き込む記号, 次の瞬間の内部状態, ヘッドの移動の三つ組です. ヘッドの移動について, Lは左へ移動, Rは右へ移動, 0は移動せず現在位置にとどまることを示します. 例えばq1の行, "空白" の列に (1,q3,0) と あるのは, 内部状態q1で空白を読んだとき, テープの現在位置に 記号1を書き込み, 内部状態をq3に変え, ヘッドは現在位置に とどまることを示しています. なお横線 "−" は停止を示します. |
| 空白 | 0 | 1 | |
| q1 | (1,q3,0) | (1,q2,L) | (0,q1,L) |
| q2 | (空白,q3,R) | (0,q2,L) | (1,q2,L) |
| q3 | - | - | - |
| q1 | |||||
| 1 | 0 | 1 |
| テープに101が書いてあるとき, このテューリング機械がどんな動作をするか 追跡してみましょう. はじめは本体の内部状態が初期状態q1で, ヘッドは右端の数字1に位置してるとします. これをここでは左の図のように表すことにします. 空色の四角がヘッドを表し, その中にq1と書いてあるのは 本体の内部状態を表します. |
| 内部状態がq1でヘッドの下の記号が1ですから, 機械の動作規則の表のq1の行の1の列を見ます. (0,q1,L) と書いてあります. つまりテープに0を書き込み, 内部状態はq1のままでヘッドは一ます左に移動します. |
| q1 | |||||
| 1 | 0 | 0 |
| 左の図のようになるはずです.
こんどは内部状態がq1で記号が0ですから, 表を見ると (1,q2,L) です. テープに1を書き込み内部状態をq2に変え ヘッドは一ます左に移動します. |
| q2 | |||||
| 1 | 1 | 0 |
| 左の図のようになります. 内部状態q2で1を読みますから, 表から(1,q2,L). テープに1を書き込み (つまりテープを書き替えず), 内部状態も変えず, ヘッドは左へ移動します. |
| q2 | |||||
| 1 | 1 | 0 |
| 内部状態q2で空白を読むと(空白,q3,R), つまりテープを書き替えず内部状態をq3に変え右へ移動します. |
| q3 | |||||
| 1 | 1 | 0 |
| 内部状態q3で1を読み, 停止します. |
| テープには110という結果が得られました. |
| 問1. 上の例のテューリング機械で,
テープに最初につぎの数字が書いてあるときの動きをそれぞれ追跡して下さい.
初期状態はq1で, ヘッドの最初の位置は右端の数字のところとします. (上の例にならって書いて下さい. 説明は省いて左の一連の図だけでいいです). (a) 0101 (b) 111 (c) 1011 |
| 問2. 上の例のテューリング機械は, 計算を終えて停止したときヘッドが左端の数字に位置しています. これを改良して, 二進法で書いた数値に1を足し, 起動したときと同じ位置つまり 右端の数字のところにヘッドを置いて停止する機械を作って下さい. |
| 問3. 上の例の機械が1を足す機械であること, つまりテープに最初に二進法で数値が書いてあれば必ずその数値に1を足した 結果をテープに書いて停止することを証明して下さい. ただし初期状態はq1で, ヘッドの最初の位置は右端の数字のところとします. |
Copyright 2002 Nagashima Takashi
email nagasima-t@mta.biglobe.ne.jp