# Are Turing machines more powerful than pushdown automata?

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?

-
– Dave Clarke Mar 22 '12 at 20:08
@DaveClarke: It didn't help me to answer this question. – Gigili Mar 22 '12 at 20:10
You should not skip the parts labeled "Proof". ;) – Raphael Mar 22 '12 at 21:46
A push down automata can work only on stack but TM is not. SO easing that restriction itself make TM more powerfull – user5507 Nov 25 '12 at 16:34

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.

-
Turing Machines describe recursively enumerable... Linear Bound Automata describe Context Sensitive Languages. – Evil Angel May 12 '14 at 12:16

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.

-

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.

-

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.

-
PDAs can only solve the halting problem on languages they recognize, and TMs can solve the halting problem on all languages PDAs can recognize, and more. So how does that make PDAs more powerful from any point of view? – Kevin Mar 23 '12 at 13:28
@Kevin -- The usual meaning of "The halting problem" for a class of languages is that it is solvable by any algorithm, that is, by a TM. One could analyze the ability of any model to solve the halting problem for any other model or class of languages. But that is usually done in the context of analyzing the range of decidable/undecidable problems for a model, or equivalently, situating the class of languages defined by the model in various hierarchies, of which the decidable/undecidable "hierarchy" is only one. IAC, even two PDAs are not more powerful than TMs, they are equivalent. – David Lewis Mar 23 '12 at 17:22
Perhaps I'm misunderstanding what you mean by "But for PDAs, the halting problem is solvable." That sounds to me like you're saying that it's an advantage for PDAs that their halting can be decided but TMs' can't. In other words, that restricting languages to (a subset of) those that can be decided is in some way better than allowing all languages. – Kevin Mar 23 '12 at 17:41
@Kevin -- Well, it's not a morality play. ;-)) But seriously, there are advantages to using less powerful models of computation in actual practice, if they can solve the problem in question, and the halting problem is one way of expressing that. Practical advantages might include the possibility of more powerful debugging tools, for example, a tool to spot infinite loops or other pathological behavior that are not detectable with full-power (Turing universal) models. This is a big topic, and would make a neat question on cs.stackexchange. – David Lewis Mar 23 '12 at 23:48

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\}^*\}$.
-

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

-