問題タブ [turing-complete]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
computer-science - 機能的完全とはチューリング完全を意味しますか?
AND、OR、NOT の 3 つの論理ゲートが機能的に完全であることに気付きました。これは、これら 3 つのゲートだけで真のテーブルを表すことができることを意味します。
では、これらの 3 つのゲートだけで計算可能な関数を表現できるかどうかを知りたいですか?
compiler-construction - Brainfuck プログラムでメモリ配列が範囲外にアクセスされているかどうかを判断することは可能ですか?
私はアセンブリで独自の BF インタープリターを作成しましたが、現在はアセンブリ コードにコンパイルする BF コンパイラを Java で作成しています。
メモリ セルの配列が範囲外かどうかを検出するちょっとした便利な機能を実装したかったのです。配列の従来の制限は、インデックスを in[0, 30000)にすることでした。それ以外の場合[0, inf)も一般的に使用されます。もう 1 つのオプションは、メモリをラップアラウンドすることです。したがって、最初のケースでは、インデックス 30000 へのアクセスはインデックス 0 へのアクセスを意味する可能性があります。
私のコンパイラでは、この検出は従来のコンパイラのセマンティック分析フェーズで行われるため、構文分析フェーズから AST (抽象構文ツリー) を既に取得しています。
しばらくの間、このための構造を考え出そうとした後、私はDetecting infinite loop inbrainfuck programを見つけました.BFのウィキペディアページと一緒に、メモリ配列としてのBFプログラムが[0, inf)チューリングマシンに似ていることがわかりました.
だから私の質問は、[0, max)と[0, inf)ケースの両方で、メモリポインターがゼロを下回ったかどうか、前者の場合は最大を下回ったかどうかを検出することは可能ですか? 明らかに、チェック中に無限ループに陥ることはありません。また、最大実行時間の設定も避けたいと思います。
おまけの質問: ループ構造[...]がループする回数を検出することは可能ですか?
math - チューリング完全なプログラミング言語を構成する必要がある要素は何ですか?
私はこれを探していましたが、何もありませんでした。
この説明は、python の本で一度見たことがありますが、どの本かは覚えていません。では、プログラミング言語が完全なチューリングで構成されるべき要素 (変数、ループ、分岐など) は何ですか?