計算可能性

計算可能性とは、効果的な手順によって問題を解決する能力のことです。これは、数理論理学における計算可能性理論、および計算機科学における計算理論の分野における重要なテーマです。問題の計算可能性は、その問題を解決するためのアルゴリズムの存在と密接に関連しています。

最も広く研究されている計算可能性モデルは、チューリング計算可能関数、μ再帰関数、そしてラムダ計算であり、いずれも計算能力は同等である。他の計算可能性モデルも研究されており、チューリングマシンよりも弱い計算可能性の概念はオートマトン理論で、チューリングマシンよりも強い計算可能性の概念はハイパーコンピューティングの分野で研究されている。

問題

計算可能性における中心的な考え方は、（計算）問題、つまりその計算可能性を調査できるタスクという考え方です。

問題には主に 2 つの種類があります。

決定問題は集合Sを固定する。S は文字列、自然数、あるいはより大きな集合Uから取られた他のオブジェクトの集合である。この問題の具体的な例としては、 Uの要素uが与えられたときに、uがSに含まれるかどうかを判定する問題が挙げられる。例えば、U を自然数の集合、Sを素数の集合とすると、これに対応する決定問題は素数判定問題となる。
関数問題は、集合Uから集合Vへの関数fから構成されます。この問題のインスタンスは、Uの要素uが与えられたときに、対応するVの要素f ( u )を計算することです。例えば、UとV が有限のバイナリ文字列全体の集合であり、f が文字列を受け取り、その数字を逆にした文字列を返す場合（つまり、 f(0101) = 1010 ）などが考えられます。

他の種類の問題には、探索問題や最適化問題などがあります。

計算可能性理論の目標の 1 つは、各計算モデルでどの問題または問題のクラスを解決できるかを決定することです。

計算の形式モデル

計算モデルとは、特定の種類の計算プロセスを形式的に記述したものです。この記述は、多くの場合、対象となるタスクを実行することを意図した抽象機械の形をとります。チューリングマシン（チャーチ＝チューリングのテーゼを参照）に相当する一般的な計算モデルには、以下のものがあります。

ラムダ計算: 計算は、最初のラムダ式（関数とその入力を分離する場合は 2 つ）と、ベータ削減を 1 回適用して前の項から推定されたラムダ項の有限シーケンスで構成されます。
組み合わせ論理: -計算と多くの類似点を持つ概念ですが、重要な相違点も存在します（例：不動点コンビネータYは組合せ論理では正規形ですが、-計算では正規形ではありません）。組合せ論理は、パラドックスの性質を理解し、数学の基礎をより簡潔に（概念的に）し、変数の概念を排除して数学におけるその役割を明確にするという大きな野心をもって発展しました。 $\lambda$ $\lambda$
μ再帰関数: 計算は、μ-再帰関数、つまりその定義シーケンス、任意の入力値、および定義シーケンスに現れる入力と出力を伴う再帰関数のシーケンスで構成されます。したがって、再帰関数 $f (x)$ の定義シーケンスに関数 $g (x)$ と $h (x, y)$ が現れる場合、形式 $g (5) = 7$ または $h (3,2) = 10$ の項が現れることがあります。このシーケンスの各エントリは、基本関数の適用であるか、合成、原始再帰、またはμ-再帰を使用して上記のエントリから続く必要があります。たとえば、 $f (x) = h (x, g (x))$ の場合、 $f (5) = 3$ が現れるには、上記で $g (5) = 6$ や $h (5,6) = 3$ などの項が現れる必要があります。最後の項が入力に適用された再帰関数の値を与える場合にのみ、計算は終了します。
文字列書き換えシステム: 文法のような規則を使用して記号の文字列を操作するマルコフアルゴリズムと、ポスト標準システムが含まれます。
レジ機: コンピュータの理論的な理想化。いくつかのバリエーションが存在する。それらのほとんどでは、各レジスタは自然数（サイズは無制限）を保持でき、命令は単純（かつ数も少ない）である。例えば、デクリメント（条件付きジャンプと組み合わせる）とインクリメント（および停止）のみが存在する。チューリングマシンに見られるような無限（または動的に増加する）外部記憶装置がない理由は、その役割をゲーデルの番号付け技法に置き換えることで理解できる。各レジスタが自然数を保持するという事実は、複雑なもの（例えば、シーケンスや行列など）を適切な巨大な自然数で表現することを可能にする。これらの技法の数論的基礎によって、表現と解釈の両方の明確性が確立される。
チューリングマシン: 有限状態機械に似ていますが、入力が実行「テープ」で提供される点が異なります。チューリングマシンは、このテープから読み込んだり、書き込んだり、読み書き「ヘッド」を越えて前後に移動したりできます。テープのサイズは任意のサイズに拡張できます。チューリングマシンは、任意の時間を要する複雑な計算を実行できます。このモデルは、事前に定義されたリソース制限がない計算をシミュレートするため、コンピュータサイエンスにおける最も重要な計算モデルと言えるでしょう。
マルチテープチューリングマシン: ここでは、複数のテープが存在する可能性があり、さらにテープごとに複数のヘッドが存在する可能性があります。驚くべきことに、この種のマシンで実行できる計算はすべて、通常のチューリングマシンでも実行できます。ただし、後者は速度が遅くなったり、テープ全体の領域をより大きく必要としたりする場合があります。
P′′: チューリングマシンと同様に、P'' は無限の記号テープ（ランダムアクセスなし）と、最小限の命令セットを使用します。しかし、これらの命令はチューリングマシンとは非常に異なっており、すべての「メモリのような」機能はテープによってのみ提供できるため、P'' は明確な状態を維持する必要がありません。現在の記号を書き換える代わりに、モジュール算術増分を実行できます。P'' には、空白の記号を検査するサイクル用の命令のペアもあります。その最小限の性質にもかかわらず、P'' は実装され（娯楽目的で）使用されている Brainfuckと呼ばれるプログラミング言語の親となる形式言語になっています。

一般的な計算モデルに加えて、より単純な計算モデルは、特殊な限定的な用途に役立ちます。例えば、正規表現は、オフィス生産性ソフトウェアからプログラミング言語まで、様々な文脈で文字列パターンを指定します。正規表現と数学的に同等な別の形式である有限オートマトンは、回路設計やある種の問題解決に使用されます。文脈自由文法は、プログラミング言語の構文を指定します。非決定性プッシュダウンオートマトンも、文脈自由文法と同等の別の形式です。

計算モデルはそれぞれ異なるタスクを実行する能力を持っています。計算モデルの能力を測定する一つの方法は、そのモデルが生成できる形式言語のクラスを研究することです。こうしてチョムスキー階層が得られます。

その他の制限された計算モデルには次のものがあります:

決定性有限オートマトン（DFA）: 有限状態機械とも呼ばれます。現実のコンピュータはすべて有限のリソースで動作するため、今日存在するすべてのコンピューティングデバイスは有限状態機械としてモデル化できます。このようなマシンは、一連の状態と、入力ストリームの影響を受ける一連の状態遷移を持ちます。特定の状態は受理状態として定義されます。入力ストリームは1文字ずつマシンに入力され、現在の状態の状態遷移が入力ストリームと比較されます。一致する遷移がある場合、マシンは新しい状態に移行します。入力ストリームの最後でマシンが受理状態にある場合、入力ストリーム全体が受理されます。
非決定性有限オートマトン（NFA）: もう一つの単純な計算モデルですが、処理順序は一意に決定されません。有限数の状態を通る複数の計算パスを同時に実行すると解釈できます。ただし、任意のNFAは等価なDFAに還元可能であることが証明可能です。
プッシュダウンオートマトン: 有限ステートマシンに似ていますが、実行スタックを備えており、任意のサイズまで拡張可能です。状態遷移は、さらにスタックにシンボルを追加するか、スタックからシンボルを削除するかを指定します。DFAは無限のメモリスタックを備えているため、DFAよりも強力ですが、常にスタックの最上位要素のみにアクセスできます。

オートマタの力

これらの計算モデルが手元にあれば、その限界が何であるかを判断できます。つまり、どのような言語のクラスを受け入れることができるかということです。

有限状態機械の力

コンピュータ科学者は、有限状態機械が受け入れ可能な言語を正規言語と呼びます。有限状態機械における可能な状態の数は有限であるという制約のため、正規言語ではない言語を見つけるには、無限の状態数を必要とする言語を構築する必要があることがわかります。

そのような言語の例として、文字「a」と「b」からなる文字列全体（文字「a」と「b」が同数含まれる）の集合が挙げられます。この言語が有限状態機械によって正しく認識されない理由を理解するために、まずそのような機械Mが存在すると仮定します。M は状態数nを持つ必要があります。次に、「a」と「b」が続く文字列xを考えます。 $(n+1)$ $(n+1)$

M がxを読み込むとき、最初の一連の 'a' を読み込むときに繰り返される何らかの状態がマシン内に存在しなければなりません。なぜなら、鳩の巣原理により、 'a' が存在し、状態はn個しかないからです。この状態をSと呼び、さらにd を、 'a' シーケンス中のSの最初の出現からそれ以降の出現までの間にマシンが読み込む 'a' の数とします。すると、 Sの 2 回目の出現で、さらにd 個(ただし) の 'a'を追加でき、再び状態Sに戻ることがわかります。これは、 'a' の文字列は'a'の文字列と同じ状態になる必要があることを意味します。これは、マシンがx を受け入れる場合、 'a' の後に 'b' が続く文字列も受け入れる必要があることを意味しますが、これは 'a' と 'b' の数が等しい文字列の言語には存在しません。つまり、M は、同じ数の 'a' と 'b' の文字列と、'a' と'b' を含む文字列を正しく区別できません。 $(n+1)$ $d>0$ $(n+d+1)$ $(n+1)$ $(n+d+1)$ $(n+1)$ $(n+d+1)$ $n+1$

したがって、この言語はいかなる有限状態機械にも正しく受理されず、したがって正規言語ではないことがわかります。この結果のより一般的な形は正規言語のポンピング補題と呼ばれ、これは広範な言語クラスが有限状態機械によって認識できないことを示すために使用できます。

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

コンピュータ科学者は、プッシュダウン・オートマトンが受理できる言語を文脈自由言語と定義し、文脈自由文法として規定することができます。「a」と「b」の数が等しい文字列からなる言語は正規言語ではないことが示されましたが、プッシュダウン・オートマトンによって決定することができます。また、一般にプッシュダウン・オートマトンは有限状態機械のように動作するため、正規言語であればどのような言語でも決定することができます。したがって、この計算モデルは有限状態機械よりも強力です。

しかし、プッシュダウンオートマトンでも決定できない言語が存在することが判明しました。その結果は正規表現の場合と同様なので、ここでは詳しく説明しません。文脈自由言語にはポンピング補題が存在します。そのような言語の例として、素数の集合が挙げられます。

チューリングマシンの力

チューリングマシンは、プッシュダウンオートマトンでは決定できない言語（例えば素数からなる言語）に加え、あらゆる文脈自由言語を決定できます。したがって、チューリングマシンはより強力な計算モデルと言えます。

チューリングマシンは入力テープを「バックアップ」する機能を持つため、これまで説明した他の計算モデルでは不可能な方法で、長時間実行することが可能となります。ある入力に対しては実行を終了しない（停止しない）チューリングマシンを構築することも可能となります。チューリングマシンが最終的にすべての入力に対して停止し、答えを返す場合、その言語を決定できると言います。このように決定できる言語は、再帰言語と呼ばれます。さらに、ある言語の任意の入力に対しては最終的に停止し、答えを返すものの、その言語に含まれない入力文字列に対しては永遠に実行される可能性があるチューリングマシンについて説明できます。このようなチューリングマシンは、与えられた文字列がその言語に含まれると判断できますが、その動作に基づいて、与えられた文字列が言語に含まれないかどうかは決して確信できません。なぜなら、そのような場合、文字列は永遠に実行される可能性があるからです。このようなチューリングマシンが受け入れる言語は、再帰的に列挙可能な言語と呼ばれます。

チューリングマシンは、実のところ、極めて強力なオートマトンモデルです。チューリングマシンの定義を修正してより強力なマシンを作ろうとする試みは、驚くべきことに失敗に終わりました。例えば、チューリングマシンにテープを追加し、2次元（あるいは3次元、あるいは任意の次元）の無限面を扱えるようにすることは、基本的な1次元テープを持つチューリングマシンですべてシミュレートできます。したがって、これらのモデルはより強力ではありません。実際、チャーチ＝チューリングのテーゼの帰結として、チューリングマシンが決定できない言語を決定できる合理的な計算モデルは存在しないことが挙げられます。

では、問うべき疑問はこうだ。再帰的に列挙可能だが、再帰的ではない言語は存在するのか？さらに、再帰的に列挙可能でもない言語は存在するのか？

停止問題

停止問題は、計算可能性理論と日常業務におけるコンピュータの利用方法に深い影響を与えるため、コンピュータサイエンスにおいて最も有名な問題の一つです。この問題は次のように表現できます。

チューリングマシンとその初期入力の説明が与えられた場合、この入力でプログラムを実行した際に、停止（完了）するかどうかを判定してください。停止しない場合は、停止することなく永久に実行されます。

ここで問うているのは、素数や回文に関する単純な質問ではなく、立場を逆転させ、あるチューリングマシンに別のチューリングマシンに関する質問に答えさせるというものです。この質問にあらゆる場合に答えられるチューリングマシンを構築することは不可能であることが示されます（主要記事「停止問題」を参照）。

つまり、あるプログラムが特定の入力に対して常に停止するかどうかを確実に知る唯一の一般的な方法は、単にプログラムを実行して停止するかどうかを確認することです。停止すれば停止したと分かります。しかし、停止しない場合は、最終的に停止するかどうかは決して分かりません。すべてのチューリングマシン記述と、それらのチューリングマシンが最終的に停止する可能性のあるすべての入力ストリームを組み合わせた言語は、再帰的ではありません。したがって、停止問題は計算不可能または決定不能と呼ばれます。

停止問題の拡張はライスの定理と呼ばれ、与えられた言語が特定の非自明な特性を持つかどうかは（一般に）決定不可能であると述べられています。

再帰的に列挙可能な言語を超えて

しかし、停止問題は、それを決定するチューリングマシンが、それ自体は停止しないチューリングマシンの表現である入力を与えられた場合に、永遠に実行し続ける可能性があると仮定すれば、簡単に解決できます。したがって、停止言語は再帰的に列挙可能です。しかし、再帰的に列挙不可能な言語を構築することも可能です。

そのような言語の簡単な例として、停止言語の補集合が挙げられます。これは、入力文字列と対になっているすべてのチューリングマシンから成り、入力に対してチューリングマシンが停止しない言語です。この言語が再帰的に列挙可能でないことを確認するために、すべてのそのようなチューリングマシンに対して明確な答えを返すことができるが、最終的に停止するチューリングマシン上では永遠に実行できるチューリングマシン M を構築することを想像してください。次に、このマシンの動作をシミュレートする別のチューリングマシンを構築できます。このマシンは、2 つのプログラムの実行をインターリーブすることで、入力で与えられたマシンの実行を直接シミュレートします。直接シミュレーションは、シミュレートしているプログラムが停止すれば最終的に停止します。また、仮定により、入力プログラムが決して停止しない場合にはMのシミュレーションも最終的に停止するため、最終的には並列バージョンの 1 つが停止することがわかります。したがって、は停止問題の決定子です。しかしながら、停止問題は決定不可能であることを既に示しました。矛盾が生じ、Mが存在するという仮定が誤りであることが示されました。したがって、停止言語の補集合は再帰的に列挙可能ではありません。 $M'$ $M'$ $M'$

並行性ベースのモデル

並列ランダムアクセスマシンやペトリネットなど、並行性に基づく多くの計算モデルが開発されてきました。これらの並行計算モデルは、チューリングマシンで実装できない数学関数をまだ実装していません。

より強力な計算モデル

チャーチ＝チューリングのテーゼは、チューリングマシンよりも多くの数学関数を計算できる効果的な計算モデルは存在しないと推測しています。コンピュータ科学者は、チューリング計算可能性を超える計算モデルである ハイパーコンピュータの様々な種類を構想してきました。

無限実行

計算の各ステップが前のステップの半分の時間（そしてできればエネルギーも半分）で済むようなマシンを想像してみてください。最初のステップに必要な時間を1/2の時間単位（そして最初のステップに必要なエネルギーを1/2のエネルギー単位）に正規化すると、実行には

1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots

実行に単位時間（および1エネルギー単位）かかります。この無限級数は1に収束するため、このゼノマシンは1単位時間（1エネルギー単位）で可算無限ステップを実行できます。このマシンは、問題のマシンの実行を直接シミュレートすることで、停止問題を判定できます。拡張すると、任意の収束する無限級数（証明可能無限でなければならない）は機能します。無限級数が値nに収束すると仮定すると、ゼノマシンはn単位時間で可算無限の実行を完了します。

Oracleマシン

いわゆるオラクルマシンは、特定の決定不能問題に対する解を提供する様々な「オラクル」にアクセスできます。例えば、チューリングマシンは「停止オラクル」と呼ばれる機能を備えており、与えられた入力に対してチューリングマシンが停止するかどうかを即座に返します。これらのマシンは、再帰理論における中心的な研究テーマです。

ハイパーコンピューティングの限界

私たちが想像できるオートマトンの最限界を体現しているように見えるこれらのマシンでさえ、それぞれに限界があります。それぞれのマシンはチューリングマシンの停止問題を解くことができますが、それぞれのマシン自身の停止問題を解くことはできません。例えば、Oracleマシンは、あるOracleマシンが停止するかどうかという問いに答えることができません。

参照

参考文献

マイケル・シップサー（1997年）『計算理論入門』PWS出版、ISBN 0-534-94728-X。第2部：計算可能性理論、第3章～第6章、123～222ページ。
クリストス・パパディミトリウ(1993). 『計算複雑性』（第1版）. アディソン・ウェスリー. ISBN 0-201-53082-1。第3章: 計算可能性、pp.57–70。
S. バリー・クーパー(2004).計算可能性理論（第1版）. チャップマン＆ホール/CRC. ISBN 978-1-58488-237-4。