patternModerate
Are Turing machines more powerful than pushdown automata?
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?
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.
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.