基于堆栈的语言的图灵完备性证明

Question

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

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 个字符版本。这足以证明图灵完备性吗？

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

Answer 1

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

• 如何证明编程语言是图灵完备的？

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

---

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

但是如果您想知道是否可以使用更小的图灵完备语言，请查看 SKI Combinator Calculus。可以说，共有三个指令：

S

、

K

和

I

组合器。而且

I

显然是多余的。

Answer 2

仅基于单个堆栈的语言不能是图灵完备的（除非你通过允许临时变量或访问堆栈中比顶部项目“更深”的值来“作弊”）。据我了解，这样的语言相当于“下推自动机”，它可以实现“一些”东西（例如上下文无关语法），但肯定不如完整的图灵机。 话虽如此，图灵机实际上比你直观预期的要低得多 - 正如最初制定的那样，它们只不过是一个链表、读取和修改链表的能力以及分支。您甚至不需要向纯粹面向堆栈的语言添加那么多内容以使其相当于图灵机 - 第二个堆栈在技术上可以做到这一点（尽管我当然不想针对它进行编程），就像链表或队列。 如果我错了，请纠正我，但我认为建立你可以读取和写入内存，可以进行分支，并且至少拥有其中一种数据结构（两个堆栈，一个队列，一个链表，或同等内容）足以建立图灵完备性。

也请查看

嵌套堆栈自动机

。

您可能还想查看 乔姆斯基层次结构（看起来您可能漂浮在类型 1 或类型 2 语言附近的某个地方）。

（我在这里要掩盖的一点是，原始模型没有对内存消耗进行任何限制，因此允许链表任意大。显然，这在真实的计算机上是不正确的，所以从技术上来说线性有界自动机是真实计算机的更现实的模型）。

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

Answer 3

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

我的直觉告诉我，函数式语言，尤其是 LISP，可能是一个不错的选择。

This

SO Q&A 指出了最小图灵完备 LISP 的样子。