チューリング完全（計算におけるチューリング完全性）

定義上の特徴

チューリング完全であるためには、通常、無制限の量の情報を操作する手段と、条件分岐または反復制御を行う手段という二つの能力が必要となる。チューリングマシン、ラムダ計算、多くのレジスタマシンなど、これらの要件を満たす形式モデルは計算等価であり、相互にシミュレートできる。実用的な言語は、一般再帰、またはそれと等価な反復およびメモリの機構を実装できる場合、チューリング完全とみなされる。

歴史と理論的背景

この概念は、抽象的な機械とオートマトンを普遍的なモデルと比較した計算理論の基礎的研究に由来する。チューリングマシンは、アルゴリズム的計算を定義するための単純で強力な形式的装置として導入された。これを模倣できるシステムは、その計算能力を受け継ぐ。この呼称が強調するのは、性能や使いやすさではなく、理論上の能力である。

例と一般的な区別

現代の汎用プログラミング言語の多くはチューリング完全である。代表的な例と比較は次のとおりである。

• ループと無制限のメモリをサポートする汎用言語およびランタイム環境（インタプリタ、仮想マシン）は、チューリング完全である。
• HTMLのような純粋なマークアップ言語は、それ自体には無制限の状態変化を行う固有の機構がないため、チューリング完全ではない。ただし、スクリプティング、たとえばJavaScriptと組み合わせることで、チューリング完全なシステムを構成できる。
• 標準的な正規表現は有限オートマトンに対応し、チューリング完全ではない。一方、一部の正規表現エンジンは後方参照などの拡張を加え、正規言語を超える表現力を持たせている。これは決定可能性を複雑にし、より強力になる一方で予測しにくくなることが多い。正規表現も参照。
• Rule 110やコンウェイのライフゲームなどのセル・オートマトンを含む、単純または難解なシステムには、最小限の規則にもかかわらず万能計算が可能であることが証明されたものがある。これは、チューリング完全性が予想外の文脈にも現れうることを示している。

用途、重要性と含意

システムがチューリング完全であると確認することは、原理上、他のあらゆる汎用モデルと同等の表現力を持つことを示す。これは実用面と理論面の両方に影響する。すなわち、高水準言語が相互のアルゴリズムを実装できる理由、コンパイラやインタプリタが異なるパラダイム間で翻訳できる理由、そして停止性問題など特定の決定問題がチューリング完全なシステムでは一般に決定不能である理由を説明する。実際には、資源の制約、アーキテクチャ上の制限、言語機能により、理論的に可能な計算でも実行不能となることがある。

限界と注目すべき事実

チューリング完全性が扱うのは何が計算できるかであり、どれほど効率よく計算できるかではない。あるシステムがチューリング完全であっても、多くの課題には著しく非実用的でありうる。反対に、安全性、解析、最適化のために言語を意図的に制限すると、しばしばチューリング完全性は失われるが、決定可能な性質やより単純な推論が得られる。システムを評価する際は、理論上の万能性と、メモリ制限、実行時間、副作用といった現実世界の要因とを区別することが有用である。

より技術的な背景と形式的定義については、計算可能性理論および抽象的な機械とオートマトンの研究を参照。現代の議論では、チューリングマシン、主流のプログラミング言語、ならびにHTMLとJavaScriptのようなマークアップとスクリプトの組み合わせ、さらに正規表現の表現力の限界など、実用的な例がしばしば参照される。