計算理論

理論計算機科学と数学において、計算理論は、計算モデルでアルゴリズムを使用してどのような問題を解決できるか、それらの問題をどの程度効率的に、またはどの程度（例えば、近似解と正確な解）解決できるかを扱う分野である。この分野は、オートマトン理論と形式言語、計算可能性理論、計算複雑性理論の3つの主要な分野に分かれており、これらは「コンピュータの基本的な機能と限界は何か？」という質問によって結びついている。 ^[1]

計算の厳密な研究を行うために、コンピュータ科学者は計算モデルと呼ばれるコンピュータの数学的抽象化に取り組んでいます。使用されているモデルはいくつかありますが、最も一般的に研究されているのはチューリングマシンです。^[2]コンピュータ科学者がチューリングマシンを研究するのは、定式化が簡単で、分析して結果を証明するのに使用でき、多くの人が最も強力で「合理的な」計算モデルであると考えるものを表すためです (チャーチ–チューリングのテーゼを参照)。^[3]潜在的に無限のメモリ容量は実現不可能な属性のように思えるかもしれませんが、チューリングマシンによって解決される決定可能な問題^[4]は常に有限量のメモリしか必要としません。したがって、原理的には、チューリングマシンによって解決 (決定) できる問題は、有限量のメモリを持つコンピュータによって解決できます。

計算理論は、コンピュータサイエンスの分野におけるあらゆる種類のモデルの作成と考えることができます。そのため、数学と論理が使用されます。前世紀には、数学から分離して独立した学問分野となり、 1960年のFOCSや1969年のSTOCなどの独自の会議、IMUアバカスメダル（1981年にロルフネヴァンリンナ賞として設立）、 1993年に設立されたゲーデル賞、 1996年に設立されたクヌース賞などの独自の賞が設けられました。

計算理論の先駆者としては、ラモン・リュイ、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、スティーブン・クリーネ、ローザ・ペーテル、ジョン・フォン・ノイマン、クロード・シャノンなどが挙げられます。

オートマトン理論は、抽象機械（より適切には、抽象的な「数学的」機械またはシステム）と、これらの機械を使用して解決できる計算上の問題を研究する分野です。これらの抽象機械はオートマトンと呼ばれます。オートマトンとは、ギリシャ語の（Αυτόματα）に由来し、何かがそれ自体で何かを行っていることを意味します。オートマトン理論は形式言語理論とも密接に関連しており、^[5]オートマトンが認識できる形式言語のクラスによって分類されることがよくあります。オートマトンとは、無限集合である可能性のある形式言語の有限表現である場合があります。オートマトンとは、計算機の理論モデルとして使用され、計算可能性の証明に使用されます。

言語理論は、言語をアルファベット上の一連の演算として記述する数学の一分野です。オートマトンが形式言語の生成と認識に使用されるため、言語理論はオートマトン理論と密接に関連しています。形式言語にはいくつかのクラスがあり、それぞれがそれ以前のものよりも複雑な言語仕様、つまりチョムスキー階層[6]を許可し、それぞれ^がそれを認識するオートマトンクラスに対応しています。オートマトンが計算のモデルとして使用されるため、計算が必要なあらゆる問題には形式言語が仕様の好ましいモードです。

計算可能性理論は、主に問題がコンピュータ上でどの程度解けるかという問題を扱っています。停止問題はチューリングマシンでは解けないという主張^[7]は、計算可能性理論における最も重要な結果の1つです。これは、定式化が容易でありながらチューリングマシンでは解けない具体的な問題の例だからです。計算可能性理論の多くは、停止問題の結果に基づいています。

計算可能性理論におけるもう一つの重要なステップはライスの定理であり、これは部分関数のすべての非自明な性質に対して、チューリングマシンがその性質を持つ部分関数を計算できるかどうかは決定不可能であるということを述べている。^[8]

計算可能性理論は、再帰理論と呼ばれる数理論理学の分野と密接に関連しており、再帰理論は、チューリングモデルに還元可能な計算モデルのみを研究するという制限を取り除きます。^[9] 再帰理論を研究する多くの数学者や計算理論家は、それを計算可能性理論と呼びます。

複雑性理論では、問題がコンピュータ上で解決できるかどうかだけでなく、問題がどれだけ効率的に解決できるかも考慮されます。考慮される主な側面は、時間の複雑さと空間の複雑さです。時間の複雑さは、計算を実行するのに何ステップ必要か、その計算を実行するのにどれだけのメモリが必要かを表します。

特定のアルゴリズムに必要な時間とスペースを分析するために、コンピュータ科学者は、問題を解決するのに必要な時間やスペースを、入力された問題のサイズの関数として表現します。たとえば、長い数字のリストから特定の数字を見つけることは、数字のリストが大きくなるにつれて難しくなります。リストにn個の数字があるとすると、リストが何らかの方法でソートまたはインデックス付けされていない場合、探している数字を見つけるためにすべての数字を調べる必要がある場合があります。したがって、この問題を解決するには、問題のサイズに応じて線形に増加するステップの数をコンピュータで実行する必要があると言えます。

この問題を単純化するために、コンピュータ科学者はビッグオー記法を採用しました。ビッグオー記法では、マシンの構造の特定の側面を考慮する必要がなく、問題が大きくなるにつれて漸近的な動作のみを考慮するだけで済むような方法で関数を比較できます。したがって、前の例では、問題を解決するにはステップが必要であると言えるでしょう。 ${\displaystyle O(n)}$

おそらく、コンピュータ サイエンス全体の中で最も重要な未解決問題は、 NPと表記される特定の広範な問題クラスが効率的に解決できるかどうかという問題です。これについては、複雑性クラス P および NPでさらに詳しく説明されています。P対 NP 問題は、 2000 年にクレイ数学研究所によって発表された7 つのミレニアム懸賞問題の 1 つです。公式の問題の説明は、チューリング賞受賞者のStephen Cookによって与えられました。

チューリングマシン以外にも、同等の計算モデル（チャーチ＝チューリングのテーゼを参照）が使用されています。

ラムダ計算

計算は、最初のラムダ式（関数とその入力を分離する場合は 2 つ）と、ベータ削減を 1 回適用して前の項から推定されたラムダ項の有限シーケンスで構成されます。

組み合わせ論理

は、-計算と多くの類似点を持つ概念ですが、重要な違いも存在します (例: 不動点コンビネータYは、組み合わせ論理では通常の形式を持ちますが、-計算では通常の形式を持ちません)。組み合わせ論理は、パラドックスの性質を理解し、数学の基礎をより経済的に (概念的に)、変数の概念を排除する (したがって、数学におけるその役割を明確にする) という大きな野心を持って開発されました。${\displaystyle \lambda}$${\displaystyle \lambda}$

μ再帰関数

計算は、μ 再帰関数、つまりその定義シーケンス、任意の入力値、および定義シーケンスに現れる入力と出力を伴う再帰関数のシーケンスで構成されます。したがって、再帰関数の定義シーケンスに関数とが現れる場合、形式 'g(5)=7' または 'h(3,2)=10' の項が現れることがあります。このシーケンスの各エントリは、基本関数の適用であるか、合成、原始再帰、またはμ 再帰を使用して上記のエントリから続く必要があります。たとえば、の場合、'f(5)=3' が現れるには、上記で 'g(5)=6' や 'h(5,6)=3' などの項が現れる必要がある。最後の項が入力に適用された再帰関数の値を与える場合にのみ、計算は終了します。${\displaystyle f(x)}$${\displaystyle g(x)}$${\displaystyle h(x,y)}$${\displaystyle f(x)=h(x,g(x))}$

マルコフアルゴリズム

文法のような規則を使用して記号の文字列を操作する文字列書き換えシステム。

レジスターマシン

は理論的に興味深いコンピュータの理想化です。いくつかのバリエーションがあります。それらのほとんどでは、各レジスタは自然数（無制限のサイズ）を保持でき、命令は単純（かつ数が少ない）で、たとえばデクリメント（条件付きジャンプと組み合わせる）とインクリメント（および停止）のみ存在します。無限（または動的に増加する）外部ストア（チューリングマシンに見られる）がないことは、その役割をゲーデルの番号付け技法に置き換えることで理解できます。各レジスタが自然数を保持するという事実は、複雑なもの（たとえば、シーケンスやマトリックスなど）を適切に巨大な自然数で表現する可能性を可能にします。表現と解釈の両方の明確さは 、これらの技法の数論的基礎によって確立できます。

一般的な計算モデルに加えて、より単純な計算モデルが、特別な制限されたアプリケーションに役立ちます。 たとえば、正規表現は、オフィス生産性ソフトウェアからプログラミング言語まで、多くのコンテキストで文字列パターンを指定します。正規表現と数学的に同等な別の形式である有限オートマトンが、回路設計やいくつかの種類の問題解決に使用されます。文脈自由文法は、 プログラミング言語の構文を指定します。非決定性プッシュダウンオートマトンも、文脈自由文法と同等の別の形式です。原始再帰関数は、再帰関数の定義済みサブクラスです。

計算モデルが異なれば、実行できるタスクも異なります。計算モデルの能力を測定する方法の 1 つは、モデルが生成できる形式言語のクラスを調べることです。この方法で、言語のチョムスキー階層が得られます。

コンピュータ科学者向けの教科書

(この分野には多くの教科書があるため、このリストは必然的に不完全です。)

• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2006) [1979].オートマトン理論、言語、計算入門(第 3 版). Addison-Wesley. ISBN 0-321-45536-3。— この分野の標準的な参考文献の 1 つ。
• リンツ P (2007)。形式言語とオートマトンの紹介。ナローサ出版。ISBN 9788173197819。
• シプサー、マイケル(2013)。計算理論入門(第 3 版)。Cengage Learning。ISBN 978-1-133-18779-0。
• エイタン・グラリ (1989)。『計算理論入門』。コンピュータサイエンス・プレス。ISBN 0-7167-8182-42007年1月7日時点のオリジナルよりアーカイブ。
• Hein, James L. (1996) 『計算理論』。 マサチューセッツ州サドベリー: Jones & Bartlett。ISBN 978-0-86720-497-1コンピューターサイエンスの学部2年生に適した、この分野のやさしい入門書。 
• Taylor, R. Gregory (1998)。『計算モデルと形式言語』。 ニューヨーク: Oxford University Press。ISBN 978-0-19-510983-2非常に読みやすい教科書で 、上級レベルの学部生や大学院の初級者に適しています。 
• Jon Kleinberg、Éva Tardos (2006): Algorithm Design、Pearson/Addison-Wesley、ISBN 978-0-32129535-4
• Lewis, FD (2007)。理論計算機科学の基礎形式言語、オートマトン、文法のトピックを扱った教科書。結果の証明よりも、結果とその応用の概要を示すことに重点が置かれているようです。
• Martin Davis、Ron Sigal、Elaine J. Weyuker、『計算可能性、複雑性、言語：理論計算機科学の基礎』第 2 版、Academic Press、1994 年、ISBN 0-12-206382-1 。プログラム意味論や数量化理論など、他のほとんどの入門書よりも幅広いトピックを扱っています。大学院生向け。 

（より広い）数学的観点からの計算可能性理論に関する書籍

• ハートリー・ロジャース・ジュニア（1987年）。再帰関数と実効計算可能性の理論、 MIT Press。ISBN 0-262-68052-1 
• S. バリー・クーパー(2004)。計算可能性理論。チャップマン・アンド・ホール/CRC。ISBN 1-58488-237-9。。
• Carl H. Smith、『計算理論への再帰的入門』、Springer、1994 年、ISBN 0-387-94332-3。コンピュータ サイエンスの大学院生に適した短い教科書。 

歴史的観点

• Richard L. Epstein および Walter A. Carnielli (2000)。 『Computability: Computable Functions, Logic, and the Foundations of Mathematics』、および『Computability: A Timeline 』(第 2 版)。Wadsworth/Thomson Learning。ISBN 0-534-54644-7。。

• MITにおける計算理論
• ハーバード大学の計算理論
• 計算可能性論理 - インタラクティブ計算の理論。このテーマに関する主要な Web ソース。