CODEWITHSUNDEEP
windowsbatch-filedos
PinkElephantsOnParade
PinkElephantsOnParade

Reputation: 6592

Is Batch turing complete?

I can't find if it is or not and am very curious - if it doesn't qualify, what functionality does it lack to qualify? I have done a decent amount of batch and don't see any obvious slip-ups in ability.

Upvotes: 24

Views: 5856

Answers (2)

yyny
yyny

Reputation: 1726

I've just 'proven' batch is turing complete, by creating a brainfuck interpreter in batch (Because brainfuck is proven to be Turing complete):

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

By the way, a turing complete programming language means its either:

  • impossible to create a program which can determine if another program (in the same language) will eventually stop or will keep running forever (I don't know how this one works, and I don't think anyone ever used this one to prove Turing completeness).
  • possible to create a program which can run all possible programs in the language (A interpreter: Brainfuck interpreter in Brainfuck (There is a better version, which I unfortunately can't find. This one is terribly slow))
  • Possible to act like or simulate a Turing machine, and thus contains at least the following aspects:
    • Writing to memory (i.e. changing a variable value to any other value; Only being able to change true to false and the other way around is still valid. In the case of batch: SET A=5)
    • 'Infinite' memory (i.e. there must me more than one bit/byte you can write too, preferably infinitely many. Strings, arrays, tables, bitfields or even just integers are all valid, as long as we can write to the entire object. Note that it must be possible to read from and write to a variable by adress: There must be bitshifts if you want integers to be valid, and you must be able to index your array, so something like array[index];.)
    • Conditional jump statements (i.e. IF %A%==0 GOTO LABEL (Jump to label if A is zero), while (var) {/*code*/} (Jump back to start of code while var is not zero) or jmp0 exit; (Jump to exit if the current value on the stack is zero))

The traditional Turing machine requires you to have a tape which is infinite on both sides, but a simple array, string, table (object) or binary number (bitfield) will work too. In my "Brainfuck in Batch" for example I used a array/table-like object to store the memory (Since batch allows you to change the key of a value, like so: SET ARRAY[%KEY%]=%VALUE%)

Upvotes: 28

Wug
Wug

Reputation: 13196

I believe it qualifies. The basic requirements of Turing completeness are thought to be reducible to a few simple operations, including: the ability to store state (variables), the ability to branch (conditionals), and the ability to iterate (loops). Batch has all of these, so unless there is some as-yet-undiscovered requirement for Turing completeness, batch scripting qualifies.

Upvotes: 16

Related Questions