基于堆栈的语言的图灵完备性证明
Proof of Turing Completeness for a stack-based language
我正在编写一种基于堆栈操作的笑话语言。我试图找到使图灵完备所需的最少指令量，但不知道基于一个堆栈的语言是否甚至可以是图灵完备的。这些说明是否足够？
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 and this one），并认为上述说明已经足够。我对么？还是我需要其他东西，比如函数调用、变量或另一个堆栈？
如果这些说明足够了，那么它们中的任何一个都是多余的吗？
编辑： 通过添加 ROTATE 命令（将堆栈的前三个值从 A B C 更改为 B C A）并消除 DUPLICATE、PLUS 和 SWAP 命令可以实现 Rule 110 cellular automaton 的 3 字符版本。这足以证明图灵完备性吗？
如果有没有变量或函数的图灵完备单栈语言的例子就好了。
如果你想证明你的语言是图灵完备的，那么你应该看看 Math StackExchange 网站上的这个问答。
一种方法是看看您是否可以使用您的语言编写可以模拟任意图灵机的程序。如果可以，那就是图灵完备性的证明。
如果您想知道这些指令中的任何一条是否多余，请查看您是否可以简化您的 TM 模拟器以不使用其中一条指令。
但是如果您想知道是否可以使用更小的图灵完备语言，请查看 SKI Combinator Calculus。可以说，存在三个指令：S、K 和 I 组合子。 I 显然是多余的。
正如其他人指出的那样，如果您可以模拟任何图灵机，那么您的语言就是图灵完备的。
然而，尽管图灵机的概念简单且适合数学处理，但它并不是最容易模拟的机器。
作为捷径，你可以模拟一些已经被证明是图灵完备的简单语言。
我的直觉告诉我，函数式语言，尤其是 LISP，可能是一个不错的选择。 This SO Q&A 提供了关于最小图灵完备 LISP 的指示。
仅基于单个堆栈的语言不能是图灵完备的（除非你通过允许临时变量之类的东西或访问“更深”的值来“作弊”堆栈比顶部项目）。按照我的理解，这样的语言相当于Pushdown Automata，它可以实现一些东西（例如上下文无关语法）但肯定不如完整的图灵机.
话虽如此，图灵机实际上比您直觉上预期的要低得多 - 正如最初制定的那样，它们只不过是一个链表、读取和修改链表以及分支的能力。您甚至不需要向纯面向堆栈的语言添加那么多内容以使其等同于图灵机——从技术上讲，第二个堆栈就可以做到这一点（尽管我当然不想针对它进行编程），就像链表或队列。
如果我错了请纠正我，但我认为建立你可以读取和写入内存，可以进行分支，并且至少拥有其中一种数据结构（两个堆栈，一个队列，一个链表或等效项）足以建立图灵完备性。
您可能还想看看 Chomsky hierarchy（看起来您可能漂浮在 Type 1 或 Type 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)
我查看了几个问题和答案（如 this one and this one），并认为上述说明已经足够。我对么？还是我需要其他东西，比如函数调用、变量或另一个堆栈？
如果这些说明足够了，那么它们中的任何一个都是多余的吗？
编辑： 通过添加
ROTATE 命令（将堆栈的前三个值从 A B C 更改为 B C A）并消除 DUPLICATE、PLUS 和 SWAP 命令可以实现 Rule 110 cellular automaton 的 3 字符版本。这足以证明图灵完备性吗？
如果有没有变量或函数的图灵完备单栈语言的例子就好了。
如果你想证明你的语言是图灵完备的，那么你应该看看 Math StackExchange 网站上的这个问答。
一种方法是看看您是否可以使用您的语言编写可以模拟任意图灵机的程序。如果可以，那就是图灵完备性的证明。
如果您想知道这些指令中的任何一条是否多余，请查看您是否可以简化您的 TM 模拟器以不使用其中一条指令。
但是如果您想知道是否可以使用更小的图灵完备语言，请查看 SKI Combinator Calculus。可以说，存在三个指令：S、K 和 I 组合子。 I 显然是多余的。
正如其他人指出的那样，如果您可以模拟任何图灵机，那么您的语言就是图灵完备的。
然而，尽管图灵机的概念简单且适合数学处理，但它并不是最容易模拟的机器。
作为捷径，你可以模拟一些已经被证明是图灵完备的简单语言。
我的直觉告诉我，函数式语言，尤其是 LISP，可能是一个不错的选择。 This SO Q&A 提供了关于最小图灵完备 LISP 的指示。
仅基于单个堆栈的语言不能是图灵完备的（除非你通过允许临时变量之类的东西或访问“更深”的值来“作弊”堆栈比顶部项目）。按照我的理解，这样的语言相当于Pushdown Automata，它可以实现一些东西（例如上下文无关语法）但肯定不如完整的图灵机.
话虽如此，图灵机实际上比您直觉上预期的要低得多 - 正如最初制定的那样，它们只不过是一个链表、读取和修改链表以及分支的能力。您甚至不需要向纯面向堆栈的语言添加那么多内容以使其等同于图灵机——从技术上讲，第二个堆栈就可以做到这一点（尽管我当然不想针对它进行编程），就像链表或队列。
如果我错了请纠正我，但我认为建立你可以读取和写入内存，可以进行分支，并且至少拥有其中一种数据结构（两个堆栈，一个队列，一个链表或等效项）足以建立图灵完备性。
您可能还想看看 Chomsky hierarchy（看起来您可能漂浮在 Type 1 或 Type 2 语言附近的某个地方）。