2

我正在编写一种基于堆栈操作的笑话语言。我试图找到使其图灵完备所需的最少指令量，但不知道基于一个堆栈的语言是否甚至可以图灵完备。这些说明就足够了吗？

IF (top of stack is non-zero)
WHILE (top of stack is non-zero)
PUSH [n-bit integer (where n is a natural number)]
POP
SWAP (top two values)
DUPLICATE (top value)
PLUS (adds top two values, pops them, and pushes result)

我已经查看了几个问题和答案（例如这个和这个），并相信上述说明就足够了。我对么？还是我需要其他的东西，比如函数调用、变量或另一个堆栈？

如果这些说明足够，它们中的任何一个都是多余的吗？

编辑：通过添加ROTATE命令（将堆栈的前三个值从A B C更改为B C A）并消除DUPLICATE、PLUS和SWAP命令，可以实现规则 110 元胞自动机的 3 字符版本。这足以证明图灵完备吗？

如果有一个没有变量或函数的图灵完备的单栈语言的例子，那就太好了。

4

3 回答 3

4

如果您想证明您的语言是图灵完备的，那么您应该在 Math StackExchange 网站上查看此问答。

一种方法是查看您是否可以使用可以模拟任意图灵机的语言编写程序。如果可以，这就是图灵完备性的证明。

如果您想知道这些指令是否是多余的，请查看是否可以简化您的 TM 仿真器以不使用其中一个指令。

但是，如果您想知道是否可以使用更小的图灵完备语言，请查看SKI Combinator Calculus。可以说，存在三个指令：S和K组合I子。而且I显然是多余的。

于 2017-07-02T01:07:24.420 回答
2

仅基于单个堆栈的语言不能是图灵完备的（除非您通过允许临时变量之类的东西“作弊”或访问堆栈中比顶部项目“更深”的值）。据我了解，这种语言相当于下推自动机，它可以实现一些东西（例如上下文无关语法），但肯定不如完整的图灵机。

话虽如此，图灵机实际上比您直观地预期的要低得多——按照最初的表述，它们只不过是一个链表、读取和修改链表的能力以及分支。您甚至不需要在纯粹的面向堆栈的语言中添加太多内容以使其等效于图灵机 - 第二个堆栈在技术上会做到这一点（尽管我当然不想针对它进行编程），就像链表或队列。

如果我错了，请纠正我，但我认为确定您可以读取和写入内存，可以进行分支，并且至少具有其中一种数据结构（两个堆栈，一个队列，一个链表，或等价的）将足以建立图灵完备性。

也看一下嵌套堆栈自动机。

您可能还想查看Chomsky 层次结构（看起来您可能漂浮在 Type 1 或 Type 2 语言附近的某个地方）。

于 2017-07-20T21:03:36.763 回答
1

正如其他人指出的那样，如果您可以模拟任何图灵机，那么您的语言就是图灵完备的。

然而，图灵机尽管概念简单且易于数学处理，但并不是最容易模拟的机器。

作为一种捷径，你可以模拟一些已经被证明是图灵完备的简单语言。

我的直觉告诉我，函数式语言，尤其是 LISP，可能是一个不错的选择。这个SO Q&A 指出了最小图灵完备 LISP 的样子。

于 2017-07-02T12:16:06.657 回答