計算可能性理論
はじめに
計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし、多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。
計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。
しかし、この観測された明白な違いはどういう意味で正確なのか？ ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？ その質問に答えるのが計算可能性理論の目標である。
計算モデルの能力
これらの計算モデルについて、その限界を定めることができる。すなわち、どのクラスの形式言語をその計算モデルは受容するか、である。
有限状態機械の能力
有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。
正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械  があるとする。 は  個の状態を持つとする。ここで、文字列  が  個の 'a' の後に  個の 'b' があるような構成であるとする。
 の状態数は  しかないため、 を入力としたときに最初の 'a' が連続する部分の長さがであることから、鳩の巣原理により、何らかの状態を繰り返すことになる。 個の 'a' を読み込んだ状態  が 'a' を  個読み込んだ時に再度現われるとする（とする）。つまり、 個の 'a' を読み込んだときと  個の 'a' を読み込んだときの状態が区別されない。従って、 が  を受容するなら、その機械は  個の 'a' と  個の 'b' からなる文字列も受容してしまう。しかしその文字列は 'a' と 'b' が同数でないため、言語の定義からは受容してはいけない文字列なのである。
従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。
この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。
プッシュダウン・オートマトンの能力
プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。正規言語でないとされた 'a' と 'b' を同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。また一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。
しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は（正規言語のときとあまり変わらないので）ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。
チューリングマシンの能力
チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語（例えば素数の集合からなる言語）も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。
チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え（言語と入力の判定）を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。
チューリングマシンは非常に強力な計算モデルである。チューリングマシンの定義を修正してより強力なモデルを作ろうとしても失敗する。例えば、1次元だったテープを2次元や3次元に拡張したチューリングマシンや、複数のテープを持つチューリングマシンなどが考えられるが、いずれも1次元の1個のテープを持つチューリングマシンでシミュレート可能であることが判っている。つまり、それらのモデルの能力は通常のチューリングマシンと同じである。実際、チャーチ＝チューリングのテーゼでは、チューリングマシンで判定できない言語を判定可能な計算モデルはないと推定されている。様々な人々がチューリングマシンよりも強力だという計算モデルを提案してきた。しかし、それらは非現実的であるか不合理である（下記参照）。
従ってチューリングマシンは計算可能性の限界に関する広範囲な問題を解析する強力な手法である。そこで次の疑問が生まれる。「帰納的可算だが帰納でない言語はあるのか？」である。また、「帰納的可算でもない言語はあるのか？」という疑問も生まれる。
帰納言語以上の言語
しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。しかし、帰納的可算ですらない言語も存在する。
そのような言語の単純な例は、停止判定の補問題である。つまり、全てのチューリングマシンとそれらが停止しない入力の全組合せからなる言語である。この言語が帰納的可算言語でないことを示すため、そのような全チューリングマシンについて停止して答えを返すチューリングマシン  を構築することを考える。このマシンはチューリングマシンとその入力の組合せが停止する場合は永遠に動作し続ける。そして、このマシンの動作をシミュレートするチューリングマシン  を考える。つまり、入力としての記述とその入力（別のチューリングマシンの記述とその入力）が与えられる。さらにタイムシェアリングによってはの入力（あるチューリングマシンとその入力）も並行して実行するものとする。の入力であるチューリングマシンの記述と入力が停止しない組合せの場合、 は停止し、そのシミュレーションも停止することになる。従って、は一方のスレッドが停止し、もう一方が停止しないことから停止問題の判定機能を備えることになる。しかし、既に示したように停止問題は判定不能である。この矛盾により、 が存在するという仮定が誤っていたことがわかる。以上から停止判定言語の補問題は帰納的可算言語ではないことがわかる。
不合理な計算モデル
チャーチ＝チューリングのテーゼでは、チューリングマシンよりも強力な計算モデルは存在しないと推測した。ここでは、その推定に反する「不合理」な計算モデルの例をいくつか示す。計算機科学者は様々な「ハイパーコンピュータ」を想像してきた（ここでいうハイパーコンピュータとは、スーパーコンピュータのさらに高性能なものという意味ではない）。
神託機械
神託機械とは、特定の決定不能な問題への解を「神託」として与える機械である。例えば、チューリングマシンに「停止問題の神託機械」が付属していれば、与えられた入力についてそのチューリングマシンが停止するかどうかは即座に判定できる。このような機械は再帰理論の中心的話題である。
ハイパーコンピュータの限界
これらのマシンにも限界はある。あるチューリングマシンの停止問題を解くことができるとしても、それらの機械自身の停止問題は解くことが出来ない。つまり、神託機械は、ある神託機械が停止するかどうかに答えることはできない。
歴史
アロンゾ・チャーチとスティーブン・コール・クリーネが開発したラムダ計算により、計算可能性理論の定式化に重要な役割を果たした。アラン・チューリングは現代計算機科学の父とされる人物であり、チューリングマシンなど計算可能性理論にも数々の重要な足跡を残している（、1936年）。