第 1 回 Turing 機械

本日の内容

• 1-1. Turing 機械とは
• 1-2. Turing 機械の拡張
• 1-3. Turing 機械のプログラミング
• 1-4. 計算の理論における「問題」
• 1-5. 演習
• 1-6. 次週の予告

計算の理論を論ずるには、まず計算とは何か定めなければなりません。 この講義では、計算を行うモデルを Turing 機械に固定します。

1-1. Turing 機械とは

Turing 機械には次のような特徴があります。

1. 非ノイマン型(プログラムをメモリーに格納しない)
2. RAM なし
3. 実質的な命令はただ一つ

Turing 機械は、片無限に伸びるマスのついたテープと、そのテープのマスに 対して記号の読み書きを行いテープ上を左右に移動するテープヘッドと、その テープヘッドの制御をする有限状態制御部からなります。

Turing 機械で使用する命令は次のような構文です。

Label1: if Tapehead="文字1" then write "文字2" ; 
                                 move the head to right ;
                                 goto Label2

この命令によって、テープヘッドから読んだ文字を元に、別の文字を書き、ヘッ ドを右(や左)に移動し(あるいはそのまま停止し)、別のラベルにジャンプしま す。 計算はこの命令のみで行います。 なお、同じ label を持つ命令も if 文の中の比較する文字1が異なれば許され るものとします(「決定性の条件」)。

この他に、計算の終りを示すための命令が追加されます。

• Label: accept
• Label: reject

accept は何らかの形で "yes" を出力して停止する命令です。 また、 reject は "no" を出力する同様の命令です。

伝統的な形で表現するには関数の形で書きます。 ラベルとテープから読んだ記号が決まると、書き込む文字とヘッドの動きと次 のラベルが決まるので、次のようになります。

このようにプログラムを関数の形で表現したものをδ関数と呼ぶこ とがあります。

Turing 機械を数学的に Formal に定義するには、集合の記述法などを使用し 次のように定義します。

使用する label(状態)の集合

Q={ label1, label2, ..., labeln}

使用する文字の集合(アルファベット)

Σ

プログラムの最初の label

q₀

プログラム終了のラベルの集合

F={labelf₁, labelf₂, ... labelf_k,

Turing 機械 T は (Q, Σ, δ, q₀, F) と 5 つの組みで定義します。

1-2. Turing 機械の拡張

Turing 機械の拡張として複数のテープを持つことを許します。

1-3. Turing 機械のプログラミング

足し算

テープ1とテープ2に入っている値の和をテープ3に入れるプログラムを考えま す。 値は二進数とし、値の前後には前後がわかるような記号├と┤が書かれている とします。 たとえば、今 10+19 を計算させようとすると初期のテープの状況は次のよう になります。

これに対してプログラムを書くと次のようになります。

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 l0;
l0: 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 l0;
l0: 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 l0;
l0: 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 l0;
l0: 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 l1;
l1: 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 l0;
l1: 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 l1;
l1: 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 l1;
l1: 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 l1;

なお、入力が(一方でも)終了した時の処理は省略します。 また、上のプログラムと同等であるオートマトンを次に示します。

1-4. 計算の理論における「問題」

数学上の未解決問題のような一つの問題について yes, no が一つだけ決まる ものは、本講義におけるプログラミングの対象としません。 たとえば次のような問題を考えます。

n≧3 の時、 を満たす整数 n, x, y, z の組 みは存在するか

これの答を出力するプログラムには次のようなものが考えられます。

• print 'yes'
• print 'no'

これらのうちのどちらかが、正しいプログラムになります (1995年に print 'no' が正しいことが証明されました)。

本講義ではパラメータにより具体的なインスタンスを無限個生成できる問題を 取り扱います。たとえば「一次方程式を解け」などという問題です。 この場合、インスタンスは次のように無限個存在します。

• 2 x + 5 =0
• 3 x + 6 =0
• …

判定問題

インスタンスに対して答が yes, no のどちらかになるような問題を判定問題 と言います。たとえば素数判定問題などは、インスタンスが「3 は素数か?」、 「4 は素数か?」などと答が yes, no のどちらかになります。

記号の有限集合をアルファベットと言います。ここでは集合の名前 を Σ とします。 記号の演算として連接・を考えます。 単純に二つの文字がつながるだけと考えて構いません。 (a・b)・c =a・(b・c) が成り立ちます。 記号の有限列を語と言います。 長さ 0 の語を空語と言い、λで表します。 アルファベットΣに対し、そこから生成できる語全体の集合を Σ^*で表します。 Σ^*の部分集合を言語と言います。 語w∈Σ^*に対して、 wがある言語に含まれるかどうかは判定問題になります。

例

1-5. 演習

Turing 機械で引き算を実現しなさい

1-6. 次週の予告

次週は Turing 機械のプログラミングを行います。