問題タブ [turing-complete]

C++ が決定可能でないことはわかっています。しかし、それは再帰的に列挙可能ですか?

有効な C++ プログラムのセットを、現在の C++ 標準の下で適切に定義されたプログラムと定義しましょう。

有効な C++ プログラムを常に有限時間で識別できるコンパイラを構築することは可能ですか?

それとも再帰的に列挙可能ですか？

有限時間内に無効なC++ プログラムを常に識別できるコンパイラを構築することは可能ですか?

それともどちらでもない？

関数シンボルを 1 つだけ含む論理プログラミングのサブセットがある場合、すべてを実行できますか?

できないとは思いますが、まったく自信がありません。プログラミング言語は、チューリング完全言語であれば、ユーザーが望むことは何でもできます。これは、if..then..elseコマンド、再帰を実行できなければならないことを意味し、自然数を定義する必要があることを教えられました。

ヘルプや意見をいただければ幸いです。

私はさまざまな型システムとラムダ計算について調べてきましたが、ラムダ キューブ内の型指定されたラムダ計算はすべて、同等のチューリングではなく、強く正規化されていることがわかりました。これには、単純に型付けされたラムダ計算とポリモーフィズムである System F が含まれます。

これにより、次の質問に至りましたが、これに対する包括的な答えを見つけることができませんでした。

• (例えば) Haskell の形式主義は、それが表向きに基づいている微積分とどのように違うのですか?
• Haskell のどの言語機能が System F 形式に当てはまらない?
• チューリングの完全な計算を可能にするために必要な最小限の変更は何ですか?

これを理解するのを手伝ってくれた人に感謝します。

この答えは言う

1. 以下は、ラムダ計算における基本的な y コンビネータです。

   Y f = (\x -> f (x x)) (\x -> f (x x))

つまり、Clojure では次のようなものです。

2. y-Combinator の別の式を次に示します (引数のステップ 2)。

3. チューリング完全言語をエンコードしました (y-Combinator を使用したため) (引数のステップ 3)

私の質問は、y-combinator がチューリング等価性を提供するのはなぜですか? それは議論の単なる仮定だったようです。

VHDLチューリングは完全ですか？私の理解では、VHDL はレジスタ マシンを作成し、任意の RAM を使用しないレジスタ マシンは完全なチューリングではありません。

これは正確ですか？レジスタ マシンでは解決できない問題について、標準的なアプローチはありますか? たとえば、VHDL の外部で RAM を使用し、VHDL を介してそれを管理しますか?

私は edX のレッスンを聞いています。教授は、これら 6 つの基本的なプリミティブを実行できるすべてのマシンをチューリング完全と呼ぶことができると強調しています。では、6 つの基本プリミティブとは何でしょうか?

そのため、公式ドキュメントでBitcoin Script について読んでいて、次の行を見つけました。難しいですが、なぜ誰かが「意図的に非チューリング完全」な言語を作るのか理解できませんでした。これの理由は何ですか？言語がチューリング完全になるとどうなりますか? さらに拡張すると、「ループなし」は、スクリプトが非チューリング完全であることと関係があるのでしょうか?

これは、このサイトでの最初の質問です。

最近、NPについて勉強しています。私はこのトピックについていくつかの混乱を抱えており、私の推論を提案し、誰かが私を検証したいと考えています.

I) 各 NP 問題は Exponential Time で解くことができます。

II) P=NP の場合、NP=NP-完全。

III) 2素因数分解の問題、NPです。

IV) 問題 X が既知の NP 困難な問題に還元できる場合、X は NP 困難である必要があります。

誰かが私の推論を検証し、私を学ぶことができますか?‌

チューリング マシンの命令にコンパイルする独自のプログラミング言語を作成しましたが、実装方法を知りたいと思っていましたif(a>b) do _ end。言語の定義は次のとおりです（ここでも入手できます）

変数は任意の幅で動的に割り当てられるため、任意の大きな整数を持つことができます

各行は、関数の呼び出し (引数の変更)、while ループの開始 (実際には for ループに近い)、変数の割り当ての 3 つのうちのいずれかを実行できます。

使用可能な関数はincr、(1 ずつ増加、オーバーフロー可能)、decr(1 ずつ減少、オーバーフロー可能)、pop(変数から最後の桁を削除)、first(変数の最上位の 0 を 1 にfrost変更)、および (最も重要な桁を変更) です。有意な 1 からゼロ)。

while ループの構文は次のとおりです。

基本的にループするたびにエラー状態になるまで<func>行います。aエラー条件は次のとおりで、incrすべてfirst1 で、decrすべてfrost0 でpop、最後の桁を削除します。incrまたはを使用した while ループの後、frostループ変数のすべてのビットが 0 になり、 と が逆にfirstなりdecrます。while ループは関数呼び出しで終了する必要があり、各実行後に含まれるすべての変数を削除します。

割り当ては、構文に基づいていくつかの異なることを行うことができます。これよりも長い場合、変数が所有するスペースにa=b変数をコピーすることを意味し、作成された最新の変数でない限り、未定義の動作を引き起こします。左に 5 つのパディング ビット (ゼロに設定) を割り当てると、最後に変数が作成されない限り、オーバーフローによって未定義の動作が発生します。をゼロにします。最後に 3 ビットで代入します。babaaa=b,5baaa=a,0aa=5,35 % 2**3a

今私はで実装if(a != 0) do _ endすることができます

if(a==b)私の質問は、if(a!=b)、 、などの他の if ステートメントをどのように実装できるかです。if(a>b)

そして、二次的な質問として、この言語はチューリング完全です.この回答に基づいてそう信じていますプログラミング言語がチューリング完全であるための最小基準はありますか? . 言語が 1 ～ 5 を満たすことはわかっていますが、6 についてはわかりません。