Είναι δυνατόν να δείξουμε ότι η γλώσσα που αναγνωρίζεται από ένα άπειρο αυτόματο automaton είναι αποφασιστική;

Όχι, δεν είναι δυνατόν να δείξουμε ότι η γλώσσα που αναγνωρίζεται από ένα Infinite Pushdown Automaton (PDA) είναι αποφασιστική. Στην πραγματικότητα, η γλώσσα που αναγνωρίζεται από ένα άπειρο PDA δεν είναι * απαραίτητα αποφασιστικό.

Εδώ είναι γιατί:

* Άπειρη ισχύ PDA: Ένα άπειρο PDA έχει μια απεριόριστη στοίβα, ακριβώς όπως ένα κανονικό PDA. Το "άπειρο" μέρος πιθανώς αναφέρεται στις δυνατότητές του να τρέχει για πάντα, το οποίο είναι εγγενές σε οποιοδήποτε μοντέλο Turing-Complete. Η κρίσιμη πτυχή είναι η * απεριόριστη * στοίβα. Αυτή η άθλια της δίνει μια ισχυρή ικανότητα να αποθηκεύει και να ανακτά πληροφορίες, υπερβαίνοντας τις δυνατότητες των μηχανών πεπερασμένων κρατών.

* Ισοδυναμία με μηχανές Turing: Ένα μηχάνημα Turing (TM) είναι ένα υπολογιστικό μοντέλο που είναι γνωστό ότι είναι ισοδύναμο στην εξουσία σε αλγόριθμους. Είναι ικανό να προσομοιώνει οποιονδήποτε αλγόριθμο. Είναι καλά εδραιωμένο το γεγονός ότι ένα PDA αυξάνεται με δύο στοίβες (ή ακόμα και μία στοίβα και η δυνατότητα να μετακινείται αυθαίρετα το κεφάλι στην ταινία εισόδου) είναι ισοδύναμη με μια μηχανή Turing.

* Ανεξάρτητες γλώσσες: Οι μηχανές Turing μπορούν να αναγνωρίσουν γλώσσες που είναι αδιαμφισβήτητες. Μια γλώσσα είναι αδιαμφισβήτητη εάν δεν υπάρχει μηχανή Turing που μπορεί να σταματήσει και να καθορίσει σωστά εάν μια δεδομένη συμβολοσειρά ανήκει στη γλώσσα. Το κλασικό παράδειγμα είναι το πρόβλημα διακοπής:ο καθορισμός εάν μια δεδομένη μηχανή Turing θα σταματήσει σε μια δεδομένη είσοδο.

* ΕΠΙΣΤΡΟΦΗ για άπειρα PDAs: Δεδομένου ότι ένα άπειρο PDA με την απεριόριστη στοίβα του μπορεί να προσομοιώσει μια μηχανή Turing, μπορεί επομένως να αναγνωρίσει τις μη αποδοτικές γλώσσες. Εάν μια γλώσσα είναι αδιαμφισβήτητη, σημαίνει ότι δεν υπάρχει αλγόριθμος (και επομένως δεν υπάρχει μηχανή Turing) που να μπορεί να αποφασίσει την ένταξη σε αυτή τη γλώσσα. Επειδή το PDA μπορεί να προσομοιώσει ένα μηχάνημα Turing, δεν μπορεί επίσης να αποφασίσει τη συμμετοχή σε αυτή τη γλώσσα.

Συνοπτικά:

Εάν το "Infinite PDA" αναφέρεται σε ένα πρότυπο PDA με μια απεριόριστη στοίβα, τότε ένα τέτοιο PDA μπορεί να προσομοιώσει μια μηχανή Turing. Δεδομένου ότι οι μηχανές Turing μπορούν να αναγνωρίσουν τις μη εξειδικευμένες γλώσσες, μπορούν και το άπειρο PDA. Επομένως, η γλώσσα που αναγνωρίζεται από ένα άπειρο PDA δεν είναι * απαραίτητα αποφασιστική.

Παράδειγμα:

Εξετάστε ένα (εξαιρετικά θεωρητικό) PDA που προσομοιώνει ένα μηχάνημα Turing που επιλύει το πρόβλημα διακοπής. Η είσοδος του PDA θα ήταν μια περιγραφή μιας μηχανής Turing και της εισόδου του. Το PDA θα προσομοιώσει την εκτέλεση αυτής της μηχανής Turing σε αυτήν την είσοδο. Το PDA αποδέχεται εάν η προσομοιωμένη μηχανή Turing σταματά και απορρίπτει εάν η προσομοιωμένη μηχανή Turing δεν σταματά.

Δεδομένου ότι το πρόβλημα αναστολής είναι αδιαμφισβήτητο, δεν υπάρχει αλγόριθμος που να μπορεί να εγγυηθεί για να καθορίσει εάν η προσομοιωμένη μηχανή Turing θα σταματήσει. Επομένως, η γλώσσα που αποδεικνύεται από αυτό το PDA (η γλώσσα των περιγραφών και των εισροών του μηχανισμού Turing, όπου σταματάει το μηχάνημα) είναι επίσης αδιαμφισβήτητη.

Επομένως, η απάντηση είναι οριστικά όχι.