windows - バッチチューリングは完了していますか？

Question

該当するかどうかはわかりませんが、非常に興味があります。資格がない場合、資格を得るにはどのような機能が欠けているのでしょうか? 私はかなりの量のバッチを実行しましたが、能力に明らかな誤りは見られません。

Answer 1

バッチでbrainfuckインタープリターを作成することにより、バッチがチューリング完全であることを「証明」しました（brainfuckはチューリング完全であることが証明されているため）：

https://github.com/yyny/Brainfuck-In-Batch

ちなみに、チューリング完全なプログラミング言語とは、次のいずれかを意味します。

• （同じ言語の）別のプログラムが最終的に停止するか、永久に実行し続けるかを判断できるプログラムを作成することは不可能です（これがどのように機能するかはわかりません。チューリングを証明するためにこれを使用した人は誰もいないと思います完全）。
• その言語で可能なすべてのプログラムを実行できるプログラムを作成することが可能です (インタープリター: Brainfuckの Brainfuck インタープリター(より良いバージョンがありますが、残念ながら見つけることができません。これは非常に遅いです))
• チューリング マシンのように動作またはシミュレートできるため、少なくとも次の側面 が含まれます。
  • メモリへの書き込み (つまり、変数値を他の値に変更trueします。変更できるのは、その逆のみfalseです。バッチの場合: SET A=5)
  • 「無限」のメモリ (つまり、書き込むことができるビット/バイトが 1 つ以上、できれば無限にある必要があります。オブジェクト全体に書き込むことができる限り、文字列、配列、テーブル、ビットフィールド、さらには整数だけでもすべて有効です。アドレスによって変数の読み書きが可能でなければならないことに注意してください: 整数を有効にしたい場合はビットシフトが必要であり、配列にインデックスを付けることができる必要があるため、array[index];.)
  • 条件付きジャンプ ステートメント (つまりIF %A%==0 GOTO LABEL、(A がゼロの場合はラベルにwhile (var) {/*code*/}ジャンプ)、(var がゼロでない場合はコードの先頭に戻る)、またはjmp0 exit;(スタック上の現在の値がゼロの場合は終了するためにジャンプ))

従来のチューリング マシンでは、両側が無限であるテープが必要ですが、単純な配列、文字列、テーブル (オブジェクト)、または 2 進数 (ビットフィールド) も機能します。たとえば、私の「Brainfuck in Batch」では、メモリを格納するために配列/テーブルのようなオブジェクトを使用しました (バッチを使用すると、値のキーを次のように変更できるため: SET ARRAY[%KEY%]=%VALUE%)

Answer 2

合格だと思います。チューリングの完全性の基本的な要件は、状態を格納する機能 (変数)、分岐する機能 (条件)、反復する機能 (ループ) など、いくつかの単純な操作に還元できると考えられています。バッチにはこれらすべてが含まれているため、チューリングの完全性に関してまだ発見されていない要件がない限り、バッチ スクリプトが適しています。