問題タブ [turing-complete]

「チューリング完全」という表現はどういう意味ですか?

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

C++のテンプレートシステムはコンパイル時にチューリング完全であると言われています。これは、この投稿とウィキペディアでも言及されています。

このプロパティを利用する計算の重要な例を提供できますか？

この事実は実際に役立ちますか？

.Net3.5にあるように。DLRが動作する4.0であることがわかっていますが、現在のバージョンに興味があります。

使用されるほぼすべてのプログラミング言語はチューリング完全であり、これにより言語は計算可能なアルゴリズムを表すことができますが、独自の問題も伴います。私が書いているアルゴリズムはすべて停止することを意図しているため、停止することを保証する言語でそれらを表現できるようにしたいと考えています。

文字列と有限状態マシンの照合に使用される正規表現は、 lexingのときに使用されますが、チューリングが完全ではない、より一般的で幅広い言語があるかどうか疑問に思っています。

編集：明確にする必要があります。「汎用」により、必ずしもすべての停止アルゴリズムをその言語で記述できるようにしたいわけではありません（そのような言語が存在するとは思いません）が、共通のスレッドがあると思われますすべてのアルゴリズムが停止することが保証されている言語を生成するために一般化できる停止証明。

この問題に取り組む別の方法もあります - 理論的に無限のメモリの必要性を排除します。マシンが許可されるメモリの量を制限すると、マシンが存在する状態の数は有限であり、数えることができるため、アルゴリズムが停止するかどうかを判断できます (マシンが以前の状態に移行することを許可しないことによって)。 ）。

私は最近、人工生命について読んでいて、 「コンウェイのライフ ゲームは、普遍的な機械として分類されるのに十分な複雑さを示している」という記述に出くわしました。私はユニバーサル マシンとは何かについて大まかにしか理解していませんでした。ウィキペディアは、ウィキペディアがかつてないほど理解に近づいただけでした。誰かがこの非常にセクシーな声明に光を当てることができるのだろうか?

コンウェイのライフ ゲームは、私には、いくつかの途方もない含意を伴う素敵な気晴らしのように思えます。それは私がすべき飛躍ですか？

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

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

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

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

編集：

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

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

停止問題はチューリング完全言語では解決できず、正規表現のように常に停止する一部の非TC言語では簡単に解決できます。

停止する機能と停止しない機能の両方を備えているが、停止するかどうかを判断できるアルゴリズムを認めている言語があるかどうか疑問に思いました。

もちろん、ラムダ計算は非常に洗練されていますが、関数の入力と出力の間にこのような非対称性があることに気付きませんか? つまり、(関数を返すことによって) 関数が 2 つのパラメーターを取るようにすることはできますが、2 つの値を返すようにすることはできません。The Bookでは見つけられなかったと思います。

たとえば、オペレーティング システムを作成するときに、チューリング完全な言語では実現できない特定のことがありますか?

可能な限り最小の言語インタープリターを作成しようとしました。参加して試してみませんか？

ゲームのルール：

• 解釈しているプログラミング言語を指定する必要があります。あなたが発明した言語の場合は、コメントにコマンドのリストが含まれているはずです。
• コードは、コードとデータ変数に割り当てられたサンプル プログラムとデータで開始する必要があります。
• コードは、結果の出力で終了する必要があります。中間ステップごとに debug ステートメントがあることが望ましいです。
• コードは記述どおりに実行できるはずです。
• データは 0 と 1 (int、string、または boolean から選択) であり、出力は 1 ビットであると想定できます。
• 言語は、チューリング マシン、マルコフ連鎖などの標準モデルで記述された任意のアルゴリズムについて、実行後にプログラムを作成する方法が合理的に明白 (または説明) であるという意味で、チューリング完全である必要があります。インタプリタによってアルゴリズムが実行されます。
• コードの長さは、入力部分、出力部分、デバッグ ステートメント、および不要な空白を取り除いた後のコードの長さと定義されます。結果のコードとその長さを投稿に追加してください。
• eval()など、コンパイラにコードを実行させる関数は使用できませんexec()。

これはコミュニティ Wiki です。つまり、質問も回答も投票から評判ポイントを得ることはありません。でもとにかく投票！