チューリング完全性

計算可能性理論では、データ操作ルールのシステム（計算モデル、コンピュータの命令セット、プログラミング言語、セルオートマトンなど）は、任意のチューリングマシン^{[ 1 ] [ 2 ]}（イギリスの数学者でコンピュータ科学者のアラン・チューリングによって考案されたもの）をシミュレートできる場合、チューリング完全または計算的に普遍的であると言われます。これは、このシステムが他のデータ操作ルールセットを認識または解読できることを意味します。チューリング完全性は、このようなデータ操作ルールセットの能力を表現する方法として使用されます。今日では、事実上すべてのプログラミング言語がチューリング完全です。^{[ a ]}

関連する概念としてチューリング等価性がある。2台のコンピュータPとQは、PがQをシミュレートでき、QがPをシミュレートできる場合に等価であると呼ばれる。^{[ 4 ]}チャーチ＝チューリングのテーゼは、アルゴリズムによって値を計算できる関数はチューリングマシンによって計算でき、したがって、現実世界のコンピュータがチューリングマシンをシミュレートできる場合、それはチューリングマシンとチューリング等価であると推測している。ユニバーサルチューリングマシンは、任意のチューリングマシンをシミュレートするために使用でき、ひいては、あらゆる現実世界のコンピュータの純粋に計算的な側面をシミュレートすることができる。^{[ 5 ] [ 6 ]} 

何かがチューリング完全であることを示すには、それが何らかのチューリング完全システムをシミュレートするために使用できることを示すだけで十分です。物理システムには無限のメモリはありませんが、有限メモリの制限を無視すれば、ほとんどのプログラミング言語はそれ以外はチューリング完全です。^{[ 7 ] [ 8 ]}

日常会話では、「チューリング完全」および「チューリング等価」という用語は、あらゆる実世界の汎用コンピュータまたはコンピュータ言語が、他の実世界の汎用コンピュータまたはコンピュータ言語の計算処理を近似的にシミュレートできることを意味します。現実世界では、これはコンピュータ仮想化とエミュレーションという実用的な概念につながります。

これまでに構築された実際のコンピュータは、単一テープ式チューリングマシン（メモリとして「テープ」を使用する）のように機能的に解析できます。そのため、その動作を十分に抽象化することで、関連する数学的手法を適用できます。しかし、実際のコンピュータは物理的なリソースが限られているため、線形限定オートマトンとしてしか完全ではありません。これに対し、汎用コンピュータの抽象化は、チューリング完全な命令セット、無限のメモリ、および無限の利用可能な時間を持つデバイスとして定義されます。

計算可能性理論では、計算システム（抽象機械やプログラミング言語など）の計算能力を説明するために、密接に関連するいくつかの用語が使用されます。

チューリング完全性

チューリング計算可能なすべての関数を計算できる計算システムは、チューリング完全（またはチューリング強力）と呼ばれる。言い換えれば、そのようなシステムは、万能チューリングマシンをシミュレートできるシステムである。

チューリング等価性

チューリング完全なシステムは、計算可能なすべての関数がチューリング計算可能である場合、チューリング等価であると呼ばれます。つまり、チューリングマシンと全く同じクラスの関数を計算するシステムです。あるいは、チューリング等価システムとは、汎用チューリングマシンをシミュレートでき、かつ汎用チューリングマシンによってシミュレートされるシステムのことです。（既知の物理的に実装可能なチューリング完全なシステムはすべてチューリング等価であり、これはチャーチ＝チューリングのテーゼを裏付けるものです。）

（計算上の）普遍性

あるシステムが、そのシステム群に関して普遍的であるとは、そのシステムがそのシステム群に含まれるシステムによって計算可能なすべての関数を計算できる場合（または、それらのシステムそれぞれをシミュレートできる場合）を指します。一般的に、「普遍性」という用語は、暗黙のうちにチューリング完全なシステム群に関して用いられます。「弱普遍性」という用語は、入力ストリームに無限個の1が含まれるようにチューリングマシンの標準定義を変更することによってのみ普遍性が達成されるシステム（例えば、セルオートマトン）を区別するために用いられることがあります。

チューリング完全性とは、あらゆる現実世界の計算装置の設計を万能チューリングマシンでシミュレートできるという点で重要な概念である。チャーチ＝チューリングのテーゼは、これが数学の法則であると述べている。すなわち、万能チューリングマシンは、原理的には、他のあらゆるプログラム可能なコンピュータが実行できる計算を実行できるということである。これは、プログラムを作成するのに必要な労力や、マシンが計算を実行するのにかかる時間、あるいは計算とは無関係なマシンの能力については何も語っていない。 

チャールズ・バベッジの解析機関（1830年代）は、設計当時に製造されていれば、最初のチューリング完全な機械になっていただろう。バベッジは、この機械が原始的な論理推論を含む高度な計算能力を備えていることを認識していたが、他のどの機械もこれより優れた計算はできないことを理解していなかった。1830年代から1940年代にかけて、加算器や乗算器などの機械式計算機が製造され、改良が加えられたが、条件分岐を実行できなかったため、チューリング完全ではなかった。

19世紀後半、レオポルド・クロネッカーは計算可能性の概念を定式化し、原始再帰関数を定義した。これらの関数は定型計算で計算できるが、計算命令が無限ループを許容しないため、万能コンピュータを作るには不十分である。20世紀初頭、ダヴィッド・ヒルベルトは、機械で実行可能な正確な公理と正確な論理的推論規則を用いて、数学全体を公理化するプログラムを主導した。やがて、少数の推論規則で任意の公理の帰結を導き出せることが明らかになった。これらの規則は、 1930年にクルト・ゲーデルによって、あらゆる定理を導き出すのに十分であることが証明された。

計算という概念そのものは、ゲーデルの不完全性定理を皮切りに、すぐに分離された。この定理は、公理系が定理を導出する計算について推論する際に限界があることを示した。チャーチとチューリングは、ヒルベルトの決定問題が解けないことをそれぞれ独立に証明し^{[ 9 ]}、不完全性定理の計算の中核を特定した。この研究は、ゲーデルの一般再帰関数に関する研究と相まって、単純な命令の集合が存在し、それらを組み合わせることであらゆる計算を生成できることを確立した。ゲーデルの研究は、計算という概念が本質的に唯一無二であることを示した。

1941年、コンラート・ツーゼはZ3コンピュータを完成させた。ツーゼは当時、チューリングの計算可能性に関する研究を知らなかった。特に、Z3には条件付きジャンプ専用の機能がなかったため、チューリング完全ではなかった。しかし、1998年にロハスによって、Z3は条件付きジャンプをシミュレートできるため、理論的にはチューリング完全であることが示された。これを行うには、テーププログラムは、すべての分岐の両側を通るすべての可能なパスを実行できるほど長くなければならない。^{[ 10 ]}

実際に条件分岐が可能で、したがって実際にチューリング完全である最初のコンピュータは、 1946年のENIACでした。ZuseのZ4コンピュータは1945年に稼働していましたが、1950年まで条件分岐をサポートしていませんでした。^{[ 11 ]}

計算可能性理論は、計算モデルを用いて問題を分析し、計算可能かどうか、またどのような状況下で計算可能かを判断する。計算可能性理論の最初の成果は、チューリング完全なシステムが任意の長い時間にわたって何をするかを予測することが不可能な問題が存在するということである。

典型的な例は停止問題です。これは、チューリング完全な言語で書かれたプログラムと、そのプログラムに入力するデータを受け取り、入力に対してプログラムが最終的に停止するか、それとも永遠に実行され続けるかを判定するアルゴリズムを作成する問題です。特定の入力に対しては、このようなアルゴリズムを作成するのは容易ですが、一般的には不可能です。プログラムの最終的な出力のいかなる特性についても、その特性が成り立つかどうかを判断することは不可能です。

この不可能性は、実際のコンピュータプログラムを分析する際に問題となる。例えば、プログラマーが無限ループを記述するのを完全に防いだり、ユーザーが無限ループを引き起こすような入力を与えるのを完全に防いだりするツールを作成することは不可能である。

代わりに、プログラムの実行時間を一定期間に制限する（タイムアウト）か、フロー制御命令の機能を制限（例えば、既存の配列の要素を反復するループのみを提供する）することができます。しかし、別の定理によれば、チューリング完全な言語で解決できる問題の中には、有限ループ機能しか持たない言語（つまり、すべてのプログラムが最終的に停止することを保証する言語）では解決できない問題があります。したがって、そのような言語はチューリング完全ではありません。例えば、プログラムが必ず完了して停止することが保証されている言語では、その言語のすべての計算可能な関数に対してカントールの対角線論法によって生成される計算可能な関数を計算することはできません。

無限のデータテープにアクセスできるコンピュータは、チューリングマシンよりも強力になる可能性がある。例えば、そのテープには停止問題やその他のチューリング不可問題の解が含まれているかもしれない。このような無限のデータテープはチューリングオラクルと呼ばれる。ランダムなデータを持つチューリングオラクルでさえ、計算は可算個しかないのに対し、オラクルは非可算個しかないため、計算不可能である（確率1）。したがって、ランダムなチューリングオラクルを持つコンピュータは、チューリングマシンでは計算できないことを計算できる。

既知の物理法則はすべて、デジタルコンピュータ上での一連の近似によって計算可能な結果を​​もたらす。デジタル物理学と呼ばれる仮説は、宇宙自体が万能チューリングマシンで計算可能であるため、これは偶然ではないと述べている。これは、万能チューリングマシンよりも強力なコンピュータは物理的に構築できないことを意味する。^{[ 12 ]}

チューリング完全システムとして議論される計算システム（代数、計算体系）は、理論計算機科学の研究を目的としたものです。これらは、計算の限界を理解しやすくするために、できるだけ単純になるように設計されています。以下にいくつか例を挙げます。

• オートマトン理論
• 形式文法（言語生成器）
• 形式言語（言語認識器）
• ラムダ計算
• ポストチューリングマシン
• プロセス計算

ほとんどのプログラミング言語（抽象モデル、場合によっては有限メモリを前提とする特定の構成要素は省略されているかもしれない）は、従来型であれ非従来型であれ、チューリング完全である。これには以下が含まれる。

• 汎用言語はすべて広く使われている。
  • C、Pascalなどの手続き型プログラミング言語。
  • Java、Smalltalk、C#などのオブジェクト指向言語。
  • Ada、C++、Common Lisp、Fortran、JavaScript、Object Pascal、Perl、Python、Rなどのマルチパラダイム言語。
• あまり一般的でないパラダイムを使用する言語のほとんど：
  • LispやHaskellのような関数型言語。
  • Prologなどの論理プログラミング言語。
  • m4などの汎用マクロプロセッサ。
  • SQLやXSLTなどの宣言型言語。^{[ 13 ] [ 14 ]}
  • VHDLおよびその他のハードウェア記述言語。
  • TeXは、組版システムの一種です。
  • 難解なプログラミング言語とは、プログラマーが極めて難解ではあるものの数学的にチューリング等価な言語で基本的なプログラミング構造を実現する方法を考案する、数学的な娯楽の一形態である。

一部の書き換えシステムはチューリング完全である。

チューリング完全性とは、その能力を実装するために使用される特定の言語機能の規定ではなく、能力の抽象的な記述です。チューリング完全性を達成するために使用される機能はかなり異なる場合があります。Fortran システムでは、繰り返しを実現するためにループ構造または場合によってはgoto文を使用します。Haskell と Prolog は、ループをほとんど完全に欠いているため、再帰を使用します。ほとんどのプログラミング言語は、メモリ (RAM とレジスタ) と制御ユニットを備えたフォン ノイマン アーキテクチャ上の計算を記述しています。これら 2 つの要素により、このアーキテクチャはチューリング完全になります。純粋関数型言語でさえチューリング完全です。^{[ 15 ] [ 16 ]}

宣言型SQLにおけるチューリング完全性は、再帰的な共通テーブル式によって実現されます。当然のことながら、SQLの手続き型拡張（PL/SQLなど）もチューリング完全です。これは、比較的強力な非チューリング完全言語が稀である理由の一つを示しています。つまり、言語が当初強力であればあるほど、適用されるタスクは複雑になり、完全性の欠如が欠点として認識されるのが早くなり、チューリング完全になるまで拡張が促されるのです。

型なしラムダ計算はチューリング完全ですが、System Fを含む多くの型付きラムダ計算はそうで​​はありません。型付きシステムの価値は、ほとんどの典型的なコンピュータプログラムを表現できると同時に、より多くのエラーを検出できる点にあります。

ルール110とコンウェイのライフゲームは、どちらもセルオートマトンであり、チューリング完全である。

チューリング完全ではない計算言語は数多く存在する。その一例として、正規表現によって生成され、有限オートマトンによって認識される正規言語が挙げられる。有限オートマトンを拡張した、より強力ではあるもののチューリング完全ではないものとして、プッシュダウンオートマトンと文脈自由文法のカテゴリがあり、これらはプログラムコンパイルの初期段階で構文解析ツリーを生成するためによく用いられる。その他の例としては、 Direct3DやOpenGL拡張機能に組み込まれたピクセルシェーダー言語の初期バージョンなどが挙げられる。

CharityやEpigramのような完全関数型プログラミング言語では、すべての関数は完全であり、必ず終了しなければなりません。Charityは型システムと圏論に基づく制御構造を使用しますが、Epigramは依存型を使用します。LOOP言語は、原始再帰関数のみを計算するように設計されています。これらの言語はすべて、計算可能な関数の完全な集合が計算可能列挙可能ではないため、計算可能な関数の適切な部分集合を計算します。また、これらの言語のすべての関数は完全であるため、チューリングマシンとは対照的に、再帰的に列挙可能な集合のアルゴリズムをこれらの言語で記述することはできません。

（型付けのない）ラムダ計算はチューリング完全であるが、単純な型付けのあるラムダ計算はチューリング完全ではない。

• 「チューリング完全」。wiki.c2.com 。