第5章 チューリングマシン
5.1 チューリングマシン
チューリングマシン (Turing Machine) とは、(AlanTuring, 1912–1954) により、計算の数学的モデルとして考えられた抽象機械である。有限個の状態を持つのは有限オートマトンと同じだが、状態のほかに、一つの記号を含むことができるセルが無限に一次元につながったテープと、テープに読み書きするためのヘッドを持ち、テープにあらかじめ入力が書き込まれている状態と、現在ヘッドが当たっているテープ上のセルの記号で、次の動作が決まる
次の動作のときに、新しい状態に移るとともに、テープのヘッドが当たっているセルを新しい記号で書き換え、ヘッドを一つ右か左のセルに移動するという点が有限オートマトンと異なる。

…

B

B

110101001BB

…

テープ
ヘッド
有限状態部

q0q4q2q1q3q5

図: チューリングマシンの概念図
形式言語の文法としては、生成規則の形にまったく制限のない文法（タイプ-0文法）に対応することが知られている。ただ、現実的には文脈自由文法より強力な文法が必要になることがないので、チューリングマシンを言語の解析のために使うことは、考えなくてよいだろう。
テープをメモリー、有限状態部を CPU と考えれば、現実のコンピューターのモデルとみなせる。整数や組、リストなど任意のデータをテープ上の記号列で表すことができるので、さまざまな計算をチューリングマシンで表現することができる。
チューリングマシンにも、非決定性チューリングマシンと決定性チューリングマシンがある。非決定性チューリングマシンは、次の動作にいくつかの選択肢があるチューリングマシンである。任意の非決定性チューリングマシンに対しオートマトン 第 5 章 p.1

て、等価な決定性チューリングマシンを構成できることが知られている。以下
では決定性チューリングマシンのみを考える。
例: 足し算をするチューリングマシン（初期状態は q ）
0

B

1

q0

(B, →, q0) (1, →, q1)

q1(1, →, q2) (1, →, q1)

q2(B, ←, q3) (1, →, q2)

q3(B, ←, q3) (B, ←, q4)

q4(1, →, stop)

読み方の例: 例えば、行 q と列 B の交点には、(B, ←, q ) がある、これは「テ23ープのヘッドの位置に B を書き込んで、ヘッドを左に移動し、新しい状態を q3とする。」 という動作を表す。
問 5.1.1 次のような初期値のテープ（ヘッドの位置は下線部）で、上の足し算をするチューリングマシンを実行せよ。

⋯ B B B 1 1 B 1 1 1 1 B B B ⋯–例: 掛け算をするチューリングマシン（初期状態は q ）
0

B

1q0

(B, →, q0)(B, →, q1)

q1(B, →, q2)(1, →, q1)

q2(B, →, q3)

q3(B, →, q4)(1, →, q3)

q4(1, ←, q5)(1, →, q4)

q5(B, ←, q6)(1, ←, q5)

q6(1, ←, q10)

(1, ←, q7)

q7(1, →, q2)(1, ←, q7)

q8(B, →, q0)(1, ←, q8)

q9(B, ←, q11)

(1, ←, q8)

q10(B, ←, q9)(1, ←, q10)

q11

(B, ←, q12)(B, ←, q11)

q12

(B, →, q12)

(B, →, q13)

q13

(B, →, q14)

(B, →, q13)

q14

(B, →, q15)

(1, →, q14)

q15

(B, ←, stop)

問 5.1.2 （結構大変）次のような初期値のテープ（ヘッドの位置は下線部）で、上の掛け算をするチューリングマシンを実行せよ。

⋯ B B B 1 1 1 B 1 1 B B B ⋯–5.2 チャーチの提唱
次の事実が知られている。
「チューリングマシンで表現できる計算」と「数）で表現できる計算」と「オートマトン 第 5 章 p.2（μ 再帰関(λ-calculus) で表現できる計算」

はすべて等価である。（帰納的関数、ラムダ計算はいずれも、チューリングマシンと同じころに考えられた「計算」の数学的なモデルである。）
チューリングマシン（または帰納的関数、またはラムダ計算）で表現できない「計算」を表現できる形式的な手法は、これまでに誰も見つけていない。
(Church's thesis) あるいは チャーチ=チューリングの提唱(Church-Turing thesis) とは、次のような主張である。
「計算できる」とは、すなわち「チューリングマシン（または帰納的関数、またはラムダ計算）で表現できる」ということである
形式的な手法でどのように「計算」を定義しても、チューリングマシン（または⋯）の能力を超えられない形式的とは「勘」とか「霊のお告げ」など他人に説明できない方法ではなく、誰がやっても同じになる、というような意味である。この主張は証明できるようなことではないので「定理」とは呼ばず「提唱」あるいは「テーゼ」 と呼ばれる。
チューリングマシン（または⋯）と等価な能力をもつ計算体系を(Turing complete) である、という。ほとんどのプログラミング言語は、チューリングマシン（または⋯）をエミュレートできるので、チューリング完全である。

5.3 チューリングマシンの停止性問題
チューリングマシンは、ヘッドが当たっているテープ上の記号と有限状態部の状態から次の動作を決める、たかが有限個の規則の集まりである。だから、チューリングマシンを記号列としてエンコードすることができる。エンコードしたチューリングマシンと入力記号列の組を受け取って、その動作をエミュレートする(universal Turing machine) を構成することもできる。（コンピューターのソフトウェアで仮想コンピューターを実現するのと同じようなものである。）
すると、次のような問題を考えることができる。
停止性問題 (halting problem) チューリングマシン（をエンコードした記号列）M と入力記号列 α の組を受け取って、チューリングマシン M が入力記号列 α に対して、停止するならば、H (M , α) が 👍 (Yes) を、停止しないならば H (M , α) が👎 (No) を返すようなチューリングマシン Hを定義することができるか？
これがもしできるならば、（コンピューターのプログラムはチューリングマシンと等価なので）プログラムが入力に対して停止するかどうか、を判定するプログラムが作成できることになる。（かなりの割合のバグが自動的に発見できる❕❗）

残念ながら、そのようなチューリングマシンを定義することは無理であることが証明されている。（チューリングマシンの停止性の決定不能性）

オートマトン 第 5 章 p.3

証明: もしも停止性を判定できるチューリングマシン H が存在したと仮定する。H を使って H を次のように定義することができる。
′{

👍ならば H (M )は停止しない。
H (M , M ) = 👎 ならば H (M )は停止する。
′H (M , M ) =′′′

H (H )が停止するかどうかを考える。停止するとすると、それは、H (H , H )′′が👎であることになる。しかし、これは H (H ) が停止しないことを意味する′′ので矛盾である。同様に H (H ) が停止しないとすると、H (H , H ) が👍であ′′′′ることになる。 H (H ) が停止することになり、やはり矛盾である。よって、′′停止性を判定できるチューリングマシン H が存在するという仮定が間違っている。（証明終わり）
チューリングマシンの停止性は、代表的な（Yes/No を決定する計算方法が存在しないことが証明されている問題）である。多くの問題の決定不能性は、チューリングマシンの停止性の決定不能性に帰着して（…が計算可能ならば、チューリングマシンの停止性も計算できる、という背理法で）証明される。

オートマトン 第 5 章 p.4