0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The same question was posted earlier today, and marked as a duplicate. $\endgroup$
    – Raphael
    Commented Feb 23, 2015 at 11:09
  • $\begingroup$ What about more than 2-stacks addition to PDA. I'm unable to find this information on the forum $\endgroup$
    – Ahmed Faraz
    Commented Feb 23, 2015 at 11:48
  • $\begingroup$ The linked question answers this. $\endgroup$
    – Raphael
    Commented Feb 23, 2015 at 12:16

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ What if we add more stacks (3,4,5,...N) to PDA $\endgroup$
    – Ahmed Faraz
    Commented Feb 23, 2015 at 11:49
  • $\begingroup$ For computability? Nothing. We know of no models more powerful than Turing Machines. $\endgroup$
    – Joey Eremondi
    Commented Feb 23, 2015 at 13:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.