チューリング完全性

計算可能性理論では、データ操作ルールのシステム（計算モデル、コンピュータの命令セット、プログラミング言語、セルオートマトンなど）は、任意のチューリングマシン^（英国の数学者でコンピュータ科学者のアラン・チューリングが考案^）をシミュレートするために使用できる場合、チューリング完全または計算汎用性^があると言われます。これは、このシステムが他のデータ操作ルールセットを認識またはデコードできることを意味します。チューリング完全性は、そのようなデータ操作ルールセットの威力を表現する方法として使用されます。今日のほぼすべてのプログラミング言語はチューリング完全です。^[a]

関連する概念として、チューリング等価性があります 。P と Q という 2 つのコンピュータは、P が Q をシミュレートでき、Q が P をシミュレートできる場合、同等であると言えます。 ^[要出典]チャーチ＝チューリングのテーゼでは、アルゴリズムによって値を計算できる関数はすべてチューリング マシンで計算できると推測されており、したがって、現実世界のコンピュータがチューリング マシンをシミュレートできる場合、そのコンピュータはチューリング マシンとチューリング等価です。汎用チューリング マシンは、あらゆるチューリング マシンをシミュレートするために使用でき、ひいてはあらゆる現実世界のコンピュータの純粋に計算的な側面をシミュレートできます。^[要出典]

何かがチューリング完全であることを示すには、それが何らかのチューリング完全なシステムをシミュレートできることを実証するだけで十分です。無限のメモリを持つ物理的なシステムは存在しませんが、有限のメモリの制限を無視すれば、ほとんどのプログラミング言語はチューリング完全です。^[要出典]

口語では、「チューリング完全」および「チューリング同等」という用語は、現実世界の汎用コンピュータまたはコンピュータ言語が、他の現実世界の汎用コンピュータまたはコンピュータ言語の計算面を近似的にシミュレートできるという意味で使用されます。現実の世界では、これはコンピューティングの仮想化とエミュレーションの実用的な概念につながります。^{[引用が必要]}

これまでに構築された実際のコンピュータは、単一テープ チューリング マシン (メモリとして「テープ」を使用) のように機能的に分析できます。したがって、操作を十分に抽象化することで、関連する数学を適用できます。ただし、実際のコンピュータは物理的なリソースが限られているため、線形制限オートマトン完全です。対照的に、汎用コンピュータの抽象化は、チューリング完全な命令セット、無限のメモリ、および無限の使用可能時間を備えたデバイスとして定義されます。^{[引用が必要]}

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

チューリング完全性

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

チューリング等価性

チューリング完全なシステムは、それが計算できるすべての関数がチューリング計算可能である場合、チューリング同等と呼ばれます。つまり、チューリングマシンが計算するのとまったく同じクラスの関数を計算します。あるいは、チューリング同等のシステムとは、汎用チューリングマシンをシミュレートでき、汎用チューリングマシンによってシミュレートされるシステムです。(物理的に実装可能な既知のチューリング完全なシステムはすべてチューリング同等であり、チャーチ-チューリングのテーゼを裏付けています。^{[引用が必要]} )

（計算上の）普遍性

あるクラスのシステムで計算可能なすべての関数を計算できる場合 (または、それらの各システムをシミュレートできる場合)、システムはそのクラスのシステムに関して普遍的であると呼ばれます。通常、「普遍性」という用語は、チューリング完全なクラスのシステムに関して暗黙的に使用されます。「弱い普遍性」という用語は、チューリング マシンの標準定義を変更して、無限の数の 1 を持つ入力ストリームを含めることによってのみ普遍性が達成されるシステム (セル オートマトンなど) を区別するために使用されることがあります。

チューリング完全性は、現実世界のあらゆるコンピューティング デバイスの設計が、ユニバーサル チューリング マシンによってシミュレートできるという点で重要です。チャーチ- チューリングのテーゼでは、これは数学の法則であり、ユニバーサル チューリング マシンは、原理的には、他のプログラム可能なコンピューターが実行できるあらゆる計算を実行できると述べています。これは、プログラムの作成に必要な労力や、マシンが計算を実行するのにかかる時間、または計算とはまったく関係のないマシンの能力については何も述べていません。

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

19 世紀後半、レオポルド クロネッカーは計算可能性の概念を定式化し、原始再帰関数を定義しました。これらの関数は暗記計算で計算できますが、計算する命令が無限ループを許可していないため、汎用コンピュータを作成するには不十分です。20 世紀初頭、デビッド ヒルベルトは、機械で実行できる正確な公理と正確な論理的演繹規則を使用して、すべての数学を公理化するプログラムを主導しました。すぐに、少数の演繹規則で、あらゆる公理のセットの結果を生み出すのに十分であることが明らかになりました。これらの規則は、 1930 年にクルト ゲーデルによって、あらゆる定理を生み出すのに十分であることが証明されました。

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

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

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

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

典型的な例は停止問題です。チューリング完全な言語で書かれたプログラムとそのプログラムに与えられるデータを入力として受け取り、入力に基づいて動作するプログラムが最終的に停止するか、永久に継続するかを判断するアルゴリズムを作成します。一部の入力に対してこれを実行できるアルゴリズムを作成するのは簡単ですが、一般には不可能です。プログラムの最終的な出力のどの特性についても、その特性が維持されるかどうかを判断することは不可能です。

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

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

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

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

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

• オートマトン理論
• 形式文法（言語ジェネレーター）
• 形式言語（言語認識装置）
• ラムダ計算
• ポストチューリングマシン
• プロセス計算

従来のプログラミング言語も非従来のプログラミング言語も、ほとんどがチューリング完全です (その抽象モデル、おそらく有限のメモリを前提とする特定の構造は省略されています)。これには次のものが含まれます。

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

いくつかの書き換えシステムはチューリング完全です。

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

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

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

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

一部のソフトウェアやビデオゲームは、意図的ではなく偶然にチューリング完全です。

ソフトウェア：

• マイクロソフトエクセル^[10]

ゲーム:

• ドワーフ要塞^[11]
• シティーズ：スカイライン^[12]
• オプス・マグナム^[13]
• マインクラフト^[14]
• マジック：ザ・ギャザリング^{[15] [16]}
• 無限グリッドマインスイーパ^[17]

ソーシャルメディア:

• ハッボホテル^[18]

計算言語:

• C++テンプレート^[19]
• printf書式文字列^[20]
• TypeScriptの型システム^[21]
• x86アセンブリのMOV命令^{[22] [23] [24]}

生物学:

• 化学反応ネットワーク^{[25] [26] [27] [28]}と酵素ベースのDNAコンピュータ^[29]はチューリングと同等であることが示されている。

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

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

(型なしの)ラムダ計算はチューリング完全ですが、単純型付きラムダ計算はそうで​​はありません。

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