| 目次 | 索引 |
|---|---|
h2 計算のモデル toc-computation-models
h3 アルゴリズム toc-algorithms
今日は、「計算機とは何か」について考えます。
言葉の通り、計算機とは計算を行う機械です。
ここで、計算という言葉は、加減乗除のことではなく、
問題を解く行為を指します。
問題を解くためには、その問題を解く方法が存在しなければなりません。
問題を解く方法が存在し、その通りに動く機械が構成できれば、
その機械でその問題を解くことができるわけです。
問題を解く方法を、
index アルゴリズム algorithm あるこりすむ
と呼びます。
アルゴリズムが存在しても、
その問題を解く機械が存在するかどうかは即答できませんが、
アルゴリズムが存在しなければ、どんな機械でもその問題は解けません。
h3 チューリング機械 toc-turing-machines
アルゴリズムという概念を厳密に議論するには、
計算機のモデルとなる機械を定義する必要があります。
計算機のモデルの中では、チューリング機械が重要です。
index チューリング機械 Turing machine ちゆうりんくきかい
とは、
index テープ tape てえふ
、
index ヘッド head へつと
、および
index 制御部 control part せいきよふ
から構成される、仮想的な機械です。
この機械のイメージは次の通りです。
...--+-----+-----+-----+-----+-----+-----+-----+--...
| | | | | | | |
| | | | | | | | テープ
...--+-----+-----+-----+-----+-----+-----+-----+--...
△
| ヘッド
|
+-----+
|
|
+--------+--------+
| |
| | 制御部
| |
+-----------------+
テープは、左にも右にも無限に伸びていて、
無限個のます目に区切られています。
一つ一つのます目には、あらかじめ決められた記号が一つ書き込めます。
テープに書き込める記号は、
index テープ記号 tape symbol てえふきこう
と呼ばれます。
ヘッドは、必ずどこかのます目に位置づけられていて、
・ます目の記号を読み取る
・ます目に記号を書き込む
・右隣のます目に移動する
・左隣のます目に移動する
ことができます。
制御部は、あらかじめ決められた記号を一つ覚えられます。
制御部の覚える記号は、
index 状態 state しようたい
と呼ばれます。
チューリング機械の一回の動作は、
状態 p と読み取ったテープ記号 a で決定されます。
その内容は、書き込むテープ記号 b, ヘッドの移動方向、次の状態 q です。
これを、動作の関数として
δ(p, a) = (b, R, q) (右移動)
δ(p, a) = (b, L, q) (左移動)
と書きます。
動作の順序は次の通りです。
1. 状態 p を確認する。
2. ます目のテープ記号 a を読み取る。
3. そのます目にテープ記号 b を書き込む。
4. ヘッドを右隣か左隣のます目に移動する。
5. 状態を q に変える。
チューリング機械への入力は、文字列で与えます。
入力の文字列が書き込まれたテープを用意し、
ヘッドをその文字列の先頭に位置づけ、
制御部を
index 初期状態 initial state しよきしようたい
と呼ばれる特別な状態にして、
チューリング機械を動かし始めます。
ただし、入力の文字列は有限の長さとし、テープの残りは
index 空白 space くうはく
と呼ばれる特別な記号 B で埋め尽くされているとします。
状態の中には、halt という特別なものがあり、
状態が halt になりますと、チューリング機械は停止します。
この時のテープの内容が、チューリング機械からの出力です。
ただし、空白は無視します。
状態が q で、テープの内容が
... B X Y Z B ...
で、ヘッドの位置が Y であることを、
B X {q} Y Z B
と表現することにします。
この表現を、
index 計算状況 configuration けいさんしようきよう
と呼びます。
計算状況の遷移は、記号 |-- で表すことにします。
なお、動作関数で定義されていない引数については、
エラーで停止するものと考えます。
h3 チューリング機械の例 toc-turing-machine-examples
チューリング機械の例として、数値 x を入力として与えると、
x + 1 を出力するものを考えます。
ここで、x は負でない整数とします。
また、テープの上では、
数値 0 は T, 1 は TT, 2 は TTT, ... と表現することにします。
例えば、入力が 2 で出力が 3 という計算でしたら、
テープの内容を
... B T T T B ...
として動き始め、最後にテープの内容が
... B T T T T B ...
となって停止します。
チューリング機械の動作関数は次の通りです。
δ(q0, T) = (T, R, q1)
δ(q1, T) = (T, R, q1)
δ(q1, B) = (T, R, halt)
上記の入力例では、計算状況は以下のようになります。
B {q0} T T T B B |-- B T {q1} T T B B
|-- B T T {q1} T B B
|-- B T T T {q1} B B
|-- B T T T T {halt} B
例題 1.
以下は足し算を行うチューリング機械です。
ここで、入力は負でない整数とします。
数値のテープ表現は、0 は T, 1 は TT, 2 は TTT, ... とします。
入力の区切りは記号 S とします。
入力が 1 と 2 のとき出力が 3 になることを確認してください。
δ(q0, T) = (B, R, q1)
δ(q1, T) = (T, R, q1)
δ(q1, S) = (S, R, q2)
δ(q2, T) = (T, R, q3)
δ(q3, T) = (T, R, q3)
δ(q3, B) = (B, L, q4)
δ(q4, T) = (B, L, q5)
δ(q5, T) = (T, L, q5)
δ(q5, S) = (T, L, halt)
解答例 1.
B {q0} T T S T T T B |-- B B {q1} T S T T T B
|-- B B T {q1} S T T T B
|-- B B T S {q2} T T T B
|-- B B T S T {q3} T T B
|-- B B T S T T {q3} T B
|-- B B T S T T T {q3} B
|-- B B T S T T {q4} T B
|-- B B T S T {q5} T B B
|-- B B T S {q5} T T B B
|-- B B T {q5} S T T B B
|-- B B {halt} T T T T B B
h3 停止問題 toc-halting-problem
上記のチューリング機械は、どんな入力に対しても停止します。
しかし、一般的には、
チューリング機械は入力によって停止したりしなかったりします。
永久に同じ動作を繰り返したり、
際限なく数を数え続けたりという状態に陥りますと、
チューリング機械は停止しません。
チューリング機械を符号化して数値に置き換えますと、
チューリング機械の性質が計算できるようになります。
チューリング機械の
index 停止問題 halting problem ていしもんたい
とは、チューリング機械 (の符号) M と数値 x を入力として与えたとき、
M に x を与えて停止するならば数値 1 を出力して停止し、
そうでないならば数値 0 を出力して停止するという計算です。
この問題については、
チューリング機械の停止問題を解くチューリング機械は存在しない。
ということが証明されています。
チューリング機械の計算能力については、
index チャーチの定立 Church's thesis ちやあちのていりつ
と呼ばれる主張があります。
これは、
アルゴリズムが存在すれば、
その問題を解くチューリング機械が必ず存在する。
ということです。
現在、チャーチの定立を疑う人はいません。
以上の二つから、
計算機には解けない問題がある。
という結論が得られます。
チューリング機械という単純なモデルを定義し、
その計算能力を厳密に議論することによって、
計算機の理論的限界が導けるということが重要です。
h2 演習 10 toc-exercises
以下は引き算を行うチューリング機械です。
ここで、入力は負でない整数とし、引き算の結果は負にならないとします。
数値のテープ表現は、0 は T, 1 は TT, 2 は TTT, ... とします。
入力の区切りは記号 S とします。
入力が 3 と 2 のとき出力が 1 になることを確認してください。
δ(q0, T) = (B, R, q1)
δ(q1, T) = (T, R, q1)
δ(q1, S) = (S, R, q2)
δ(q2, T) = (T, R, q3)
δ(q3, T) = (T, R, q4)
δ(q3, B) = (B, L, q7)
δ(q4, T) = (T, R, q4)
δ(q4, B) = (B, L, q5)
δ(q5, T) = (B, L, q6)
δ(q6, T) = (T, L, q6)
δ(q6, S) = (S, L, q6)
δ(q6, B) = (B, R, q0)
δ(q7, T) = (B, L, q7)
δ(q7, S) = (T, L, halt)
今日の演習10の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（12月3日）を明記してください。