turing-machines - 有两个堆栈的 PDA 可以接受 RE 语言吗？

Question

所以，我很难弄清楚图灵机不会停止的字符串究竟是什么意思。我在某处读到图灵机相当于具有 2 个堆栈的确定性自动机。但是，当对于任何有限字符串确定要停止时，具有 2 个堆栈的确定性自动机将如何接受不会停止的字符串……我是否遗漏了什么？

Answer 1

一个有两个堆栈的 PDA 相当于一个图灵机。为了说明 TM 至少与两层 PDA 一样强大，我们可以使用 TM 与两带 TM 完全一样强大的事实。在双磁带 TM 中，我们可以限制磁带的使用来模拟它们的堆叠。因此，当然，TM 可以做两层 PDA 可以做的任何事情。

显示具有两个堆栈的 PDA 至少与两个堆栈 TM 一样强大有点棘手，但基本上的想法是您可以使用两个堆栈模拟单个磁带，如下所示:

调用一个堆栈 L 和另一个 R

L 的内容代表磁带头左侧的所有内容(包括当前符号)

R 的内容代表磁带头右侧的所有内容

覆盖当前交易品种:从 L 弹出并推到 L

在磁带中向左移动:从 L 弹出并推到 R

在磁带中向右移动:从 R 弹出并推到 L

因此，我们可以左右移动并覆盖符号。这让我们可以模拟磁带，这是 TM 所能做的。