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.
2 Answers
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
tofalse
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) orjmp0 exit;
(Jump to exit if the current value on the stack is zero))
- Writing to memory (i.e. changing a variable value to any other value; Only being able to change
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%
)
-
3"possible to create a program which can run all possible programs in the language". I don't believe this is sufficient. Consider a language which has exactly one output, no matter the code. Now any program in the language is technically an interpreter for the language, since, for any given program you pass it, it will produce the correct output for that program. It is obviously not Turing complete though. Feb 28, 2019 at 17:09
-
@YairHalberstadt Good point, although in my opinion not a very meaningful one. As with the "infinite memory" case, no system is perfect, and there are limits to what we can achieve in the real world. However, "Turing completeness" is used to classify the complexity of a computational system, and when we can already determine the complexity beforehand ("only has one output") checking for completeness becomes pretty meaningless. You could even argue about when it's not a computational system/programming language anymore.– yynyFeb 28, 2019 at 17:52
-
1Whilst I admit my example is trivial, my point is this condition is insufficient. I believe that there may be other more subtle cases where a language can interpret any program in itself, but is not turing complete. I believe the true condition is that it can interpret a language known to be turing complete. Feb 28, 2019 at 17:56
-
Apparently a faster bf interpreter: hevanet.com/cristofd/brainfuck/dbfi.b found by @zvava– yynyApr 1, 2020 at 22:57
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.
-
9I'll also point out that people manage to do some utterly ridiculous things using nothing but pure batch scripting. :S– WugJun 20, 2012 at 19:27
-
1I feel like there is slightly more to it than this. A Turing Machine doesn't just "store state", it has basically a double-ended stack. FSMs have weak versions of state, branching, and iteration, and are not TC. PDAs even have a stack and are still not TC; it takes a PDA with two stacks to be TC. Mar 4, 2017 at 19:41