Dit is waarom:

* Oneindige PDA-kracht: Een oneindige PDA heeft een onbegrensde stapel, net als een gewone PDA. Het ‘oneindige’ deel verwijst waarschijnlijk naar het potentieel om eeuwig te blijven bestaan, wat inherent is aan elk Turing-compleet-model. Het cruciale aspect is de *onbegrensde* stapel. Deze grenzeloosheid geeft het een krachtig vermogen om informatie op te slaan en op te halen, wat de mogelijkheden van eindige toestandsmachines overtreft.

* Gelijkwaardigheid met Turing-machines: Een Turing Machine (TM) is een rekenmodel waarvan bekend is dat het qua kracht gelijkwaardig is aan algoritmen. Het is in staat om elk algoritme te simuleren. Het is algemeen bekend dat een PDA aangevuld met twee stapels (of zelfs één stapel en de mogelijkheid om de kop willekeurig op de invoerband te bewegen) gelijkwaardig is aan een Turing-machine.

* Onbeslisbare talen: Turingmachines kunnen talen herkennen die onbeslisbaar zijn. Een taal is onbeslisbaar als er geen Turingmachine bestaat die kan stoppen en correct kan bepalen of een bepaalde string tot de taal behoort. Het klassieke voorbeeld is het stopprobleem:bepalen of een bepaalde Turingmachine zal stoppen bij een bepaalde invoer.

* Implicatie voor Infinite PDA's: Omdat een oneindige PDA met zijn onbegrensde stapel een Turingmachine kan simuleren, kan hij daarom onbeslisbare talen herkennen. Als een taal onbeslisbaar is, betekent dit dat er geen algoritme (en dus geen Turingmachine) is dat kan beslissen over het lidmaatschap van die taal. Omdat de PDA een Turing-machine kan simuleren, kan hij ook niet beslissen over lidmaatschap van die taal.

Samengevat:

Als "oneindige PDA" verwijst naar een standaard PDA met een onbegrensde stapel, dan kan zo'n PDA een Turing-machine simuleren. Omdat Turing-machines onbeslisbare talen kunnen herkennen, kan de oneindige PDA dat ook. Daarom is de taal die door een oneindige PDA wordt herkend *niet* noodzakelijkerwijs beslisbaar.

Voorbeeld:

Overweeg een (zeer theoretische) PDA die een Turing-machine simuleert die het stopprobleem oplost. De input van de PDA zou een beschrijving zijn van een Turingmachine en zijn input. De PDA zou op die input de uitvoering van die Turingmachine simuleren. De PDA accepteert het als de gesimuleerde Turingmachine stopt, en wijst het af als de gesimuleerde Turingmachine niet stopt.

Omdat het stopprobleem onbeslisbaar is, is er geen algoritme dat kan garanderen dat het kan bepalen of de gesimuleerde Turingmachine zal stoppen. Daarom is de taal die door deze PDA wordt geaccepteerd (de taal van de beschrijvingen en invoer van Turing-machines waar de machine stopt) ook onbeslisbaar.

Het antwoord is dus definitief nee.