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

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显然是多余的。