Are Turing machines more powerful than pushdown automata?

Question

I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.

Is this true?

Answer 1

If you only consider that 'Turing machines can always be made to behave like a stack' you can only conclude that they are at least as powerful as pushdown automata.

But in general, yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can describe Context Sensitive Languages.

Answer 2

You can't go to the bottom of the stack without "forgetting" the rest of the stack. With a Turing machine you can easily go back and forth on the tape.

This simple task cannot be done with a pushdown transducer (roughly the same thing as the pushdown automata, but that can write things at each step), but can easily be done with a tape:

Read a string $w$ and then write the string twice: $ww$

If you don't want to hear about transducers, the similar problem is for you: this language is easily recognized by a Turing machine, but not with a pushdown automaton:

$$L = \{ ww \mid w \in Σ^* \}$$

but I think with a transducer you get a grasp of the difference.

Answer 3

Turing machines are indeed more powerful than regular PDAs.

However in special case of a PDA with two stacks (TPDA or 2-PDA) the TPDA is equally powerful than a turing automata.

The basic idea is that you can simulate the TM's tape using two stacks: in the left stack everything is stored which is left from the head on the Turing-tape, while the symbol under the head and everything right from the head is stored in the other stack. And thus the TPDA can simulate the work of a Turing machine, and they are equivalent. A slightly more detailed description can be found here.

Answer 4

One Turing machine is more powerful than one pushdown automaton -- that is a fundamental theorem of automata theory and can be proved in a number of ways. For example, the halting problem for TMs is undecidable -- there is no program (or other TM) that will always give a correct yes-or-no answer to the question: will this TM on this input halt. But for PDAs, the halting problem is solvable. So the models have inherently different power, the TM model has more power than the PDA model, but also "suffers" for it.

But two pushdown automata "working together" can simulate a Turing machine. We just have to specify what we mean by two PDAs working together -- they are both connected to the input string and each can work with its stack independently of the other. Their finite state controls are also connected, or equivalently, merged into a single finite-state control.

The proof of that goes roughly that each of the PDAs can simulate half of the TM's tape, that is, the part of the TMs tape starting at the home square and going out indefinitely to the left or right. The details can get a bit messy, but the basic idea is simple. The top of the "left" pushdown store represents the current head square of the TM and the bottom represents the leftmost active square of the TM's tape; similarly for the "right" pushdown store. As for moves, for example, when the TM moves one square to the left, the simulating combo of PDAs pops a symbol from the right pushdown store and pushes it onto the top of the left pushdown store. When the TM rewrites the symbol under its head, the left pda pops its top symbol (the prior value) and pushes back another symbol (the new value).

So the combo of two PDAs working this way has exactly the same power as TMs, and the halting problem for the combo is also undecidable.

Answer 5

Just exhibit a TM accepting $0^n 1^n 2^n$, which isnt't context free (and thus there is no PDA accepting it).

Answer 6

The usual proof is one with detour.

1. Show that pushdown-automata accept exactly the context-free languages, the set of languages accepted by context-free grammars. (found in any text book on the matter)
2. Note that Turing machines accept all recursive languages (by definition).
3. Show that the context free languages are a proper subset of the recursive languages, for instance via Pumping Lemma -- which is easily proven on with context-free grammars -- and $\{ww \mid w\in \{a,b\}^*\}$.