批量图灵完成了吗？

Question

我无法找到它是否是非常好奇 - 如果它没有资格,它缺乏什么功能才能获得资格？我做了相当数量的批次,并没有看到任何明显的能力下滑.

Answer 1

通过批量创建一个brainfuck解释器,我已经'证明'批处理完成了(因为brainfuck被证明是图灵完成的):

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

顺便说一句,图灵完整的编程语言意味着它:

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

传统的图灵机要求你有一个两边都是无限的磁带,但是一个简单的数组,字符串,表(对象)或二进制数(bitfield)也可以工作.在我的"Brainfuck在批处理",例如我使用的阵列/表状物体来存储存储器(由于批处理允许你改变一个值的密钥,例如:SET ARRAY[%KEY%]=%VALUE%)

Answer 2

我相信它有资格.图灵完整性的基本要求被认为可以简化为一些简单的操作,包括:存储状态(变量)的能力,分支(条件)的能力以及迭代(循环)的能力.批处理具有所有这些,因此除非对图灵完整性有一些尚未发现的要求,否则批处理脚本符合条件.