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

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

Κατανόηση του τοπίου πρώτα

Πριν από την κατάδυση σε παραδείγματα, ας διευκρινίσουμε τις κατηγορίες:

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

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

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

Παραδείγματα μη αναγνωρίσιμων γλωσσών

Τα πιο συνηθισμένα παραδείγματα αναγνωρίσιμων γλωσσών που δεν είναι αναγνωρίσιμες συχνά περιλαμβάνουν τα συμπληρώματα γνωστών μη αποικοδομήσιμων προβλημάτων.

1. Το συμπλήρωμα του προβλήματος διακοπής (¬HALT):

* Το πρόβλημα διακοπής (HALT): Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανών Turing `⟨m, w⟩` όπου το Turing Machine` m` σταματάει στη συμβολοσειρά εισόδου `w '. (Αυτό είναι αναγνωρίσιμο από το Turing, αλλά όχι * δεν μπορεί να διακριθεί).

* ¬Halt: Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανών Turing `⟨m, w⟩` όπου το Turing Machine` m` δεν έχει * halt on input string `w`.

* Γιατί είναι αναγνωρίσιμο μη-turing: Εάν οι ¬ Halt ήταν αναγνωρίσιμες, τότε το HALT θα ήταν διακοσμητικό (θα μπορούσαμε να προσομοιώσουμε `m` on` w` και αν ο αναγνωριστικός μας για το ¬Halt αποδέχεται, γνωρίζουμε ότι το m` δεν σταματάει, αν απορρίψει, γνωρίζουμε ότι «θα σταματήσει). Αλλά το HALT είναι * αποδεδειγμένο * Ανεξάρτητο. Δεδομένου ότι το HALT είναι αναγνωρίσιμο, αλλά δεν είναι εξαντλητικό, το συμπλήρωμα του, ¬ HALT, πρέπει να είναι μη αναγνωρίσιμο. Εάν η διακοπή ήταν αποφασισμένη τότε και τα δύο και το κομπλιμέντο θα ήταν αναγνωρίσιμο.

2. ):

* Το πρόβλημα αποδοχής (A <υπο -> TM ): Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανών Turing `⟨m, w⟩` όπου το Turing Machine` m` δέχεται συμβολοσειρά εισόδου `w '. (Αυτό είναι αναγνωρίσιμο από τον Turing, αλλά δεν είναι διακοσμητικό).

* ¬ _tm : Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανών Turing `⟨m, w⟩` όπου το Turing Machine` m` δεν * δεν δέχεται συμβολοσειρά εισόδου `w '. «M» μπορεί είτε να απορρίψει είτε να βρόχος.

* Γιατί είναι αναγνωρίσιμο μη-turing: Παρόμοια συλλογιστική όπως και με το ¬alt. Εάν ¬A tm ήταν αναγνωρίσιμες από τον Turing, έπειτα _tm θα ήταν ο Turing-Decidable, αντιφατικά για τη γνωστή μη αποικοδομικότητα ενός _tm .

3. ):

* Το πρόβλημα κενότητας (e tm ): Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανών Turing `⟨m⟩` όπου η γλώσσα που αναγνωρίζεται από το Turing Machine` m` είναι άδειο (δηλαδή, `l (m) =∅`). (Αυτό δεν είναι * αναγνωρίσιμο).

* ¬e tm : Αυτή είναι η γλώσσα που περιέχει όλες τις κωδικοποιήσεις μηχανής Turing `⟨m⟩` όπου η γλώσσα που αναγνωρίζεται από το Turing Machine` m` δεν είναι * άδειο (δηλ. 'L (m) ≠ ∅`).

* Γιατί είναι αναγνωρίσιμο από τον Turing: Ένα μηχάνημα Turing μπορεί να αναγνωρίσει αυτή τη γλώσσα με την προσομοίωση της μηχανής `m` σε όλες τις πιθανές εισόδους μέχρι να δεχθεί το m`.

4.

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

* Θα μπορούσατε να δοκιμάσετε να εκτελέσετε το μηχάνημα σε πολλές διαφορετικές εισόδους, αλλά ποτέ δεν θα είστε βέβαιοι ότι δεν θα σταματήσει σε κάποια άλλη, μη δοκιμασμένη εισροή.

Πώς οι μη αναγνωρίσιμες γλώσσες διαφέρουν

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

* -decidable: Ένα μηχάνημα Turing * πάντα * δίνει μια σωστή απάντηση ("Ναι" ή "όχι") και σταματά.

* αναγνωρίσιμο Turing: Ένα μηχάνημα Turing δίνει μια απάντηση "ναι" εάν η συμβολοσειρά είναι στη γλώσσα, αλλά μπορεί να βρόχο για πάντα εάν η συμβολοσειρά δεν είναι * στη γλώσσα.

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

Διαίσθηση

Σκεφτείτε το έτσι:

* Αποδοχές: Έχετε μια απόλυτα αξιόπιστη δοκιμή που σας δίνει πάντα τη σωστή απάντηση.

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

* μη αναγνωρίσιμο: Δεν μπορείτε καν να δημιουργήσετε μια δοκιμή που θα προσδιορίσει αξιόπιστα τις περιπτώσεις "Ναι". Οποιαδήποτε δοκιμή που καταλήγετε θα είναι λανθασμένη και μπορεί να σας δώσει εσφαλμένα αποτελέσματα.

Σημαντικές επιπτώσεις

Η ύπαρξη μη αναγνωρίσιμων γλωσσών έχει βαθιές επιπτώσεις στην επιστήμη και τα μαθηματικά των υπολογιστών:

* Όρια υπολογισμού: Αποδεικνύει ότι υπάρχουν εγγενείς περιορισμοί σε ό, τι μπορούν να κάνουν οι υπολογιστές, ανεξάρτητα από το πόσο ισχυροί γίνονται.

* Ανεξάρτητα: Υπογραμμίζει την ύπαρξη προβλημάτων που είναι θεμελιωδώς ακατάλληλα - δεν υπάρχει αλγόριθμος που να μπορεί να τα λύσει σε όλες τις περιπτώσεις.

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

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