windows - Batch 图灵完成了吗？

Question

我找不到它是否符合条件并且很好奇 - 如果它不符合条件，它缺少什么功能来符合条件？我已经完成了大量的批处理，没有发现任何明显的能力失误。

Answer 1

我刚刚通过批量创建一个 brainfuck 解释器来“证明”批处理是图灵完备的(因为 brainfuck 被证明是图灵完备的):

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

顺便说一句，图灵完备的编程语言意味着:

• 不可能创建一个程序来确定另一个程序(使用相同语言)最终会停止还是会永远运行(我不知道这个程序是如何工作的，而且我认为没有人用过这个程序来证明图灵完备性)。
• 有可能创建一个可以运行该语言所有可能程序的程序(解释器:Brainfuck interpreter in Brainfuck(有一个更好的版本，不幸的是我找不到。这个非常慢))
• 可能表现得像或模拟图灵机，因此包含至少以下方面:
  • 写入内存(即，将变量值更改为任何其他值；只能将 true 更改为 false，反之亦然。在批量大小写:SET A=5)
  • “无限”内存(即必须有不止一位/字节你也可以写，最好是无限多。字符串，数组，表，位域甚至整数都是有效的，只要我们可以写入整个对象。请注意，必须可以通过地址读取和写入变量:如果您希望整数有效，则必须有移位，并且您必须能够索引您的数组，所以像 array[索引];.)
  • 条件跳转语句(即 IF %A%==0 GOTO LABEL(如果 A 为零则跳转到标签)，while (var) {/*code*/} code>(当 var 不为零时跳回到代码的开头)或 jmp0 exit;(如果堆栈中的当前值为零则跳转到退出)

传统的图灵机需要你有一个两边都是无限的磁带，但是一个简单的数组、字符串、表(对象)或二进制数(位域)也可以。例如，在我的“Brainfuck in Batch”中，我使用了一个类似数组/表格的对象来存储内存(因为批处理允许您更改值的键，如下所示:SET ARRAY[%KEY%]=% VALUE%)