Nej, det är inte möjligt att visa att det språk som erkänns av en oändlig pushdown -automat (PDA) är avgörande. I själva verket är det språk som erkänns av en oändlig PDA * inte * nödvändigtvis avgörande.
Här är varför:
* oändlig PDA -kraft: En oändlig PDA har en obegränsad stack, precis som en vanlig PDA. Den "oändliga" delen hänvisar sannolikt till dess potential att köra för evigt, vilket är inneboende i alla Turing-kompletta modell. Den avgörande aspekten är den * obundna * stacken. Denna obegränsning ger den en kraftfull förmåga att lagra och hämta information och överskrida kapaciteten hos ändliga tillståndsmaskiner.
* ekvivalens till Turing Machines: En Turing Machine (TM) är en beräkningsmodell som är känd för att vara ekvivalent i kraft till algoritmer. Det kan simulera någon algoritm. Det är väl etablerat att en PDA förstärks med två staplar (eller till och med en stack och förmågan att godtyckligt flytta huvudet på ingångstejpen) motsvarar en Turing-maskin.
* Olyckliga språk: Turing -maskiner kan känna igen språk som är obeslutbara. Ett språk är obeslutbart om det inte finns någon Turing -maskin som kan stoppa och korrekt avgöra om en given sträng tillhör språket. Det klassiska exemplet är stoppproblemet:att bestämma om en given Turing -maskin kommer att stoppa vid en given ingång.
* Implikation för oändliga PDA: Eftersom en oändlig PDA med sin obegränsade stack kan simulera en Turing -maskin kan den därför känna igen obeslutbara språk. Om ett språk är obeslutbart betyder det att det inte finns någon algoritm (och därför ingen Turing -maskin) som kan bestämma medlemskap på det språket. Eftersom PDA kan simulera en Turing -maskin kan den inte bestämma medlemskap på det språket.
Sammanfattningsvis:
Om "oändlig PDA" hänvisar till en standard PDA med en obegränsad stack, kan en sådan PDA simulera en Turing -maskin. Eftersom Turing -maskiner kan känna igen obeslutbara språk, kan den oändliga PDA också. Därför är det språk som erkänns av en oändlig PDA * inte * nödvändigtvis avgörande.
Exempel:
Tänk på en (mycket teoretisk) PDA som simulerar en Turing -maskin som löser stoppproblemet. PDA:s ingång skulle vara en beskrivning av en Turing -maskin och dess ingång. PDA skulle simulera exekveringen av den Turing -maskinen på den ingången. PDA accepterar om den simulerade Turing -maskinen stoppar och avvisar om den simulerade Turing -maskinen inte stoppar.
Eftersom stoppproblemet är obeslutbart finns det ingen algoritm som kan garantera att avgöra om den simulerade Turing -maskinen kommer att stoppa. Därför är det språk som accepteras av denna PDA (språket för Turing -maskinbeskrivningar och ingångar där maskinen stoppar) också obeslutbar.
Därför är svaret definitivt nej.
