我正在编写一种基于堆栈操作的笑话语言。我试图找到使其图灵完备所需的最少指令量，但不知道基于一个堆栈的语言是否可以是图灵完备的。这些说明就足够了吗？
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个字符版本。这足以证明图灵完备性吗？
如果有一个没有变量或函数的图灵完备单栈语言的例子，那就太好了。
如果你想证明你的语言是图灵完备的，那么你应该看看Math StackExchange网站上的这个问答。
- 如何证明编程语言是图灵完备的？
一种方法是查看是否可以使用您的语言编写可以模拟任意图灵机的程序。 如果可以的话，那就是图灵完备性的证明。
如果您想知道这些指令中的任何一个是否是多余的，请查看是否可以简化 TM 模拟器以不使用其中一条指令。
但是，如果你想知道较小的图灵完备语言是否可行，请查看SKI Combinator Calculus。 可以说，有三个指令：S、K和I组合器。I显然是多余的。
仅基于单个堆栈的语言不可能是图灵完备的(除非你通过允许临时变量之类的东西或访问堆栈中比顶部项目"更深"的值来"作弊"(。据我所知，这种语言相当于下推自动机，它可以实现一些东西(例如上下文无关的语法(，但肯定不如完整的图灵机。
话虽如此，图灵机实际上比你直觉预期的要低得多 - 正如最初制定的那样，它们只不过是一个链表，读取和修改链表的能力，以及分支。你甚至不需要向纯粹面向堆栈的语言添加那么多东西来使其等同于图灵机 - 第二个堆栈在技术上可以做到这一点(尽管我当然不想针对它编程(，链表或队列也是如此。
如果我错了，请纠正我，但我认为建立你可以读取和写入内存，可以进行分支，并且至少有一个数据结构(两个堆栈，一个队列，一个链表，或等效(就足以建立图灵完备性。
也看看嵌套堆栈自动机。
您可能还想查看乔姆斯基层次结构(似乎您可能漂浮在类型 1 或类型 2 语言附近的某个地方(。
正如其他人所指出的，如果你可以模拟任何图灵机，那么你的语言就是图灵完备的。
然而，图灵机尽管概念简单，并且易于数学处理，但并不是最容易模拟的机器。
作为捷径，您可以模拟一些已被证明为图灵完备的简单语言。
我的直觉告诉我，函数式语言，特别是LISP，可能是一个不错的选择。这个SO问答指向了最小图灵完备LISP是什么样子的。