アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

270

8

章 不可能なプログラム

8.2

　決定可能性

これまでチューリングマシンには高い能力と柔軟性があることを見てきました。チューリングマシン

はデータとしてエンコードされた任意のプログラムを実行することができ、考え得るどんなアルゴリズ

ムも実行することができ、時間の制限なく動かすことができ、自分自身の記述を計算することができま

す。また、その単純さにもかかわらず、この小さな架空の機械は一般的な万能機械を代表しているこ

ともわかっています。

チューリングマシンがそれほど強力で柔軟であるなら、チューリングマシン（すなわち現実世界のコ

ンピュータとプログラミング言語）にできないことはあるのでしょうか。

この質問に答える前に、もう少し質問を正確にする必要があります。私たちがチューリングマシンに

頼めるのは、どんな種類の問題なのでしょうか。どうすればそれが完了したとわかるのでしょうか。あ

らゆる種類の問題について調べる必要があるのでしょうか。それと

も、一部の問題について考えれば

十分なのでしょうか。解決策が単に私たちの現在の理解を超えているような問題を探しているので

しょうか。それとも、すでに私たちには決して解けないとわかっているような問題を探しているので

しょうか。

決定問題（decision problem）に注目することによって、質問のスコープを絞ることができます。決

定問題というのは、イエスかノーで答えられる問題です。たとえば「2は3よりも小さいですか」「正規

表現

(a(|b))

*

は文字列

'abaab'

にマ