Η Καθολική μηχανή Turing είναι μια μηχανή που η περιγραφή και η κωδικοποίηση της αλλά και ο χειρισμός της είναι ακριβώς ίδιος με μια μηχανή Turing, με την διαφορά ότι η καθολική μηχανή μπορεί να διερμηνεύει άλλες απλές μηχανές Turing ακόμα και τον εαυτό της.
Με άλλα λόγια, η καθολική μηχανή Turing κατά την διερμήνευση μιας οποιαδήποτε μηχανής Turing, δίνει τα ίδια αποτελέσματα με αυτή. Δηλαδή η καθολική μηχανή "τερματίζει" εάν και μόνο εάν και η μηχανή Turing τερματίσει.
Πολλές φορές κατά τη φάση ανάπτυξης και δοκιμών ενός νέου προγράμματος αναγκαζόμαστε να διακόψουμε την εκτέλεσή του γιατί το πρόγραμμά μας δείχνει να έχει "κολλήσει" σε κάποιο σημείο. Θα ήταν χρήσιμο να είχαμε μια μέθοδο, έναν αλγόριθμο, ένα άλλο πρόγραμμα, που να μας έλεγε εάν υπάρχει περίπτωση εισόδου που το πρόγραμμά μας θα "κολλήσει".
Διαβάστε:Μπορώ να βγω από Endless Loop;
Γενικότερα, θα μας ήταν απείρως πιο χρήσιμο κάποιο πρόγραμμα που θα μας έλεγε εάν το πρόγραμμά μας συμπεριφέρεται σύμφωνα με τις προδιαγραφές του. Δυστυχώς και στις δύο αυτές περιπτώσεις αποδεδειγμένα δεν υπάρχει γενική λύση. Η απόδειξη βασίζεται στο ότι το κατά πολύ απλούστερο πρόβλημα του τερματισμού αποδεικνύεται μη επιλύσιμο.
Σε ορολογία προγραμμάτων το πρόβλημα του τερματισμού είναι εάν κάποιο πρόγραμμα Ρ τερματίζει ή όχι με δοθείσα είσοδο X. Σε ορολογία αλγορίθμων το πρόβλημα του τερματισμού είναι εάν κάποιος αλγόριθμος τερματίζει ή όχι για δοθείσα είσοδο.
Στην ορολογία μηχανών Turing το πρόβλημα του τερματισμού ορίζεται τυπικά ως εξής:
Πρόβλημα τερματισμού: Τερματίζει ή όχι δοθείσα μηχανή Turing Μ με
δοθείσα είσοδο w;
Πολύ πιθανόν για κάποιο συγκεκριμένο πρόγραμμα, αλγόριθμο ή μηχανή Turing και για συγκεκριμένη είσοδο να μπορεί κανείς να αποδείξει ότι το πρόβλημα του τερματισμού έχει λύση. Το πρόβλημα του τερματισμού αναφέρεται στη γενική περίπτωση, δηλαδή για οποιαδήποτε δοθείσα μηχανή Turing και οποιαδήποτε δοθείσα είσοδο.
Οι παρακάτω "προτάσεις" αποτελούν μια σειρά από μη επιλύσιμα προβλήματα για μηχανές Turing ανάγονται στο πρόβλημα του Τερματισμού.
1) Δοθείσας μιας μηχανής Turing Μ και εισόδου w, αποδέχεται η Μ την είσοδο w;
2) Υπάρχει συγκεκριμένη μηχανής Turing για την οποία το πρόβλημα του τερματισμού είναι επιλύσιμο;
3) Δοθείσας μιας μηχανής Turing Μ, αποδέχεται η Μ την κενή συμβολοσειρά;
4) Δοθείσας μιας μηχανής Turing Μ, υπάρχει κάποια είσοδος την οποία η Μ αποδέχεται;
5) Δοθείσας μιας μηχανής Turing Μ, αποδέχεται η Μ κάθε είσοδο;
6) Δεδομένων μηχανών Turing M1 και Μ2, αποδέχονται αυτές την ίδια γλώσσα;
7) Δοθείσας μιας μηχανής Turing Μ,η γλώσσα L(M) που αποδέχεται η Μ είναι κανονική ;
8) Δοθείσας μιας μηχανής Turing Μ,η γλώσσα L(M) που αποδέχεται η Μ είναι ελεύθερη συμφραζομένων;
9) Δοθείσας μιας μηχανής Turing Μ,η γλώσσα L(M) που αποδέχεται η Μ είναι Turing αποφασίσιμη (αναδρομική);
Δημοσίευση σχολίου