computer-science - 言語の「チューリング完全性」を評価するための実用的なガイドラインは何ですか?

Question

「チューリング完全とは」とウィキペディアのページを読みましたが、チューリング完全であることの実際的な意味よりも、正式な証明には興味がありません。

私が実際に決めようとしているのは、私が設計したおもちゃの言語が汎用言語として使用できるかどうかです。それを使ってチューリングマシンを書くことができれば、それを証明できることはわかっています。しかし、成功することがかなり確実になるまで、その演習を実行したくありません.

チューリングの完全性が不可能な最小限の機能セットはありますか? 完全性を事実上保証する一連の機能はありますか?

(私の推測では、条件付き分岐と読み取り/書き込み可能なメモリストアがあれば、ほとんどの場合そこにたどり着くことができます)

編集：

「チューリング完全」と言ったことで、ちょっと話が逸れてしまったように思います。私は、特定の機能セットを備えた新しく発明された言語 (または、特定の命令セットを備えた VM) が計算に値するものなら何でも計算できると、合理的な自信を持って推測しようとしています。それを使ってチューリングマシンを構築できることを証明することは 1 つの方法ですが、唯一の方法ではありません。

私が望んでいたのは、「X、Y、および Z を実行できる場合、おそらく何でも実行できる」という一連のガイドラインでした。

score 46 · Accepted Answer

なんらかの形式の動的割り当てコンストラクト ( mallocor newor conswill do) と、再帰関数または無限ループを記述するその他の方法が必要です。それらを持っていて、面白いことが何でもできるなら、ほぼ確実にチューリング完全です。

ラムダ計算は、チューリングマシンと同等の能力を備えています。ラムダ計算を実装すると、実際にラムダ計算プログラムを書くのはかなり楽しいものになります。 チューリングマシンのプログラムを書くよりもはるかに楽しいです。

私が認識しているチューリング完全性の唯一の実用的な意味は、終了しないプログラムを作成できるということです。終了を保証する特殊な目的の言語をいくつか使用したため、チューリング完全ではありません。保証された終了と引き換えに、余分な表現力を放棄することが役立つ場合があります。

score 31 · Accepted Answer

「チューリング完全性」とは、そもそもチューリングマシンのポイントであった、任意のアルゴリズム計算を表現できるという性質を表しています。言語または論理システムは、この性質を持っている場合、「チューリング完全」と記述できます。実用的な観点から、すべての汎用プログラミング言語 (および驚くほど多数の特殊目的プログラミング言語) は、適切に緩い定義でこれを行うことができます (以下を参照)。

ただし、チューリング完全性の厳密な定義は無限のストレージ容量を意味しますが、これはもちろん物理的に不可能です。これを考えると、物理マシンがチューリング完全である可能性はありませんが、チューリング完全性をプログラミング言語に帰する場合、この制約は通常 (少なくとも非公式に) 緩和されます。言語のチューリング完全性を測る簡単なテストの 1 つは、その言語を使用してチューリングマシンシミュレーターを実装できるかどうかです。

チューリング完全ではない広範なシステムの例はリレーショナル代数です。これは、Codd の論文「大規模な共有データバンクのリレーショナルモデル」で説明されている SQL の背後にある理論的基礎です。関係代数には、ゲーデル完全性という性質があります。これは、 1 階述語計算(通常の論理式)で定義できるあらゆる計算を表現できることを意味します。ただし、任意のアルゴリズム計算を表現できないため、Turing-Complete ではありません。

すべてではないにしてもほとんどの実用的な SQL ダイアレクトは、通常プログラミング言語に適用される定義によってチューリング完全である範囲で、手続き型構造を使用して純粋なリレーショナルモデルを拡張することに注意してください。ただし、個々の SQL クエリは概してそうではありません。

チューリング完全ドメイン固有言語のさらに悪質な例としては、TeXとsendmail.cf があります。後者の場合、sendmail.cf を使用してユニバーサルチューリングマシンシミュレータを実装した有名な例が実際にあります。

score 11 · Accepted Answer

あなたの言語でBrainf$インタープリターを書けるなら、それはチューリング完全です。 LOLCODEはまさにこの方法でチューリング完全であることが証明されました。

score 9 · Accepted Answer

チューリング完全ではない言語の例には、次のような有界ループが頻繁にあります。

for i=1 to N {...}

ただし、次のような、より一般的な条件をチェックする無制限のループがありません。

while bool_expr {...}

考えられるすべてのループ構造が制限されている場合、プログラムは確実に終了します。また、無条件の終了保証は潜在的に有用ですが、言語がチューリング完全ではないことも示しています。

また、考えられるすべてのループ構造を特定するのは難しい場合があることにも注意してください。たとえば、C++テンプレートはチューリング完全であることを意図していないと確信しています...

score 7 · Accepted Answer

「最小限の機能セット」があるかどうかはわかりませんが、言語がチューリング完全であることを証明するには、別のチューリング完全システム (必ずしもチューリングマシンである必要はありません) をエミュレートできることを証明するだけで済みます。他のシステムはチューリング完全であることが知られています。http://en.wikipedia.org/wiki/Turing_complete#Examplesには、チューリング完全システムの完全なリストがあります。それらのいくつかは、チューリングマシンよりも単純です。

score 3 · Accepted Answer

Norman Ramsey が言ったことに 1 つの警告を追加したいと思います: チューリングマシンには無限のメモリがあるため、チューリングが完全であると見なされるプログラミング言語は、メモリも無限であるという仮定の下でのみそうなります。

score 3 · Accepted Answer

Brainfuck はチューリング完全で、ループ構造とメモリの増減しかないので、これで十分です。

一方、ラムダ計算では値を変更する方法はありませんが、チューリング完全であるため、ミュータブルメモリなしで変更できることは明らかです。

ただし、プログラムはラムダ計算とは何の関係もない可能性が最も高いため、実用的な答えを得るには、最小値は

変数への書き込み方法
変数を読み取る方法
条件付き goto の形式 (if ステートメント、while ループなど)

score 2 · Accepted Answer

チューリング完全性の最小機能のようなものを見た覚えがありません。ただし、言語がループと条件分岐をサポートしている場合は、チューリング完全である可能性が高くなります。ただし、それを証明する唯一の方法は、チューリングマシンまたは別のチューリング完全言語をシミュレートすることです。

score 1 · Accepted Answer

OISC（One Instruction-Set Computer）のエミュレートを試すことができます。そこで命令の1つをエミュレートできれば、それらの単一の命令を使用してチューリング完全マシンを構成できるため、言語もチューリング完全でなければならないことが証明されます。

score 1 · Accepted Answer

チューリングマシンを実装できる場合 (それらが実装できる限り、それらは無制限のメモリを備えた数学的構造であるため [テープサイズは無限です])、チューリングが完全であることを確認できます。

いくつかの兆候:

メモリをチェックして、現在の値に基づいて操作したり、それを使用してプログラムフローを制御したりできます。
そのメモリは、メモリ、追加できる文字列、再帰によってメモリを割り当てることができるスタックなどに割り当てることができます。
プログラムフローは、反復または選択ベースの再帰を通じて行うことができます。

score 1 · Accepted Answer

非終了が可能な言語は、ほぼチューリング完全です。制限のないループ構造 (While ループや自分自身に再び到達できる Goto など) を与えるか、一般的な再帰を与える (関数に制限なしで自分自身を呼び出させる) ことによって、言語を非終了可能にすることができます。

チューリング完全になると、他のチューリング完全言語 (自分自身のものを含む) の解釈などを行うことができます。

本当の質問は、「それは何が良いのか」です。あなたの言語が特定の問題を解決するために特定のドメインで使用される場合は、チューリング完全ではない言語で解決策を表現する方法を見つけたほうがよい場合があります。したがって、答えが保証されます。

X が非チューリング完全言語によって提供されている場合、他のチューリング完全言語で「これ、あれ、または何でも; ただし、X によって提供される結果でそれを行う」と記述することで、いつでもチューリング完全性を追加できます。

もちろん、1つの言語だけを使用したい場合は、おそらくチューリング完全の方がよいでしょう...

score 1 · Accepted Answer

チューリングの完全性が不可能な最小限の機能セットはありますか? 完全性を事実上保証する一連の機能はありますか?

はい、データを条件とした制御の流れを持たせる必要がありますif。たとえば、+-*/ポケット電卓は、条件を表現する方法がないため、チューリング完全ではありません。

また、ループを実装できる上に、プログラムの前のポイントに戻るジャンプを表現できる必要があります。たとえば、プログラムが終了することを保証するために逆方向へのジャンプを禁止する BPF もチューリング完全ではありません。

読み取りと書き込みの両方が可能で、任意の大きさのストレージが必要です。たとえば、32 ビット変数が 2 つしかない言語では、計算できる内容が制限されます。ストレージの構造には多くのオプションがあります: ポインタ、配列、スタック、コンスセル、純粋なデータ構造などによってアドレス指定されるメモリ。

これらに加えて、他のすべてのプログラミング言語を構築できます。簡単でも高速でもないかもしれませんが、十分です。

score -5 · Accepted Answer

...チューリング完全であることの実際的な意味よりも。

チューリングが完全であることの実用的な意味があるとは思えません。

元のチューリングマシンなど、チューリング完全マシンの例をいくつか見ると、実際の計算にはあまり役に立たないため、その概念は理論上の関心のみにとどめる必要があることがわかります。

computer-science - 言語の「チューリング完全性」を評価するための実用的なガイドラインは何ですか?

13 に答える 13

Related

Reference