批次图灵完成吗？

我找不到它，是否非常好奇 - 如果它没有资格，它缺少什么功能来限定？我已经完成了相当数量的批量工作，并没有发现任何明显的能力偏差。批次图灵完成吗？

来源

2012-06-20 PinkElephantsOnParade

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

来源

2012-06-20 19:20:59 Wug

我还会指出人们设法做一些完全荒谬的事情，只使用纯批量脚本。：S – Wug

我觉得这比它略微多一些。图灵机不仅仅是“存储状态”，它基本上是一个双端堆栈。 FSM具有弱状态，分支和迭代版本，不是TC。 PDA甚至有一个堆栈，但仍然不是TC;它需要一个有两个堆栈的PDA作为TC。 –

我只是（因为brainfuck被证明是图灵完整的）“证明”批是图灵完备，通过创建一个批处理解释brainfuck：

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

顺便说一句，一个图灵完备编程语言意味着其可以：

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

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

来源

2015-05-10 12:58:04 YoYoYonnY

批次图灵完成吗？

回答

相关问题