windows - 批处理图灵完成了吗？

Question

我找不到它是否是，我很好奇 - 如果它不符合条件，它缺乏什么功能来符合条件？我已经完成了相当多的批次，并且没有看到任何明显的能力失误。

score 26 · Accepted Answer

我刚刚通过批量创建brainfuck解释器“证明”批处理是图灵完整的（因为brainfuck被证明是图灵完整的）：

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

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

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

score 15 · Accepted Answer

我相信它是合格的。图灵完备性的基本要求被认为可以简化为一些简单的操作，包括：存储状态的能力（变量）、分支的能力（条件）和迭代的能力（循环）。批处理具有所有这些，因此除非对图灵完整性有一些尚未发现的要求，否则批处理脚本是合格的。

2 回答 2