計算可能性理論

計算可能性理論（けいさんかのうせいりろん、英: computability theory）とは、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。

理論計算機科学の中心的課題の1つとして、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処する、ということがあった。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。しかし間違っており、そのことは「チューリングマシンの停止問題」の否定的解決として示された。以下では、そこに至る過程とそこから先の発展を述べる。

計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。すなわち「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか？」である。この質問はやや難解なので、もう少し判り易く例を挙げる。まず、全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。同様に、全ての回文の集合や、文字 'a' だけからなる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。

しかし、この観測された明白な違いはどういう意味で正確なのか？ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？その質問に答えるのが計算可能性理論の目標である。

計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。

決定性有限状態機械: 決定性有限オートマトン（DFA）、あるいは単に有限状態機械とも呼ぶ。単純な計算モデルである。現在、実際に使われているコンピュータは、有限状態機械としてモデル化できる。この機械は状態の集合を持ち、入力列によって働く状態遷移の集合を持つ。一部の状態は受容状態と呼ばれる。入力列は一度に1文字ずつ機械に入力され、現在状態から状態遷移先への遷移条件と入力が比較され、マッチングするものがあればその状態が新たな状態となる。入力列が終了したとき機械が受容状態にあれば、全入力列が受容されたということができる。
プッシュダウン・オートマトン: 有限状態機械に似ているが、任意のサイズに成長可能な実行スタックを利用可能である点が異なる。状態遷移の際に記号をスタックに積むかスタックから記号を除くかを指定できる。
チューリングマシン: これも有限状態機械に似ているが、入力が「テープ」の形式になっていて、読むだけでなく書くこともでき、テープを送ったり巻き戻したりして読み書きの位置を決めることができる。テープのサイズは任意である。チューリングマシンは時間さえかければ、かなり複雑な問題も解くことができる。このモデルは計算機科学では最も重要な計算モデルであり、資源の限界がない計算をシミュレートしたものである。

これらの計算モデルについて、その限界を定めることができる。すなわち、どのクラスの形式言語をその計算モデルは受容するか、である。

有限状態機械の能力

有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。

正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 $M$ があるとする。 $M$ は $n$ 個の状態を持つとする。ここで、文字列 $x$ が $(n+1)$ 個の 'a' の後に $(n+1)$ 個の 'b' があるような構成であるとする。

$M$ の状態数は $n$ しかないため、 $x$ を入力としたときに最初の 'a' が連続する部分の長さが $(n+1)$ であることから、鳩の巣原理により、何らかの状態を繰り返すことになる。 $(n+1)$ 個の 'a' を読み込んだ状態 $S$ が 'a' を $d$ 個読み込んだ時に再度現われるとする（ $d>0$ とする）。つまり、 $(n+d+1)$ 個の 'a' を読み込んだときと $(n+1)$ 個の 'a' を読み込んだときの状態が区別されない。従って、 $M$ が $x$ を受容するなら、その機械は $(n+d+1)$ 個の 'a' と $(n+1)$ 個の 'b' からなる文字列も受容してしまう。しかしその文字列は 'a' と 'b' が同数でないため、言語の定義からは受容してはいけない文字列なのである。

従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。

この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。

プッシュダウン・オートマトンの能力

プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。正規言語でないとされた 'a' と 'b' を同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。また一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。

しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は（正規言語のときとあまり変わらないので）ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。

チューリングマシンの能力

チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語（例えば素数の集合からなる言語）も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。

チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え（言語と入力の判定）を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。

チューリングマシンは非常に強力な計算モデルである。チューリングマシンの定義を修正してより強力なモデルを作ろうとしても失敗する。例えば、1次元だったテープを2次元や3次元に拡張したチューリングマシンや、複数のテープを持つチューリングマシンなどが考えられるが、いずれも1次元の1個のテープを持つチューリングマシンでシミュレート可能であることが判っている。つまり、それらのモデルの能力は通常のチューリングマシンと同じである。実際、チャーチ＝チューリングのテーゼでは、チューリングマシンで判定できない言語を判定可能な計算モデルはないと推定されている。様々な人々がチューリングマシンよりも強力だという計算モデルを提案してきた。しかし、それらは非現実的であるか不合理である（下記参照）。

従ってチューリングマシンは計算可能性の限界に関する広範囲な問題を解析する強力な手法である。そこで次の疑問が生まれる。「帰納的可算だが帰納でない言語はあるのか？」である。また、「帰納的可算でもない言語はあるのか？」という疑問も生まれる。

停止問題

→詳細は「チューリングマシンの停止問題」を参照

停止問題は計算機科学の重要な問題の1つであり、計算可能性理論だけでなく日々のコンピュータの利用にも深い意味を持っている。停止問題を簡単に述べると次のようになる:

チューリングマシンと入力が与えられたとき、その入力を与えられたプログラム（チューリングマシン）は停止（完了）するかどうかを求めよ。停止しない場合、永遠に動作し続ける。

ここでチューリングマシンが判定しようとするのは素数や回文といった単純な問題ではなく、チューリングマシンで他のチューリングマシンに関する質問への答えを得ようとしているのである。詳しくは主項目（チューリングマシンの停止問題）を参照してもらうとして、結論としてこの問いに（あらゆる場合に）答えられるチューリングマシンは構築できない。

すなわち、あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラムを実行してみるしかないということになる。そして、停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せずに永遠に動作するのかは判らない。あらゆるチューリングマシンに関する記述とあらゆる入力の停止する全組合せからなる言語は帰納言語ではない。従って、停止問題は計算不能または判定不能と呼ばれる。

停止問題を拡張したライスの定理では、言語が特定の自明な特性を持つかどうかは（一般に）判定不能であるとされる。

帰納言語以上の言語

しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。しかし、帰納的可算ですらない言語も存在する。

そのような言語の単純な例は、停止判定の補問題である。つまり、全てのチューリングマシンとそれらが停止しない入力の全組合せからなる言語である。この言語が帰納的可算言語でないことを示すため、そのような全チューリングマシンについて停止して答えを返すチューリングマシン $M$ を構築することを考える。このマシンはチューリングマシンとその入力の組合せが停止する場合は永遠に動作し続ける。そして、このマシンの動作をシミュレートするチューリングマシン $M'$ を考える。つまり、入力として $M$ の記述とその入力（別のチューリングマシンの記述とその入力）が与えられる。さらにタイムシェアリングによって $M'$ は $M$ の入力（あるチューリングマシンとその入力）も並行して実行するものとする。 $M$ の入力であるチューリングマシンの記述と入力が停止しない組合せの場合、 $M$ は停止し、そのシミュレーションも停止することになる。従って、 $M'$ は一方のスレッドが停止し、もう一方が停止しないことから停止問題の判定機能を備えることになる。しかし、既に示したように停止問題は判定不能である。この矛盾により、 $M$ が存在するという仮定が誤っていたことがわかる。以上から停止判定言語の補問題は帰納的可算言語ではないことがわかる。

チャーチ＝チューリングのテーゼでは、チューリングマシンよりも強力な計算モデルは存在しないと推測した。ここでは、その推定に反する「不合理」な計算モデルの例をいくつか示す。計算機科学者は様々な「ハイパーコンピュータ」を想像してきた（ここでいうハイパーコンピュータとは、スーパーコンピュータのさらに高性能なものという意味ではない）。

無限実行

計算の各ステップが前のステップの半分の時間しかかからない機械を考える。第一ステップにかかる時間を 1 に正規化すると、実行にかかる時間は

1+{1 \over 2}+{1 \over 4}+\cdots

となる。この無限数列の総和は 2 に近づいていく。つまり、このチューリングマシンは 2 単位の時間内に無限の処理を実行できる。この機械は、対象となる機械の実行を直接シミュレーションすることで停止問題の判定が可能である。

神託機械

神託機械とは、特定の決定不能な問題への解を「神託」として与える機械である。例えば、チューリングマシンに「停止問題の神託機械」が付属していれば、与えられた入力についてそのチューリングマシンが停止するかどうかは即座に判定できる。このような機械は再帰理論の中心的話題である。

ハイパーコンピュータの限界

これらのマシンにも限界はある。あるチューリングマシンの停止問題を解くことができるとしても、それらの機械自身の停止問題は解くことができない。つまり、神託機械は、ある神託機械が停止するかどうかに答えることはできない。

アロンゾ・チャーチとスティーブン・コール・クリーネが開発したラムダ計算により、計算可能性理論の定式化に重要な役割を果たした。アラン・チューリングは現代計算機科学の父とされる人物であり、チューリングマシンなど計算可能性理論にも数々の重要な足跡を残している（、1936年）。

Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Part Two: Computability Theory, chapters 3–6, pp.123–222.
Christos Papadimitriou (1993年). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1 Chapter 3: Computability, pp.57–70.