HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Are Turing machines more powerful than pushdown automata?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
arepowerfulthanmorepushdownautomatamachinesturing

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#669, answer score: 17

Revisions (0)

No revisions yet.