Ποια είναι μερικά παραδείγματα μη αποδοτικών γλωσσών και πώς διαφορετικά από τις αποφασιστικές γλώσσες;

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

Ακολουθούν ορισμένα παραδείγματα μη ακινητοποιημένων γλωσσών, που απεικονίζουν διαφορετικούς τρόπους που προκύπτουν η αδιαφορία:

1. Το πρόβλημα διακοπής (h):

* Περιγραφή γλώσσας: H ={⟨m, w⟩ | Το μηχάνημα Turing M σταματάει την είσοδο W}. Αυτή η γλώσσα αποτελείται από όλα τα ζεύγη κωδικοποίησης ενός μηχανήματος Turing (⟨m⟩) και μια συμβολοσειρά εισόδου (W) έτσι ώστε το μηχάνημα να σταματάει όταν δοθεί η είσοδος.

* Ανεξάρτητα: Είναι αποδεδειγμένο ότι κανένας αλγόριθμος δεν μπορεί να υπάρχει που να καθορίζει σωστά, για κάθε ⟨m, w⟩, είτε το M σταματάει στο w. Πρόκειται για ένα θεμελιώδες αποτέλεσμα στη θεωρία της υπολογιστικότητας. Οποιαδήποτε προσπάθεια οικοδόμησης ενός τέτοιου αλγορίθμου οδηγεί σε μια αντίφαση (συνήθως μέσω της διαγώνιας).

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

2. Το πρόβλημα αποδοχής (α):

* Περιγραφή γλώσσας: A ={⟨m, w⟩ | Η μηχανή Turing M δέχεται W}. Αυτό είναι παρόμοιο με το πρόβλημα διακοπής, αλλά επικεντρώνεται ειδικά στην αποδοχή (το μηχάνημα σταματά σε κατάσταση αποδοχής).

* Ανεξάρτητα: Αυτό είναι επίσης αδιαμφισβήτητο. Εάν μπορούσαμε να αποφασίσουμε Α, θα μπορούσαμε επίσης να αποφασίσουμε το H (γιατί αν το m δέχεται w, σαφώς σταματάει το w). Δεδομένου ότι το H είναι ανεφάρμοστο, το Α πρέπει επίσης να είναι ανεφάρμοστο.

3. Το πρόβλημα κενότητας για τις μηχανές Turing (e):

* Περιγραφή γλώσσας: E ={⟨m⟩ | L (m) =∅} όπου l (m) είναι η γλώσσα που γίνεται αποδεκτή από το Machine Turing M. Αυτή η γλώσσα περιέχει τις κωδικοποιήσεις όλων των μηχανών Turing που δεν δέχονται καθόλου χορδές (η γλώσσα τους είναι κενή).

* Ανεξάρτητα: Δεν υπάρχει αλγόριθμος που να μπορεί να καθορίσει, για κάθε μηχανή Turing M, είτε το L (m) είναι άδειο. Αυτό σχετίζεται με το πρόβλημα διακοπής. Εάν μπορούσαμε να λύσουμε το E, θα μπορούσαμε να λύσουμε το πρόβλημα διακοπής, κατασκευάζοντας ένα μηχάνημα που σταματά εάν και μόνο αν ο M σταματά και αποδέχεται το w.

4. Πρόβλημα αλληλογραφίας (PCP):

* Περιγραφή γλώσσας: Αυτό είναι ένα πιο περίπλοκο παράδειγμα που περιλαμβάνει ζευγάρια χορδών. Είναι αδιαμφισβήτητο να προσδιορίσουμε εάν ένα δεδομένο σύνολο ζεύγους συμβολοσειρών έχει μια λύση (μια συγκόλληση των χορδών από τα ζεύγη που ταιριάζουν).

* Ανεξάρτητα: Η μη αποικοδόμηση του PCP αποδεικνύεται χρησιμοποιώντας μειώσεις (δείχνοντας ότι εάν η PCP ήταν αποφασιστική, τότε το πρόβλημα διακοπής θα ήταν επίσης αποφασιστικό - μια αντίφαση).

Αποφασιστικές γλώσσες - αντίθεση:

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

* Η γλώσσα των palindromes: Ένας αλγόριθμος μπορεί εύκολα να ελέγξει εάν μια δεδομένη συμβολοσειρά είναι η ίδια προς τα εμπρός και προς τα πίσω.

* Η γλώσσα των χορδών που περιέχουν "ABC": Ένας απλός αλγόριθμος μπορεί να σαρώσει μια συμβολοσειρά και να ελέγξει για το υποσύνολο "ABC".

* Η γλώσσα των δυαδικών συμβολοσειρών του μήκους: Ένας αλγόριθμος μπορεί να ελέγξει το μήκος της συμβολοσειράς.

Στην ουσία, η διαφορά βράζει κάτω από το αν ένας αλγόριθμος μπορεί να σχεδιαστεί για να * πάντα * να δώσει μια σωστή απάντηση ναι/όχι σε πεπερασμένο χρόνο. Για μη αποδοτικές γλώσσες, ένας τέτοιος αλγόριθμος είναι αποδεδειγμένα αδύνατο να δημιουργηθεί. Η ύπαρξη ενός τέτοιου αλγορίθμου είναι το καθοριστικό χαρακτηριστικό που διακρίνεται αποφασιστικά από τις μη αποδοτικές γλώσσες.