「チューリング完全」という表現はどういう意味ですか?
あまり理論的な詳細には立ち入らずに、簡単に説明していただけますか?
質問する
243923 次
14 に答える
454
最も簡単な説明は次のとおりです。
チューリング完全システムとは、答えを見つけるプログラムを記述できるシステムを意味します (ただし、実行時間やメモリに関する保証はありません)。
したがって、誰かが「私の新しいものはチューリング完全です」と言った場合、それは原理的には (実際にはそうではないことが多いですが)、あらゆる計算問題を解決するために使用できることを意味します。
冗談です...ある人がviでTuring Machineシミュレーターを書いたので、viは世界で唯一必要とされた計算エンジンであると言えます。
于 2008-08-10T20:10:48.687 に答える
123
非公式な定義
チューリング完全言語は、あらゆる計算を実行できる言語です。Church-Turing Thesisは、実行可能な計算はすべてチューリング マシンで実行できると述べています。チューリング マシンは、無限のランダム アクセス メモリと、そのメモリをいつ読み書きし、移動するか、いつ特定の結果で終了するか、次に何をすべきかを指示する有限の「プログラム」を備えたマシンです。チューリング マシンへの入力は、開始前にメモリに格納されます。
チューリング完全ではない言語を作ることができるもの
チューリング マシンは、メモリ内にあるものに基づいて決定を下すことができます+- 、-、*、および整数のみをサポートする「言語」は/、入力に基づいて選択を行うことができないため、チューリング完全ではありませんが、チューリング マシンは可能です。
チューリング マシンは永遠に実行できます - Java、Javascript、または Python を使用して、あらゆる種類のループ、GOTO、または関数呼び出しを実行する機能を削除した場合、それは任意の計算を実行できないため、完全なチューリングにはなりません。終わることはありません。Coqは、終了しないプログラムを表現できない定理証明器なので、チューリング完全ではありません。
チューリング マシンは無限のメモリを使用できます- Java とまったく同じですが、4 ギガバイトを超えるメモリを使用すると終了する言語は、チューリング完全ではありません。チューリング マシンは無限のメモリを使用できるためです。これが実際にチューリング マシンを構築できない理由ですが、Java言語には無限のメモリの使用を妨げる制限がないため、Java は依然としてチューリング完全言語です。これが、正規表現がチューリング完全でない理由の 1 つです。
チューリング マシンにはランダム アクセス メモリpushがあります。スタックに対するメモリ操作と操作のみを可能にする言語は、pop完全なチューリングではありません。文字列を 1 回読み取り、スタックからのプッシュとポップによってのみメモリを使用できる「言語」がある場合、文字列内のすべての文字列が後で独自のものを持っているかどうかを知ることができ(ます。ただし、すべてが後で独自のものを持ち、すべてが後で独自のものを持つかどうかはわかりません（この基準は満たしていますが、満たしていないことに注意してください）。チューリング マシンは、そのランダム アクセス メモリを使用して と を追跡できます。)()()[]([)]([]]()[]は別ですが、スタックだけのこの言語はできません。
チューリング マシンは他のチューリング マシンをシミュレートできます- チューリング マシンは、適切な「プログラム」が与えられると、別のチューリング マシンの「プログラム」を取り、任意の入力でシミュレートできます。Python インタープリターの実装が禁止されている言語がある場合、それは完全なチューリングではありません。
チューリング完全言語の例
言語に無限のランダム アクセス メモリ、条件付き実行、および何らかの形式の繰り返し実行がある場合、おそらくチューリング完全です。チューリングマシンができることすべてを達成できる、よりエキゾチックなシステムがあり、それらもチューリング完全になります。
- 型指定されていないラムダ計算
- コンウェイの人生ゲーム
- C++ テンプレート
- プロローグ
于 2009-10-22T23:45:42.453 に答える
86
ウィキペディアから：
アラン チューリングにちなんで名付けられたチューリングの完全性は、これまでに進歩したコンピューティング デバイスのすべての妥当な設計がユニバーサル チューリング マシンによってエミュレートできるという点で重要です。したがって、万能チューリングマシンとして機能できるマシンは、原則として、他のプログラム可能なコンピューターが実行できるあらゆる計算を実行できます。ただし、これは、マシンのプログラムを作成するために必要な労力、マシンが計算を実行するのにかかる時間、またはマシンが持つ計算とは関係のない能力とは何の関係もありません。
真にチューリング完全なマシンは、無制限のストレージを必要とするため、物理的に不可能である可能性が非常に高いですが、チューリングの完全性は、多くの場合、無制限のストレージがあれば普遍的な物理マシンまたはプログラミング言語に大まかに起因します。この意味で、現代のコンピュータはすべてチューリング完全です。
「十分な時間とスペースがあれば、計算可能な問題に答えることができる」ということを除いて、あなたがそれ以上に技術的ではない方法を知りません。
于 2008-08-10T18:59:06.460 に答える
18
基本的に、チューリング完全性は 1 つの簡潔な要件、無制限の再帰です。
記憶に縛られることさえありません。
私はこれを独自に考えましたが、ここで主張のいくつかの議論があります。LSP の私の定義は、より多くのコンテキストを提供します。
ここでの他の回答は、チューリング完全性の基本的な本質を直接定義していません。
于 2011-11-27T04:03:15.853 に答える
16
チューリング コンプリートとは、少なくともチューリング マシンと同じくらい強力であることを意味します。これは、チューリング マシンで計算できるものはすべて、チューリング完全システムで計算できることを意味します。
チューリング マシンよりも強力なシステムを見つけた人はまだいません。したがって、当分の間、システムがチューリング完全であると言うのは、そのシステムが既知のコンピューティング システムと同じくらい強力であると言うのと同じです ( Church-Turing Thesisを参照)。
于 2009-05-18T17:09:11.900 に答える
3
「チューリング完全」という概念の重要性は、プロセスをより単純でより単純な「単純な」命令に分解できる計算機（必ずしも機械的/電気的な「コンピューター」である必要はない）を識別する能力にあると思います。ユニバーサルマシンが解釈して実行できる命令。
注釈付きチューリングを強くお勧めします
@Markあなたが説明しているのは、万能チューリング機械の説明とチューリング完全の説明の組み合わせだと思います。
チューリング完全であるものは、実際的な意味では、ユニバーサルマシン（デスクトップコンピューター）によって実行されるプログラムとして記述および表現できるマシン/プロセス/計算です。他の人が言っているように、それは時間やストレージを考慮していませんが。
于 2008-08-20T07:23:29.867 に答える
2
Brasilford 教授がこのビデオで説明していることの超簡単な要約。
Turing Complete ≅ Turing Machine でできることはすべて実行します。
条件分岐があります(つまり、「if ステートメント」)。また、「go to」を意味するため、ループが許可されます。
プログラムが必要とする任意の量のメモリ(十分な長さのテープなど) を取得します。
于 2021-02-18T13:08:15.720 に答える
-1
ほとんどのプログラマーになじみのある実用的な言語用語で言えば、チューリングの完全性を検出する通常の方法は、言語がネストされた無制限の while ステートメントのシミュレーションを許可するか許可するかどうかです (上限が固定されたパスカル スタイルの for ステートメントとは対照的に)。
于 2016-10-26T20:12:17.857 に答える
-2
チューリング コンプリートとは、少なくともチューリング マシンと同じくらい強力であることを意味します。
私はこれは間違っていると思います。システムがチューリング マシンとまったく同じくらい強力であれば、そのシステムはチューリング完全であると言えます。つまり、マシンによって実行されるすべての計算はシステムによって実行できますが、システムによって実行されるすべての計算もチューリング マシンによって実行できます。 .
于 2009-10-05T23:18:19.903 に答える
-9
リレーショナルデータベースは、場所や道路の緯度と経度を入力し、それらの間の最短経路を計算できますか？いいえ。これは、SQLがチューリング完全ではないことを示す1つの問題です。
しかし、C ++はそれを行うことができ、あらゆる問題を行うことができます。したがって、そうです。
于 2012-12-15T18:33:53.127 に答える