Question Detail: 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?
Asked By : Gigili
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/669
Answered By : Mike B.
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.
