計算の理論を論ずるには、まず計算とは何か定めなければなりません。 この講義では、計算を行うモデルを Turing 機械に固定します。
Turing 機械はアランチューリングが考案した理論的なコンピュータです。 この Turing 機械の原理を元に実際のコンピュータが作られました。
Turing 機械には次のような特徴があります。
Turing 機械は、片無限に伸びるマスのついたテープと、そのテープのマスに 対して記号の読み書きを行いテープ上を左右に移動するテープヘッドと、その テープヘッドの制御をする有限状態制御部からなります。
Turing 機械で使用する命令は次のような構文です。
Label1: if Tapehead="文字1" then write "文字2" ;
move the head to right ;
goto Label2
この命令によって、テープヘッドから読んだ文字を元に、別の文字を書き、ヘッ ドを右(や左)に移動し(あるいはそのまま停止し)、別のラベルにジャンプしま す。 計算はこの命令のみで行います。 なお、同じ label を持つ命令も if 文の中の比較する文字1が異なれば許され るものとします(「決定性の条件」)。
この他に、計算の終りを示すための命令が追加されます。
accept は何らかの形で "yes" を出力して停止する命令です。 また、 reject は "no" を出力する同様の命令です。
伝統的な形で表現するには関数の形で書きます。 ラベルとテープから読んだ記号が決まると、書き込む文字とヘッドの動きと次 のラベルが決まるので、次のようになります。
このようにプログラムを関数の形で表現したものをδ関数と呼ぶこ とがあります。
Turing 機械を数学的に Formal に定義するには、集合の記述法などを使用し 次のように定義します。
Turing 機械 T は (Q, Σ, δ, label0, F) と 5 つの組みで定義します。
Turing 機械の拡張として複数のテープを持つことを許します。
なお、この Turing 機械における命令はつぎのようになります。
Label1: if Tapehead1="文字1" and ... and Tapeheadk="文字k"
then write "文字1'" ; move head1 to right ;
...
write "文字k'" ; move headk to left ;
goto Label2
テープ1とテープ2に入っている値の和をテープ3に入れるプログラムを考えま す。 値は二進数とし、値の前後には前後がわかるような記号├と┤が書かれている とします。 たとえば、今 10+19 を計算させようとすると初期のテープの状況は次のよう になります(数値は下位が先頭に、つまり little endian になっています)。
これに対してプログラムを書くと次のようになります。
start: if テープヘッド1=├ and テープヘッド2=├ then
write ├ to テープ1; write ├ to テープ2; write ├ to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label0;
label0: if テープヘッド1=0 and テープヘッド2=0 then
write 0 to テープ1; write 0 to テープ2; write 0 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label0;
label0: if テープヘッド1=0 and テープヘッド2=1 then
write 0 to テープ1; write 1 to テープ2; write 1 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label0;
label0: if テープヘッド1=1 and テープヘッド2=0 then
write 1 to テープ1; write 0 to テープ2; write 1 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label0;
label0: if テープヘッド1=1 and テープヘッド2=1 then
write 1 to テープ1; write 1 to テープ2; write 0 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label1;
label1: if テープヘッド1=0 and テープヘッド2=0 then
write 0 to テープ1; write 0 to テープ2; write 1 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label0;
label1: if テープヘッド1=0 and テープヘッド2=1 then
write 0 to テープ1; write 1 to テープ2; write 0 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label1;
label1: if テープヘッド1=1 and テープヘッド2=0 then
write 1 to テープ1; write 0 to テープ2; write 0 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label1;
label1: if テープヘッド1=1 and テープヘッド2=1 then
write 1 to テープ1; write 1 to テープ2; write 1 to テープ3;
move ヘッド1 right; move ヘッド2 right; move ヘッド3 right;
goto label1;
なお、入力が(一方でも)終了した時の処理は省略します。 また、上のプログラムと同等であるオートマトンを次に示します。 但し、ここで、テープ 1,2 は読み込み専用であるとし、 write による出力は 省略します。 さらにすべての遷移において、すべてのテープヘッドは右に動くので、これも 省略しています。
数学上の未解決問題のような一つの問題について yes, no が一つだけ決まる ものは、本講義におけるプログラミングの対象としません。 たとえば次のような問題を考えます。
これの答を出力するプログラムには次のようなものが考えられます。
これらのうちのどちらかが、正しいプログラムになります (1995年に print 'no' が正しいことが証明されました)。
本講義では一つの問題に対して、パラメータにより具体的なインスタンス(問 題例)を無限個生成できる問題を 取り扱います。たとえば「一次方程式を解け」などという問題です。 この場合、一つの問題に対してインスタンスは次のように無限個存在します。
インスタンスに対して答が yes, no のどちらかになるような問題を判定問題 と言います。たとえば素数判定問題などは、インスタンスが「3 は素数か?」、 「4 は素数か?」などとなりますが、それに対して答は yes, no のどちらかに なります。 さて、このように判定問題のインスタンスを考えると、 yes となるインスタ ンス(yes インスタンス)の集合を考えることができます。 素数判定問題においては素数の集合が yes インスタンスの集合になります。 したがって、ある判定問題を解くとは、与えられたインスタンスが yes イン スタンスの集合に含むかどうかを判定することと同じになります。
さて、判定問題や、yes インスタンスの集合というものを数学的に定式化しま しょう。 記号の有限集合をアルファベットと言います。ここでは集合の名前 を Σ とします。 記号の演算として連接・を考えます。 単純に二つの文字がつながるだけと考えて構いません。 (a・b)・c =a・(b・c) が成り立ちます。 記号の有限列を語と言います。 長さ 0 の語を空語と言い、λで表します。 アルファベットΣに対し、そこから生成できる語全体の集合を Σ*で表します。 Σ*の部分集合を言語と言います。 語w∈Σ*に対して、 wがある言語に含まれるかどうかは判定問題になります。
Σ={ (, ) } に対して、カッコ言語とは全てのカッコが正しく対 応しているような列全体の集合を言う。
Turing 機械で引き算を実現しなさい。
次週は Turing 機械のプログラミングを行います。