如果开括号什么都不做的话,图灵仍然是完整的吗

  • 本文关键字:图灵 仍然是 如果 brainfuck
  • 更新时间 :
  • 英文 :


我正在开发一个8位CPU的物理实验板,它可以直接解释大脑。

语言规范表明开括号和闭括号都有逻辑:

[=>跳转到匹配]如果为零

]=>跳转到匹配[除非为零

但以我的CPU制造方式,我无法实现第一条规则,很难找到匹配的右括号。

将左括号逻辑更改为什么都不做,只保留右括号逻辑会有什么后果?它会影响语言的图灵完备性吗?

我知道这将不再是Brainfuck,现有的程序可能不再正常工作,例如:

[+.]

经典的头脑风暴:不会做任何事

我修改后的大脑操:将打印从0到255的每个字符(如果单元格没有循环回0,则会出现溢出错误(

在这里的讨论中,Int-e展示了这一点"一边干一边干"变体是图灵完备的,通过从一个稍微有限的形式的正则brainfuck(必须在一开始就得到所有输入(的约简。如果你愿意,我可以把我的通用图灵机程序翻译成这个变体。

在这种情况下,它不会是图灵完备的,因为它缺少条件句。你能做的最好的事情是用常数改变数字,或者用常数改变用户输入(例如a->c,b->d(。

为了让你的CPU图灵变得完整,你可以尝试另一种深奥的编程语言,一种解释特定指令的参数而不是符号的语言。

最新更新