計算理論

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

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

計算理論は、コンピュータ科学の分野におけるあらゆる種類のモデルの構築とみなすことができる。そのため、数学と論理学が用いられる。20世紀には、数学から分離し、独立した学問分野となり、1960年のFOCSや1969年のSTOCといった独自の学会や、 IMUそろばんメダル（1981年にロルフ・ネヴァンリンナ賞として設立）、 1993年に設立されたゲーデル賞、1996年に設立されたクヌース賞といった独自の賞を持つようになった。

計算理論の先駆者には、ラモン・リュル、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、スティーブン・クリーネ、ローザ・ペーター、ジョン・フォン・ノイマン、クロード・シャノンなどがいる。

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

ラムダ計算

計算は、初期ラムダ式（関数とその入力を分離したい場合は2つ）と、ベータ還元を1回適用することによって前の項から導出される有限個のラムダ項のシーケンスで構成されます。

組み合わせ論理

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

μ-再帰関数

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

マルコフアルゴリズム

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

レジスターマシン

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

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

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

コンピュータ科学者を対象とした教科書

（この分野には多くの教科書があり、このリストは必然的に不完全なものです。）

• ホップクロフト、ジョン・E.、モトワニ、ラジーブ、ウルマン、ジェフリー・D. (2006) [1979].オートマタ理論、言語、計算入門（第3 版）. アディソン・ウェスリー. ISBN 0-321-45536-3。―この分野における標準的な参考文献の一つ。
• リンツ P (2007)。形式言語とオートマトンの紹介。ナローサ出版。ISBN 9788173197819。
• Sipser, Michael (2013).計算理論入門（第3 版）. Cengage Learning. ISBN 978-1-133-18779-0。
• エイタン・グラリ（1989）。『計算理論入門』コンピュータサイエンスプレス。ISBN 0-7167-8182-42007年1月7日にオリジナルからアーカイブされました。
• ハイン、ジェームズ・L. (1996)計算理論。 マサチューセッツ州サドベリー：ジョーンズ＆バートレット 。ISBN 978-0-86720-497-1コンピュータサイエンス学科の2年生向けに、この分野への分かりやすい入門書として最適です。
• Taylor, R. Gregory (1998).計算モデルと形式言語. ニューヨーク: オックスフォード大学出版局. 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コンピュータサイエンスの大学院生に適した、より簡潔な教科書。

歴史的視点

• リチャード・L・エプスタイン、ウォルター・A・カーニエリ（2000）。『計算可能性：計算可能な関数、論理、数学の基礎』、および『計算可能性：タイムライン』（第2版）。ワズワース／トムソン・ラーニング。ISBN 0-534-54644-7。。

• マサチューセッツ工科大学（MIT）の計算理論
• ハーバード大学における計算理論
• 計算可能性論理― 対話型計算の理論。この分野に関する主要なウェブサイト。