Είναι η διαφορά μεταξύ των αποφασιστικών και αναγνωρίσιμων γλωσσών στη θεωρητική επιστήμη των υπολογιστών σαφή σε εσάς;

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

* Δαφής γλώσσα (αναδρομική γλώσσα): Μια γλώσσα l είναι αποφασιστική εάν υπάρχει μια μηχανή turing που, για * κάθε * εισροή συμβολοσειρά w, σταματάει και απαντά σωστά "ναι" αν w ∈ L και "όχι" αν w ∉ L. Αυτό σημαίνει ότι το TM πάντα σταματά, ανεξάρτητα από το αν η είσοδος είναι στη γλώσσα ή όχι.

* αναγνωρίσιμη γλώσσα (αναδρομικά απαράδεκτη γλώσσα): Μια γλώσσα l είναι αναγνωρίσιμη αν υπάρχει μια μηχανή turing που, για * κάθε * εισροή συμβολοσειρά w, σταματά και απαντήσεις "ναι" αν w ∈ L. Ωστόσο, αν w ∉ l, το TM μπορεί να σταματήσει και να απαντήσει "όχι" ή μπορεί να τρέξει για πάντα (loop επ 'αόριστον). Το κλειδί είναι ότι * πάντα * δίνει τη σωστή απάντηση ("Ναι") εάν η συμβολοσειρά είναι στη γλώσσα. Επιτρέπεται μόνο να είναι μη-καθοριστική ή να αποτυγχάνει να δώσει μια απάντηση όταν η συμβολοσειρά δεν είναι * στη γλώσσα.

Με απλούστερους όρους:

* Αποδοχές: Το TM δίνει πάντα μια οριστική απάντηση (ναι ή όχι) σε πεπερασμένο χρόνο.

* αναγνωρίσιμο: Το TM δίνει μια απάντηση "ναι" σε πεπερασμένη ώρα εάν η είσοδος είναι στη γλώσσα, αλλά μπορεί να μην δώσει μια απάντηση (με βρόχο για πάντα) εάν η είσοδος δεν είναι στη γλώσσα.

Κάθε αναγνωρίσιμη γλώσσα είναι επίσης αναγνωρίσιμη. Ωστόσο, το αντίστροφο δεν είναι αλήθεια. Υπάρχουν αναγνωρίσιμες γλώσσες που δεν είναι αποφασιστικές. Το πρόβλημα διακοπής είναι ένα κλασικό παράδειγμα μιας γλώσσας που είναι αναγνωρίσιμη αλλά όχι αποφασιστική. Μπορεί να κατασκευαστεί ένα TM που αναγνωρίζει ότι οι χορδές που αντιπροσωπεύουν τις μηχανές τέρματος (προσομοιώνει το μηχάνημα και τις απαντήσεις "ναι" αν σταματήσει), αλλά κανένα TM δεν μπορεί να αποφασίσει εάν ένα αυθαίρετο μηχάνημα Turing θα σταματήσει σε μια δεδομένη είσοδο (επειδή αυτό θα λύσει το ίδιο το πρόβλημα της διακοπής).

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