Loading article…
計算可能性とは、効率的な手順によって問題を解決できる能力のことである。これは、数理論理学における計算可能性理論、およびコンピュータ科学における計算理論の分野における重要なテーマである。問題の計算可能性は、その問題を解決するためのアルゴリズムの存在と密接に関連している。
計算可能性のモデルとして最も広く研究されているのは、チューリング計算可能関数、μ再帰関数、ラムダ計算であり、これらはすべて計算能力が同等である。計算可能性の他の形態も研究されており、チューリングマシンよりも弱い計算可能性の概念はオートマトン理論で研究され、チューリングマシンよりも強い計算可能性の概念はハイパーコンピューティングの分野で研究されている。
計算可能性における中心的な概念は、（計算）問題という概念であり、これは計算可能性を探求できるタスクのことである。
問題には大きく分けて2種類あります。
その他の問題の種類としては、探索問題や最適化問題などがある。
計算可能性理論の目標の一つは、それぞれの計算モデルにおいて、どの問題、あるいはどの種類の問題が解決可能かを明らかにすることである。
計算モデルとは、特定の種類の計算プロセスを形式的に記述したものである。この記述は、多くの場合、対象となるタスクを実行するための抽象的な機械の形をとる。チューリングマシン（チャーチ＝チューリングのテーゼを参照）に相当する一般的な計算モデルには、以下のようなものがある。
一般的な計算モデルに加えて、より単純な計算モデルは、特定の限定されたアプリケーションに役立ちます。たとえば、正規表現は、オフィス生産性ソフトウェアからプログラミング言語まで、多くのコンテキストで文字列パターンを指定します。正規表現と数学的に等価な別の形式である有限オートマトンは、回路設計や一部の問題解決に使用されます。文脈自由文法は、プログラミング言語の構文を指定します。非決定性プッシュダウンオートマトンは、文脈自由文法と等価な別の形式です。
計算モデルによって、実行できるタスクは異なります。計算モデルの能力を測る一つの方法は、そのモデルが生成できる形式言語のクラスを調べることです。そうすることで、チョムスキー言語階層が得られます。
その他の制限付き計算モデルには以下が含まれる。
これらの計算モデルを用いることで、それらの限界を判断できます。つまり、どのような種類の言語を受け入れることができるのかを判断できるのです。
コンピュータ科学者は、有限状態機械で受理可能な言語を正規言語と呼ぶ。有限状態機械における可能な状態の数は有限であるという制約があるため、正規言語ではない言語を見つけるには、無限個の状態を必要とする言語を構築する必要があることがわかる。
このような言語の一例として、文字「a」と「b」が同数含まれるすべての文字列の集合が挙げられます。この言語が有限状態機械で正しく認識できない理由を理解するために、まず、そのような機械Mが存在すると仮定します。Mはn個の状態を持つ必要があります。次に、次のような文字列xを考えます。「a」の後に続く「b」。
M がxを読み込むとき、最初の「a」の系列を読み込むときに繰り返される機械の状態が必ずあるはずです。鳩の巣原理により、'a' とn 個の状態のみが存在する。この状態をSと呼び、さらに、機械がSの最初の出現から 'a' シーケンス中の次の出現まで読み取る'a' の数を d とする。すると、Sの 2 番目の出現時に、追加のd (ここで) 'a's と、再び状態Sに戻ります。これは、文字列が「a」は文字列と同じ状態になる必要があります「a」。これは、マシンがx を受け入れる場合、文字列も受け入れなければならないことを意味します。「a」の後に続く'b's は、'a' と 'b' が同数含まれる文字列の言語には含まれません。言い換えれば、M は、'a' と 'b' が同数含まれる文字列と、'b' が同数含まれる文字列を正しく区別できません。「a」と「b」。
したがって、この言語は有限状態機械では正しく受理されないため、正規言語ではないことがわかります。この結果のより一般的な形式は、正規言語のポンピング補題と呼ばれ、広範な言語クラスが有限状態機械で認識されないことを示すために使用できます。
コンピュータ科学者は、プッシュダウンオートマトンが受理できる言語を文脈自由言語と定義し、これは文脈自由文法として指定できます。私たちが正規言語ではないことを示した「a」と「b」の数が等しい文字列からなる言語は、プッシュダウンオートマトンによって判定できます。また、一般に、プッシュダウンオートマトンは有限状態機械と全く同じように動作できるため、正規言語であれば何でも判定できます。したがって、この計算モデルは有限状態機械よりもはるかに強力です。
しかし、プッシュダウンオートマトンでも判定できない言語も存在することが判明した。結果は正規表現の場合と同様であり、ここでは詳細には触れない。文脈自由言語にはポンピング補題が存在する。そのような言語の一例として、素数の集合が挙げられる。
チューリングマシンは、プッシュダウンオートマトンや文脈自由文法で受理される言語だけでなく、素数からなる言語など、プッシュダウンオートマトンでは判定できない言語も判定できる。したがって、チューリングマシンは、プッシュダウンオートマトンよりもはるかに強力な計算モデルである。
チューリングマシンは入力テープを「バックアップ」できるため、これまで説明した他の計算モデルでは不可能な方法で、長時間実行することが可能になります。一部の入力に対して実行を終了（停止）しないチューリングマシンを構築することも可能です。チューリングマシンが最終的にすべての入力に対して停止し、答えを出す場合、そのチューリングマシンは言語を判定できると言います。このように判定できる言語は再帰的言語と呼ばれます。さらに、ある言語内の任意の入力に対しては最終的に停止して答えを出すが、その言語に含まれない入力文字列に対しては永遠に実行し続ける可能性のあるチューリングマシンについても説明できます。このようなチューリングマシンは、与えられた文字列が言語に含まれていることを教えてくれますが、そのような場合、永遠に実行し続ける可能性があるため、その動作に基づいて、与えられた文字列が言語に含まれていないことを確信することはできません。このようなチューリングマシンによって受理される言語は、再帰的に列挙可能な言語と呼ばれます。
チューリングマシンは、非常に強力なオートマトンモデルであることが判明した。チューリングマシンの定義を修正してより強力なマシンを作ろうとする試みは、驚くべきことに失敗に終わった。例えば、チューリングマシンにテープを追加したり、2次元（あるいは3次元、または任意の次元）の無限面を扱えるようにしたりしても、基本的な1次元テープを持つチューリングマシンで全てシミュレートできる。したがって、これらのモデルはより強力ではない。実際、チャーチ＝チューリングのテーゼの帰結として、チューリングマシンでは判定できない言語を判定できる合理的な計算モデルは存在しない。
そこで問うべきは、再帰的に列挙可能ではあるが再帰的ではない言語は存在するのか、そしてさらに、再帰的に列挙可能ですらない言語は存在するのか、ということである。
停止問題は、計算可能性理論や日常生活におけるコンピュータの利用方法に大きな影響を与えるため、コンピュータ科学において最も有名な問題の一つです。この問題は次のように表現できます。
ここで問われているのは、素数や回文に関する単純な質問ではなく、立場を逆転させて、チューリングマシンに別のチューリングマシンに関する質問に答えさせるというものです。この質問にすべての場合において答えられるチューリングマシンを構築することは不可能であることが示されています（メイン記事「停止問題」を参照）。
つまり、特定の入力に対してプログラムが必ず停止するかどうかを確実に知る唯一の一般的な方法は、プログラムを実行して停止するかどうかを確認することです。停止すれば、停止することが分かります。しかし、停止しない場合は、最終的に停止するかどうかは決して分からないかもしれません。すべてのチューリングマシン記述と、それらのチューリングマシンが最終的に停止する可能性のあるすべての入力ストリームをペアにした言語は、再帰的ではありません。したがって、停止問題は計算不可能または決定不能と呼ばれます。
停止問題の拡張としてライスの定理があり、これは（一般に）与えられた言語が特定の非自明な性質を持つかどうかは決定不可能であると述べている。
停止問題は、停止を決定するチューリングマシンが、停止しないチューリングマシンの表現を入力として与えられた場合に、永久に実行し続けることを許容すれば、簡単に解決できる。したがって、停止言語は再帰的に列挙可能である。しかし、再帰的に列挙できない言語を構築することも可能である。
このような言語の簡単な例として、停止言語の補数、すなわち、入力文字列に対して停止しないチューリングマシンとペアになったすべてのチューリングマシンからなる言語が挙げられます。この言語が再帰的に列挙可能ではないことを示すために、すべてのチューリングマシンに対して明確な答えを与えることができるが、最終的に停止するチューリングマシンに対しては無限に実行され続ける可能性のあるチューリングマシンMを構築することを考えてみましょう。そうすれば、別のチューリングマシンを構築することができます。これは、この機械の動作をシミュレートすると同時に、入力で与えられた機械の実行も直接シミュレートし、2 つのプログラムの実行を交互に行います。直接シミュレートするプログラムは、シミュレートしているプログラムが停止すると最終的に停止し、また、仮定により、入力プログラムが停止しない場合はMのシミュレーションも最終的に停止するため、次のことがわかります。最終的には、その並行バージョンのいずれかが停止するだろう。したがって、は停止問題の判定器である。しかし、停止問題は決定不能であることを既に示した。矛盾が生じ、Mが存在するという仮定が誤りであることが示された。したがって、停止言語の補集合は再帰的に列挙可能ではない。
並列ランダムアクセスマシンやペトリネットなど、並行処理に基づいた計算モデルが数多く開発されてきた。しかし、これらの並行計算モデルは、チューリングマシンでは実装できない数学関数を実装することはできない。
チャーチ＝チューリングのテーゼは、チューリングマシンよりも多くの数学関数を計算できる有効な計算モデルは存在しないと推測している。コンピュータ科学者たちは、チューリング計算能力を超える計算モデルであるハイパーコンピュータの様々な種類を構想してきた。
各計算ステップに必要な時間が前のステップの半分（そしてできれば前のステップの半分のエネルギー）である機械を想像してみてください。最初のステップに必要な時間を1/2時間単位（そして最初のステップに必要なエネルギーを1/2エネルギー単位）に正規化すると、実行には
実行には時間単位（およびエネルギー単位1）が必要です。この無限級数は1に収束するため、このゼノマシンは時間単位1（エネルギー単位1を使用）で可算無限ステップを実行できます。このマシンは、問題のマシンの実行を直接シミュレートすることで停止問題を判定できます。さらに、収束する無限級数（証明可能な無限級数）であればどれでも機能します。無限級数が値nに収束すると仮定すると、ゼノマシンは時間単位nで可算無限実行を完了します。
いわゆるオラクルマシンは、特定の決定不能問題の解を提供する様々な「オラクル」にアクセスできます。例えば、チューリングマシンには、特定の入力に対してチューリングマシンが停止するかどうかを即座に答える「停止オラクル」が存在する場合があります。これらのマシンは、再帰理論における中心的な研究テーマです。
想像しうるオートマタの限界を表しているように見えるこれらの機械でさえ、独自の限界に直面する。それぞれの機械はチューリングマシンの停止問題を解決できるが、自分自身の停止問題を解決することはできない。例えば、オラクルマシンは、特定のオラクルマシンが停止するかどうかという問いに答えることはできない。
