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