出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。theory)では、チューリングマシンなどの計算模型でいかなる計算問題が解けるか、またより抽象的に、計算可能な問題のクラスがいかなる構造をもっているかを調べる、計算理論や数学の一分野である。計算可能性は計算複雑性の特殊なものともいえるが、ふつう複雑性理論といえば計算可能関数のうち計算資源を制限して解ける問題を対象とするのに対し、計算可能性理論は、計算可能関数またはより大きな問題クラスを主に扱う。関連項目はじめに[編集]計算機科学の中心的課題の1つは、コンピュータを使って解ける問題の範囲を理解することでコンピュータの限界に対処することである。コンピュータは無限の計算能力を持つと思われがちだし、十分な時間さえ与えられればどんな問題も解けると想像することは易しい。多大な計算資源を与えられたとしても、見たところ単純な問題を解くことでコンピュータの能力の限界を明確に示すことは可能である。計算可能性理論では、次の質問に答えることでコンピュータの能力を明らかにする。「ある形式言語と文字列が与えられたとき、その文字列はその形式言語に含まれるか?」である。この質問はやや難解なので、もう少し判り易く例を挙げる。全ての素数を表す数字列の集合を言語として定義する。入力文字列がその形式言語に含まれるかどうかという質問は、この場合、その数が素数であるかを問うのと同じことである。なる全ての文字列の集合などが形式言語の例である。これらの例では、それぞれの問題を解くコンピュータの構築の容易さが言語によって異なることは明白である。その質問に答えるのが計算可能性理論の目標である。計算の形式モデル[編集]計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。オートマトン(DFA)、あるいは単に有限状態機械とも呼ぶ。単純な計算モデルである。現在、実際に使われているコンピュータは、有限状態機械としてモデル化できる。この機械は状態の集合を持ち、入力列によって働く状態遷移の集合を持つ。一部の状態は受容状態と呼ばれる。入力列は一度に1文字ずつ機械に入力され、現在状態から状態遷移先への遷移条件と入力が比較され、マッチングするものがあればその状態が新たな状態となる。入力列が終了したとき機械が受容状態にあれば、全入力列が受容されたということができる。プッシュダウン・オートマトン有限状態機械に似ているが、任意のサイズに成長可能な実行スタックを利用可能である点が異なる。状態遷移の際に記号をスタックに積むかスタックから記号を除くかを指定できる。チューリングマシンこれも有限状態機械に似ているが、入力が「テープ」の形式になっていて、読むだけでなく書くこともでき、テープを送ったり巻き戻したりして読み書きの位置を決めることができる。テープのサイズは任意である。チューリングマシンは時間さえかければ、かなり複雑な問題も解くことができる。このモデルは計算機科学では最も重要な計算モデルであり、資源の限界がない計算をシミュレートしたものである。計算モデルの能力[編集]これらの計算モデルについて、その限界を定めることができる。どのクラスの形式言語をその計算モデルは受容するか、である。有限状態機械の能力[編集]有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。同数含まれている言語がある。個の状態を持つとする。あるような構成であるとする。あることから、鳩の巣原理により、何らかの状態を繰り返すことになる。読み込んだときの状態が区別されない。なる文字列も受容してしまう。同数でないため、言語の定義からは受容してはいけない文字列なのである。従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。この言語を認識できるプログラムは簡単に書けると思われるかもしれない。現在のコンピュータは有限状態機械でモデル化できると上に書いてある。プログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。プッシュダウン・オートマトンの能力[編集]プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。プッシュダウン・オートマトンでも判定できない言語がある。その詳細は(正規言語のときとあまり変わらないので)ここでは述べない。文脈自由言語の反復補題も存在する。素数の集合からなる言語がその例である。チューリングマシンの能力[編集]チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語(例えば素数の集合からなる言語)も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。チューリングマシンでは、入力テープに「バックアップ」を置くことができるため、上で説明した計算モデルには不可能な方法で動作可能である。入力に対して停止しないチューリングマシンを構築することもできる。チューリングマシンはあらゆる入力について停止して答え(言語と入力の判定)を返す機械である。このようにチューリングマシンが必ず停止する言語クラスを帰納言語と呼ぶ。ある言語に含まれる文字列を与えられたときには停止するが、その言語に含まれない文字列を与えられたときに停止しない可能性があるというチューリングマシンもある。このような言語を帰納的可算言語と呼ぶ。チューリングマシンは非常に強力な計算モデルである。チューリングマシンの定義を修正してより強力なモデルを作ろうとしても失敗する。1次元だったテープを2次元や3次元に拡張したチューリングマシンや、複数のテープを持つチューリングマシンなどが考えられるが、いずれも1次元の1個のテープを持つチューリングマシンでシミュレート可能であることが判っている。それらのモデルの能力は通常のチューリングマシンと同じである。実際、チャーチ=チューリングのテーゼでは、チューリングマシンで判定できない言語を判定可能な計算モデルはないと推定されている。様々な人々がチューリングマシンよりも強力だという計算モデルを提案してきた。それらは非現実的であるか不合理である(下記参照)。従ってチューリングマシンは計算可能性の限界に関する広範囲な問題を解析する強力な手法である。そこで次の疑問が生まれる。「帰納的可算だが帰納でない言語はあるのか?」である。「帰納的可算でもない言語はあるのか?」という疑問も生まれる。停止問題は計算機科学の重要な問題の1つであり、計算可能性理論だけでなく日々のコンピュータの利用にも深い意味を持っている。停止問題を簡単に述べると次のようになる:チューリングマシンと入力が与えられたとき、その入力を与えられたプログラム(チューリングマシン)は停止(完了)するかどうかを求めよ。停止しない場合、永遠に動作し続ける。ここでチューリングマシンが判定しようとするのは素数や回文といった単純な問題ではなく、チューリングマシンで他のチューリングマシンに関する質問への答えを得ようとしているのである。詳しくは主項目(チューリングマシンの停止問題)を参照してもらうとして、結論としてこの問いに(あらゆる場合に)答えられるチューリングマシンは構築できない。あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラムを実行してみるしかないということになる。停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せずに永遠に動作するのかは判らない。あらゆるチューリングマシンに関する記述とあらゆる入力の停止する全組合せからなる言語は帰納言語ではない。従って、停止問題は計算不能または判定不能と呼ばれる。停止問題を拡張したライスの定理では、言語が特定の自明な特性を持つかどうかは(一般に)判定不能であるとされる。帰納言語以上の言語[編集]しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。帰納的可算ですらない言語も存在する。そのような言語の単純な例は、停止判定の補問題である。全てのチューリングマシンとそれらが停止しない入力の全組合せからなる言語である。構築することを考える。このマシンはチューリングマシンとその入力の組合せが停止する場合は永遠に動作し続ける。記述とその入力(別のチューリングマシンの記述とその入力)が与えられる。入力(あるチューリングマシンとその入力)も並行して実行するものとする。停止し、そのシミュレーションも停止することになる。一方のスレッドが停止し、もう一方が停止しないことから停止問題の判定機能を備えることになる。示したように停止問題は判定不能である。存在するという仮定が誤っていたことがわかる。以上から停止判定言語の補問題は帰納的可算言語ではないことがわかる。不合理な計算モデル[編集]チャーチ=チューリングのテーゼでは、チューリングマシンよりも強力な計算モデルは存在しないと推測した。ここでは、その推定に反する「不合理」な計算モデルの例をいくつか示す。計算機科学者は様々な「ハイパーコンピュータ」を想像してきた(ここでいうハイパーコンピュータとは、スーパーコンピュータのさらに高性能なものという意味ではない)。無限実行[編集]計算の各ステップが前のステップの半分の時間しかかからない機械を考える。