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

Question

所以，我很难弄清楚图灵机不会停止的字符串到底是什么意思。我在某处读到图灵机相当于具有 2 个堆栈的确定性自动机。但是，具有 2 个堆栈的确定性自动机将如何接受一个不会停止的字符串，而对于任何有限的字符串，它决定停止......我错过了什么吗？

Answer 1

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

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

1. 调用一个堆栈 L 和另一个 R
2. L 的内容代表磁带头左侧的所有内容（包括当前符号）
3. R的内容代表磁带头右侧的所有内容
4. 覆盖当前符号：从 L 弹出并推到 L
5. 要在磁带中向左移动：从 L 弹出并推到 R
6. 要在磁带中向右移动：从 R 弹出并推到 L

因此，我们可以左右移动并覆盖符号。这让我们可以模拟磁带，这是 TM 无论如何都可以做的。