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

Οι αναγνωρίσιμες γλώσσες του Turing, γνωστές και ως αναδρομικές γλώσσες, έχουν τις ακόλουθες ιδιότητες κλεισίματος:

Ιδιότητες θετικού κλεισίματος (κλειστές κάτω από αυτές τις λειτουργίες):

* Ένωση: Εάν τα L1 και L2 είναι αναγνωρίσιμα από τον Turing, τότε το L1 ∪ L2 είναι επίσης αναγνωρίσιμο. Μπορείτε να προσομοιώσετε και τα δύο μηχανήματα Turing για L1 και L2 παράλληλα. Εάν είτε αποδέχεται, το συνδυασμένο μηχάνημα δέχεται.

* Συνέλευση: Εάν τα L1 και L2 είναι αναγνωρίσιμα από τον Turing, τότε το L1L2 είναι επίσης αναγνωρίσιμο. Αυτό είναι λίγο πιο δύσκολο. Μπορείτε να διαχωρίσετε μη-deterministal τη συμβολοσειρά εισόδου σε δύο μέρη και στη συνέχεια να εκτελέσετε τις μηχανές Turing για L1 και L2 σε αυτά τα μέρη. Εάν και οι δύο αποδοθούν, τότε το συνδυασμένο μηχάνημα δέχεται.

* Kleene Star: Εάν το L είναι αναγνωρίσιμο, τότε ο L* είναι επίσης αναγνωρίσιμος από τον Turing. Παρόμοια με τη συγκόλληση, μπορείτε να διαχωρίσετε μη-καθοριστικά τη συμβολοσειρά εισόδου σε μηδέν ή περισσότερα μέρη και να δοκιμάσετε εάν κάθε τμήμα βρίσκεται στο L.

* αντιστροφή: Εάν το L είναι αναγνωρίσιμο, τότε L r (Η αντιστροφή του L) είναι επίσης αναγνωρίσιμη από τον Turing. Ένα μηχάνημα Turing μπορεί εύκολα να αντιστρέψει τη συμβολοσειρά εισόδου και στη συνέχεια να εκτελέσει το μηχάνημα Turing για L στη συμβολοσειρά αντιστροφής.

Αρνητικές ιδιότητες κλεισίματος (δεν είναι κλειστές κάτω από αυτές τις λειτουργίες):

* διασταύρωση: Οι αναγνωρίσιμες γλώσσες Turing είναι * όχι * κλειστές κάτω από τη διασταύρωση. Αυτό σημαίνει ότι εάν οι L1 και L2 είναι αναγνωρίσιμες, το L1 ∩ L2 δεν είναι αναγκαστικά * turing-recognizable. Ωστόσο, εάν*και οι δύο*L1 και L2 είναι δεκτές*, τότε το L1 ∩ L2 είναι μεταβλητό (και επομένως και το αναγνωρίσιμο του Turing).

* Συμπλήρωση: Οι αναγνωρίσιμες γλώσσες Turing είναι * όχι * κλειστές υπό συμπλήρωση. Εάν το L είναι αναγνωρίσιμο, το ¬l (το συμπλήρωμα του L) δεν είναι απαραίτητα * turing-recognizable.

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

Συνοπτικά:

| Λειτουργία | Κλειστό; | Επεξήγηση |

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

| Ένωση | Ναι | Προσομοιώστε και τα δύο μηχανήματα παράλληλα, αποδεχτείτε εάν αποδέχεστε. |

| Συμπύκνωση | Ναι | Μη-καθοριστικά διαχωρισμένη είσοδο και δοκιμάστε κάθε τμήμα. |

| Kleene Star | Ναι | Μη-καθοριστικά διαχωρισμένη είσοδο σε πολλαπλά μέρη και δοκιμάστε κάθε τμήμα. |

| Αναστροφή | Ναι | Αντιστρέψτε την είσοδο και εκτελέστε το TM. |

| Διασταύρωση | Όχι | Μπορεί να αποτύχει. Απαιτεί και οι δύο γλώσσες να είναι αποφασιστικές για το κλείσιμο. |

| Συμπλήρωση | Όχι | Το συμπλήρωμα μιας γλώσσας που μπορεί να αναγνωρίσει το Turing δεν είναι πάντα αναγνωρίσιμο. |

Γιατί η διασταύρωση και η συμπλήρωση δεν είναι κλειστά;

Το ζήτημα προέρχεται από το γεγονός ότι οι μηχανές Turing για αναγνωρίσιμες γλώσσες μπορούν να βρουν για πάντα.

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

* Συμπλήρωση: Ένα μηχάνημα Turing για L είτε δέχεται, απορρίπτει ή βρόχους σε μια είσοδο. Για να αναγνωρίσετε το συμπλήρωμα ¬l, πρέπει να απορρίψετε * όλες τις χορδές που έγιναν αποδεκτές από L και * αποδέχονται * όλες οι χορδές που απορρίπτονται * ή looped στο * από L. Δεν μπορείτε να διακρίνετε αξιόπιστα μεταξύ μιας μηχανής που * θα απορρίψει τελικά και ένα που θα βρόχο για πάντα. Θα πρέπει να είστε σε θέση να γνωρίζετε με κάποιο τρόπο * όταν * ένα μηχάνημα πρόκειται να βυθιστεί, το οποίο είναι γενικά αδύνατο.

Παράδειγμα που επιδεικνύει μη κλιμάκωση υπό συμπλήρωση:

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