我找不到它是否符合条件并且很好奇 - 如果它不符合条件,它缺少什么功能来符合条件?我已经完成了大量的批处理,没有发现任何明显的能力失误。
最佳答案
我刚刚通过批量创建一个 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%
)
关于windows - Batch 图灵完成了吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11126539/