私はそれがあるかどうか、非常に興味がある - 私はそれが修飾されていない場合は、どの機能が修飾されませんか?私はバッチのまともな量を行い、能力の明らかなスリップアップが表示されません。バッチチューリングは完了しましたか?
17
A
答えて
12
私はそれが適格であると信じています。チューリングの完全性の基本的な要件は、状態(変数)を格納する機能、分岐する機能(条件付き)、反復する機能(ループ)など、いくつかの簡単な操作では簡単にできると考えられています。バッチにはこれらのすべてが含まれているため、Turingの完全性のための未だに未知の要件がない限り、バッチスクリプトは適格です。
15
(brainfuckがチューリング完全であることが証明されているので)私はちょうど「証明」バッチがバッチでbrainfuckインタプリタを作成することによって、チューリング完全できました:
https://github.com/YoYoYonnY/Brainfuck-In-Batch
ところで、完全なチューリングプログラミング言語は、そのいずれかを意味します
(同じ言語で)別のプログラムが最終的に停止しますか永遠に実行し続けるかどうかを判断することができますプログラムを作成することは不可能- (私はこの1つはどのように動作するかを知っている、と私はありません誰にも思わないverはこれをTuringの完全性を証明するために使用しました)。行動する
- 可能:言語(Brainfuck interpreter in Brainfuck(私は残念ながら見つけることができない、より良いバージョンは、あります。この1はひどく遅いです)。インタプリタ)に可能なすべてのプログラムを実行することができ、プログラムを作成することが可能
- ;のみ
false
にtrue
を変更することができることと、他の方法は、周りで- すなわち、他の値に変数の値を変更する(メモリへの書き込み:ようやチューリング機械をシミュレートし、したがっては少なくとも次の側面が含まれています依然として有効です。バッチの場合:
SET A=5
) - 「無限」メモリ(すなわち、 1ビット/バイト以上の書き込みが可能でなければなりません。オブジェクト全体に書き込むことができる限り、文字列、配列、テーブル、ビットフィールド、または整数だけが有効です。整数を有効にするにはbitshiftsが必要であり、配列にインデックスを付ける必要があります(
array[index];
など)。 - 条件付きジャンプ文(すなわち
IF %A%==0 GOTO LABEL
(Aがゼロであれば標識するジャンプ)、while (var) {/*code*/}
(varがゼロではないながら、コードの先頭に戻るジャンプ)またはjmp0 exit;
スタック上の現在の値がゼロである場合()出口へジャンプ)
- すなわち、他の値に変数の値を変更する(メモリへの書き込み:ようやチューリング機械をシミュレートし、したがっては少なくとも次の側面が含まれています依然として有効です。バッチの場合:
従来のチューリングマシンでは、両側に無限大のテープが必要ですが、単純な配列、文字列、テーブル(オブジェクト)またはバイナリ番号(ビットフィールド)は仕事も。私の "Brainfuck in Batch"では、メモリを格納するために配列/テーブルのようなオブジェクトを使いました(バッチは値のキーを変更することができます:SET ARRAY[%KEY%]=%VALUE%
)
私も指摘します純粋なバッチスクリプトだけで何かをしている人はまったくばかげていることをしています。 :S – Wug
これよりも若干それがあるように感じます。チューリングマシンは単に「状態を格納」するだけではなく、基本的に両端スタックを備えています。 FSMは状態、分岐、反復の弱いバージョンを持ち、TCではありません。 PDAにもスタックがあり、まだTCではありません。 TCとなるには2つのスタックを持つPDAが必要です。 –