Διαφορά μεταξύ των αναθεωρήσεων του «Μηχανή Τούρινγκ»

καμία σύνοψη επεξεργασίας
Η Μηχανή Τούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών όπως "στην κατάσταση 42, εάν το σύμβολο που εμφανίζεται είναι το 0, τότε γράψε 1, ενώ εάν το σύμβολο που εμφανίζεται είναι το 1, πήγαινε στην κατάσταση 17 και στην κατάσταση 17, εάν το σύμβολο που εμφανίζεται είναι 0, γράψε 1 και πήγαινε στην κατάσταση 6" κλπ. Στο πρωτότυπο άρθρο ("On computable numbers, with an application to the [[Entscheidungsproblem]]", βλέπε επίσης [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), ο Τούρινγκ δεν φαντάζεται έναν μηχανισμό, αλλά ένα άτομο το οποίο αποκαλεί ο "υπολογιστής", το οποίο εκτελεί δουλικά αυτούς τους ντετερμινιστικούς μηχανικούς κανόνες(ή όπως το θέτει ο Τούρινγκ με έναν ξεκαρφωτο τρόπο).
 
 
[[Image:Turing machine 2a.svg|thumb|right|300px|Η κεφαλή βρίσκεται πάντα πάνω από ένα συγκεκριμένο τετράγωνο της ταινίας. Μόνο ένα πεπερασμένο πλήθος τετραγώνων εμφανίζεται. Η εντολή που εκτελείται (q<sub>4</sub>) φαίνεται πάνω από το τετράγωνο που σκανάρεται.(Drawing after Kleene (1952) p.375.)]]
 
[[Image:Turing machine 2b.svg|thumb|right|300px|Εδώ, η εσωτερική κατάσταση (q<sub>1</sub>) φαίνεται μέσα στην κεφαλή και η εικονογράφηση περιγράφει την περίπτωση που η ταινία είναι άπειρη και γεμάτη με "0", το σύμβολο που αντιστοιχεί στο κενό σύμβολο. Η πλήρης κατάσταση του συστήματος (η πλήρης ....) αποτελείται από την εσωτερική κατάσταση, τα μη-κενά σύμβολα στην ταινία ( σε αυτήν την περίπτωση "11Β"), και την θέση της κεφαλής σε σχέση με όλα τα σύμβολα, περιλαμβανομένων και των κενόν, δηλαδή "011Β". (Drawing after Minsky (1967) p. 121).]]
# Μία '''κεφαλή''' που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά. Σε μερικά μοντέλα κινείται μόνο η κεφαλή, ενώ η ταινία παραμένει σταθερή.
#Ένα '''μητρώο καταστάσεων''' που αποθηκεύει μία κατάσταση της Μηχανής Τουρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική ''αρχική'' κατάσταση με την οποία ξεκινά το μητρώο. Αυτές οι καταστάσεις, γράφει ο Τούρινγκ, αντικαθιστούν την "πνευματική κατάσταση" στην οποία αρχικά θα ήταν το άτομο που θα έκανε τους υπολογισμούς.
# Ένας πεπερασμένος '''πίνακας''' (ενίοτε ονομαζόμενος ως '''διαδραστικός πίνακας''' ή '''συνάρτηση μετάβασης''') από οδηγίες (συνήθως πενταπλές [5-tuples] : q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, αλλά μερικές φορές τετραπλές [4-tuples] όπου, δεδομένης της κατάστασης (q<sub>i</sub>) στην όποια βρίσκεται αυτή τη στιγμή η μηχανή, ''και'' το ''σύμβολο'' (a<sub>j</sub>) που διαβάζεται στην ταινία (το σύμβολο που βρίσκεται εκείνη τη στιγμή κάτω από την κεφαλή) ορίζει στη μηχανή να κάνει τα ακόλουθα σε σειρά (για τα πενταπλά μοντέλα):
 
*Είτε απαλείφει , ή καταγράφει ένα σύμβολο (αντικαθιστώντας το a<sub>j</sub> με το a<sub>j1</sub>), ''και έπειτα''
*Μετακινεί την κεφαλή (η οποία περιγράφεται απο d<sub>k</sub> και μπορεί να έχει τιμές : 'L' για ένα βήμα αριστερά ''ή'' 'R' για ένα βήμα δεξιά ''ή'' 'N' για να μείνει στο ίδιο μέρος), ''και έπειτα''
*Θεωρεί την ίδια ή μια ''καινούργια κατάσταση'' όπως ορίζεται ( πηγαίνει στην κατάσταση q<sub>i1</sub>).
Στο τετραπλό μοντέλο , η απαλοιφή ή η καταγραφή ενός συμβόλου (a<sub>j1</sub>) και η μετακίνηση της κεφαλής αριστερά ή δεξιά (d<sub>k</sub>) καθορίζονται ως ξεχωριστές εντολές. Συγκεκριμένα , ο πίνακας λέει στη μηχανή (ia) να διαγράψει ή να καταγράψει ένα σύμβολο ''ή'' (ib) να κινήσει την κεφαλή αριστερά ή δεξιά , ''και έπειτα'' (ii) να θεωρήσει την ίδια ή καινούργια κατάσταση όπως ορίζεται , άλλα όχι και τις 2 ενέργειες ia) , ib), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχων συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.
 
 
14

επεξεργασίες