チューリング完全版とは何ですか?

https://stackoverflow.com/questions/7284

08-06-2019
|

質問

「チューリング完了」という表現は何を意味しますか?

あまり理論的な詳細には触れずに、簡単に説明していただけますか?

解決

最も簡単な説明は次のとおりです。

Turing Complete システムとは、(実行時間やメモリに関する保証はありませんが) 答えを見つけるプログラムを作成できるシステムを意味します。

したがって、誰かが「私の新しいものはチューリング完全です」と言った場合、それは原理的には（実際にはそうではないことも多いですが）あらゆる計算問題の解決に使用できることを意味します。

たまには冗談でも…ある人が vi でチューリングマシンシミュレータを書いたので、vi は世界で必要とされた唯一の計算エンジンであると言えます。

他のヒント

最も簡単な説明は次のとおりです

アラン・チューリングは、プログラムを受け取り、そのプログラムを実行して何らかの結果を表示できるマシンを作成しました。しかしその後、プログラムごとに異なるマシンを作成する必要がありました。そこで彼は、あらゆるプログラムを受け取って実行できる「ユニバーサルチューリングマシン」を作成しました。

プログラミング言語は、(仮想ではありますが) それらのマシンに似ています。彼らはプログラムを取得して実行します。さて、十分な時間とメモリがあれば、チューリングマシンが実行できる任意のプログラム（言語に関係なく）を実行できるプログラミング言語を「チューリング完全」と呼びます。

例えば：10 個の数値を取得して加算するプログラムがあるとします。チューリングマシンはこのプログラムを簡単に実行できます。しかし、何らかの理由であなたのプログラミング言語が同じ加算を実行できない場合、それはチューリングマシンが不完全であると想像してください。一方、万能チューリングマシンが実行できるように、任意のプログラムを実行できる場合、それはチューリングが完了したことになります。

Java、JavaScript、Perl などの最新のプログラミング言語のほとんどは、加算、乗算、if-else 条件、return ステートメント、データの保存/取得/消去方法など、プログラムの実行に必要なすべての機能を実装しているため、完全なチューリングを実現しています。。

アップデート：詳細については、私のブログ投稿をご覧ください。「JavaScript のチューリングが完了しました」 — 説明

からウィキペディア:

アランチューリングにちなんで名付けられたチューリングの完全性は、これまでのところ進んだコンピューティングデバイスのすべてのもっともらしい設計が、教会の教会の論文として知られるようになった普遍的なチューリングマシンによってエミュレートできるという点で重要です。したがって、ユニバーサルチューリングマシンとして機能できるマシンは、原則として、他のプログラム可能なコンピューターができる計算を実行できます。ただし、これは、マシンのプログラムを作成するために必要な努力、マシンが計算を実行するのにかかる時間、またはマシンが計算とは無関係の能力を持つ能力とは何の関係もありません。

無制限のストレージが必要なため、真にチューリングコンプリートマシンは物理的に不可能である可能性が非常に高いですが、チューリングの完全性は、無制限のストレージがあれば普遍的な物理マシンまたはプログラミング言語に大まかに起因することが多いことが多いです。この意味では、最新のコンピューターはすべてチューリングが完全になっています。

「チューリングの完全とは、『十分な時間と空間が与えられた計算可能な問題に答えることができる』ということを意味する」と言う以外に、どうすればこれ以上非技術的なことができるのかわかりません。

非公式の定義

チューリング完全言語とは、あらゆる計算を実行できる言語です。の教会とチューリングの論文実行可能な計算はすべてチューリングマシンで実行できると述べています。あチューリングマシンは、無限のランダムアクセスメモリと、いつそのメモリを読み取り、書き込み、移動するか、いつ特定の結果で終了するか、そして次に何をするかを指示する有限の「プログラム」を備えたマシンです。チューリングマシンへの入力は、開始前にメモリに保存されます。

言語をチューリングとして完成させないもの

チューリングマシンはメモリ内にあるものに基づいて決定を下すことができます - のみをサポートする「言語」 +, -, *, 、そして / 整数では、入力に基づいて選択を行うことができないため、チューリングは完全ではありませんが、チューリングマシンは選択できます。

チューリングマシンは永遠に稼働できる - Java、Javascript、または Python を使用して、あらゆる種類のループ、GOTO、または関数呼び出しを実行する機能を削除した場合、終了しない任意の計算を実行できないため、チューリングは完全ではなくなります。コックは終了しないプログラムを表現できない定理証明器であるため、チューリング完全ではありません。

チューリングマシンは無限のメモリを使用できる - Java とまったく同じ言語ですが、4 ギガバイトを超えるメモリを使用すると終了する言語は、チューリングマシンが無限にメモリを使用できるため、完全なチューリングとは言えません。これが、実際にはできない理由です 建てる チューリングマシンですが、Java は依然としてチューリング完全言語です。言語無限のメモリの使用を妨げる制限はありません。これが、正規表現がチューリングとして完成していない理由の 1 つです。

チューリングマシンにはランダムアクセスメモリがある - メモリを使用してのみ作業できる言語 push そして pop スタックに対する操作はチューリング完了ではありません。文字列を読み取る「言語」がある場合一度スタックからプッシュおよびポップすることによってのみメモリを使用できます。 ( 文字列には独自のものがあります ) 後で見つけたら押すことで ( 見ると飛び出す ). 。ただし、すべてかどうかはわかりません ( 独自のを持っています ) 後で そして 毎 [ 独自のを持っています ] 後ほど（注意） ([)] この基準は満たしていますが、 ([]] ではない）。チューリングマシンはランダムアクセスメモリを使用して追跡できます。 ()'砂 []は個別に作成できますが、スタックのみのこの言語ではそれができません。

チューリングマシンは他のチューリングマシンをシミュレートできます - チューリングマシンは、適切な「プログラム」が与えられると、別のチューリングマシンの「プログラム」を取得し、任意の入力でシミュレートできます。Python インタプリタの実装が禁止されている言語がある場合、その言語はチューリングとしては完成していません。

チューリング完全言語の例

あなたの言語に無限のランダムアクセスメモリ、条件付き実行、および何らかの形式の繰り返し実行がある場合、それはおそらくチューリング完全です。チューリングマシンができるすべてのことを依然として達成できる、さらに珍しいシステムがあり、それらもチューリングマシンを完成させます。

型なしラムダ計算
コンウェイの人生ゲーム
C++ テンプレート
プロローグ

基本的に、チューリング完全性は 1 つの簡潔な要件、つまり無制限の再帰です。

記憶にさえ制限されません。

独自に考えたのですが、ここに議論がありますという主張の。私のLSPの定義より多くのコンテキストを提供します。

ここでの他の回答は、チューリング完全性の基本的な本質を直接定義するものではありません。

Turing Complete とは、少なくとも同等の強力さを意味します。チューリングマシン. 。これは、チューリングマシンで計算できるものはすべて、チューリング完全システムでも計算できることを意味します。

チューリングマシンより強力なシステムをまだ発見した人はいません。したがって、当分の間、システムがチューリング完全であると言うのは、そのシステムが既知のコンピューティングシステムと同じくらい強力であると言うのと同じです (「教会とチューリングの論文).

最も単純に言えば、チューリング完全システムは考えられるあらゆる計算問題を解決できます。

重要な要件の 1 つは、スクラッチパッドのサイズに制限がなく、巻き戻してスクラッチパッドへの以前の書き込みにアクセスできることです。

したがって、実際には、チューリング完全なシステムは存在しません。

むしろ、一部のシステムは、無制限のメモリをモデル化し、システムのメモリ内に収まる可能なあらゆる計算を実行することによってチューリング完全性を近似します。

「チューリング完全」という概念の重要性は、プロセスをより単純な命令で構成される「単純な」命令に分解できるコンピューティングマシン (必ずしも機械的/電気的な「コンピュータ」である必要はない) を識別できることにあると思います。ユニバーサルマシンが解釈して実行できる命令。

注釈付きチューリングを強くお勧めします

@Markあなたが説明していることは、ユニバーサルチューリングマシンの説明とチューリングコンプリートの説明が混ざったものだと思います。

実際的な意味でのチューリング完全なものとは、プログラムとして記述および表現でき、ユニバーサルマシン (デスクトップコンピューター) によって実行できるマシン/プロセス/計算です。他の人が述べたように、時間や保管場所は考慮されていませんが。

簡単な言葉で私が理解していること：

チューリングの完了: 計算を行うことができるプログラミング言語/プログラム、それがチューリング完全です。

例えば：

Just を使用して 2 つの数値を加算できますか? HTML. 。(答えは 'いいえ'、加算を実行するには JavaScript を使用する必要があります。)、したがって HTML はチューリング完全ではありません。
Java、C++、Python、JavaScript、Solidity for Ethereum などの言語は、この言語を使用して 2 つの数値を加算するような計算を実行できるため、チューリング完全です。

お役に立てれば。

としてウェイロン・フリンは言った:

チューリングコンプリートとは、少なくともチューリングマシンと同じくらい強力であることを意味します。

これは間違いだと思います。システムがチューリングマシンとまったく同じくらい強力であれば、システムはチューリングとして完全です。マシンによって実行されるすべての計算はシステムによって実行できますが、システムによって実行されるすべての計算はチューリングマシンによって実行することもできます。

ほとんどのプログラマに馴染みのある実用的な言語用語では、チューリングの完全性を検出する通常の方法は、言語が入れ子になった無制限の while ステートメントのシミュレーションを許可するかどうかです (上限が固定されたパスカルスタイルの for ステートメントとは対照的です)。

リレーショナルデータベースは、場所や道路の緯度と経度を入力し、それらの間の最短経路を計算できるでしょうか。これは、SQL がチューリングが完全ではないことを示す 1 つの問題です。

しかし、C++ ならそれができ、どんな問題でも解決できます。そのとおりです。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow