計算可能性理論
停止問題は計算機科学の重要な問題の1つであり、計算可能性理論だけでなく日々のコンピュータの利用にも深い意味を持っている。停止問題を簡単に述べると次のようになる:
チューリングマシンと入力が与えられたとき、その入力を与えられたプログラム(チューリングマシン)は停止(完了)するかどうかを求めよ。停止しない場合、永遠に動作し続ける。
ここでチューリングマシンが判定しようとするのは素数や回文といった単純な問題ではなく、チューリングマシンで他のチューリングマシンに関する質問への答えを得ようとしているのである。詳しくは主項目(チューリングマシンの停止問題)を参照してもらうとして、結論としてこの問いに(あらゆる場合に)答えられるチューリングマシンは構築できない。
すなわち、あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラムを実行してみるしかないということになる。そして、停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せずに永遠に動作するのかは判らない。あらゆるチューリングマシンに関する記述とあらゆる入力の停止する全組合せからなる言語は帰納言語ではない。従って、停止問題は計算不能または判定不能と呼ばれる。
停止問題を拡張したライスの定理では、言語が特定の自明な特性を持つかどうかは(一般に)判定不能であるとされる。
理論計算機科学の中心的課題の1つとして、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処する、ということがあった。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし間違っており、そのことは「チューリングマシンの停止問題」の否定的解決として示された。以下では、そこに至る過程とそこから先の発展を述べる。
計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか?」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。
しかし、この観測された明白な違いはどういう意味で正確なのか? ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか? その質問に答えるのが計算可能性理論の目標である。