I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with two stacks. I also know that you can’t simulate a Turing machine with a PDA, because a professor challenged a student when he suggested the treating a stack as a matrix, that is, as if it were two arrays. What’s the roadblock?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ The stack can only be accessed in a very particular way. Using two stacks you can simulate a Turing machine, however. $\endgroup$– Yuval FilmusNov 7, 2019 at 19:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The comment of @Yuval tells the intuition behind the answer (the shortcoming of a PDA is that you can iterate only once over the word and you cannot read the second letter in the stack before popping the first one, note that you can keep only constant amount of data in the state).
However, a very concise formal proof why we can not simulate all Turing machines with PDAs is that you can build to each PDA a corresponding context free grammar such that a given word is accepted by a given PDA if and only if it can be constructed with the corresponding grammar source.
Now since CFL is a proper subset of CSL which is again a proper subset of recursive languages which all can be decided by Turing machines, Turing machines can simulate all PDAs but not vise versa. To see why, for a given recursive but not context-free language, say the standard example $a^nb^nc^n$, there is no PDA to compute this language since else there would be a context free grammar to compute it which would make it CFL. On the other hand it is not hard to build a Turing machine that decides this language.
answered Nov 7, 2019 at 22:46