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

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)

我已经查看了几个问题和答案(例如 this one 和 this one )，并相信上述说明已经足够了。我对么？或者我是否需要其他东西，例如函数调用、变量或另一个堆栈？

如果这些说明足够了，其中有哪些是多余的吗？

<小时/> 编辑:通过添加 ROTATE命令(将堆栈的前三个值从 A B C更改为 B C A)并消除了 DUPLICATE、 PLUS和 SWAP命令，可以实现 Rule 110 cellular automaton的3个字符版本。 。这足以证明图灵完备性吗？

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

Answer 1

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

• How to Prove a Programming Language is Turing Complete?

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

<小时/>

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

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