图灵机比Pushdown Automata更强大吗？

Question

我在阅读一些自动机书籍时提出了结果，图灵机似乎比俯卧自动机更强大。由于图灵机的胶带总是可以像堆栈一样行为，因此我们实际上可以声称TMS更强大。

这是真的？

Answer 1

如果您只认为始终可以使“图灵机”表现得像堆栈一样”，那么您只能得出结论，它们至少与俯卧撑自动机一样强大。

但总的来说，是的，图灵机比PDA更强大。最简单的例子是证明图灵机可以描述上下文敏感语言。

Answer 2

如果不忘记堆栈的其余部分，您就无法进入堆栈的底部。使用图灵机，您可以轻松地在胶带上来回走动。

这项简单的任务无法通过俯卧式传感器完成（与下降自动机大致相同，但可以在每个步骤写东西），但是可以用磁带轻松完成：

阅读字符串$ W $，然后两次写下字符串：$ WW $

如果您不想听到有关传感器的信息，那么类似的问题也适合您：Turing Machine很容易识别此语言，但不使用俯卧撑自动机识别：

$$ l = {ww mid w inσ^* } $$

但是我认为使用传感器，您可以掌握差异。

Answer 3

图灵机的确比常规PDA更强大。

但是，在具有两个堆栈（TPDA或2-PDA）的PDA的特殊情况下，TPDA比图灵自动机同样强大。

基本想法是，您可以使用两个堆栈模拟TM的磁带：在左堆栈中，所有内容都存储在Turing-Tape上的头部，而头部下方的符号和头部的所有内容都存储在其他堆栈。因此，TPDA可以模拟图灵机的工作，它们是等效的。可以找到稍微详细的描述 这里.

Answer 4

一 图灵机比 一 俯卧撑自动机 - 这是自动机理论的基本定理，可以通过多种方式证明。例如，TMS的停止问题是不确定的 - 没有程序（或其他TM）始终对问题给出正确的是或不答案：此输入中的TM会停止。但是对于PDA，可以解决停止问题。因此，模型具有本质上不同的功率，TM模型比PDA模型具有更多的功率，但也“遭受”。

但 二 下降自动机“一起工作”可以模拟图灵机。我们只需要指定两个PDA一起工作的含义 - 它们都连接到输入字符串，并且每个PDA都可以独立于另一个PDAS来与其堆栈一起工作。它们的有限状态控制也被连接到单个有限状态控制中。

这样大致证明，每个PDA都可以模拟TM胶带的一半，即TMS胶带的一部分，从家族广场开始，无限期地向左或向右驶出。细节可能会变得有些混乱，但是基本想法很简单。 “左”下降店的顶部表示TM的当前头正方形，底部表示TM胶带的最左侧正方形。同样，对于“右”下降店。至于移动，例如，当TM向左移动一个正方形时，PDA的模拟组合会从右下角存储中弹出一个符号，并将其推到左下俯卧撑店的顶部。当TM重写其头部下方的符号时，左PDA弹出其顶部符号（先前的值），然后推回另一个符号（新值）。

因此，使用这种方式工作的两个PDA的组合具有与TMS完全相同的功率，而组合的停止问题也是不可决定的。

Answer 5

只需展示一个接受$ 0^n 1^n 2^n $的TM，这不是免费上下文（因此没有PDA接受它）。

Answer 6

通常的证据是绕行的证据。

1. 证明Puspdown-Automata完全接受 无上下文的语言, ，由无上下文语法接受的一组语言。 （在任何有关此事的教科书中找到）
2. 请注意，图灵机（根据定义）接受所有递归语言。
3. 表明上下文无语言是递归语言的正确子集，例如通过 抽动引理 - 通过无上下文的语法很容易证明这一点 - 以及$ {ww mid w in {a，b }^*} $。