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

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

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

Παραδείγματα γλωσσών που μπορούν να αναγνωρίσουν το Turing:

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

* Η γλώσσα όλων των αληθινών δηλώσεων στην αριθμητική πρώτης τάξης: Το θεώρημα πληρότητας του Gödel δείχνει ότι μπορεί να αποδειχθεί κάθε αληθινή δήλωση. Ένα μηχάνημα Turing μπορεί συστηματικά να απαριθμήσει όλες τις πιθανές αποδείξεις και να αποδεχθεί μια δήλωση εάν βρεθεί μια απόδειξη. Ωστόσο, εάν μια δήλωση είναι ψευδής, το μηχάνημα δεν θα σταματήσει ποτέ.

* Η γλώσσα όλων των γραμματικών χωρίς περιβάλλοντα που παράγουν τουλάχιστον μία σειρά μήκους 10: Μια μηχανή Turing μπορεί συστηματικά να παράγει όλες τις χορδές ενός δεδομένου CFG και να ελέγξει το μήκος τους. Εάν βρίσκει ένα μήκος 10, δέχεται. Εάν το CFG δεν παράγει τέτοια συμβολοσειρά, το μηχάνημα μπορεί να τρέξει επ 'αόριστον προσπαθεί να βρει ένα.

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

Πώς διαφέρουν από άλλους τύπους γλωσσών:

Η βασική διαφορά έγκειται στη συμπεριφορά διακοπής:

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

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

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

Συνοπτικά:

| Τάξη γλώσσας | Συμπεριφορά | Παράδειγμα |

| ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

| Διευκόλυνση | Πάντα σταματάει, αποφασίζει σωστά τη συμμετοχή | Τακτικές γλώσσες, γλώσσες χωρίς περιβάλλοντα (με περιορισμούς)

| Turing-recognizable | Σταματά και δέχεται χορδές στη γλώσσα, μπορεί να βυθιστεί διαφορετικά | Γλώσσα των μηχανών Turing που σταματούν στην κενή συμβολοσειρά |

| Μη-turing-recognizable | Κανένα μηχάνημα Turing δεν μπορεί να το αναγνωρίσει | Συμπλήρωση του προβλήματος διακοπής |

Η ιεραρχία είναι:ο Turing-Decidable ⊂ turing-recognizable ⊂ όλες οι γλώσσες. Η ένταξη είναι αυστηρή. Υπάρχουν αναγνωρίσιμες γλώσσες που δεν είναι αποφασιστικές. Και υπάρχουν πολλές γλώσσες πέρα από τις αναγνωρίσιμες.