Problem Detail: Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation? It’s been told that PDA with 2-Stacks is equally powerful to Turning Machine. But what if we add more stacks i.e. 3, 4, 5…N to PDA; will it become more powerful or it can serve same purpose.
Asked By : Ahmed Faraz Hashmi
Answered By : jmite
2 stacks is enough for a PDA to be as powerful as a Turing Machine. Basically, you can pop from one stack and push into the other to simulate moving across the tape head, writing, etc. In fact, a 2-counter machine is as powerful as a Turing Machine, though the proof is much more involved. There’s a sketch of it on Wikipedia
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/39705
