Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας Ετικέτα: μεγάλη προσθήκη |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 253:
Μια παραλλαγή αυτού βλέπουμε στον Kleene (1952) όπου ο [[Stephen Cole Kleene|Kleene]] δείχνει πώς να γράψεις [[Gödel number]] από μια "κατάσταση" μηχανής: τοποθετεί το σύμβολο του q<sub>4</sub> "μ-σχηματισμού" πάνω από το κελί που διαβάζεται περίπου στο κέντρο από τα 6 μη-κενά κελιά στην ταινία (βλέπε την εικόνα της Τούρινγκ-ταινίας σ 'αυτό το άρθρο) και το τοποθετεί στα ''δεξιά'' από το κελί που διαβάζεται. Αλλά ο Kleene αναφέρεται στο "q<sub>4</sub>" ώς την "κατάσταση μηχανής" (Kleene, σελ. 374-375). Οι Hopcroft και Ullman καλούν αυτή τη μίξη η "στιγμιαία περιγραφή" και ακολουθούν τη συνήθεια του Τούρινγκ να τοποθετεί την "τρέχουσα κατάσταση" (επιγραφή της εντολής , μ-σχηματισμός) στα ''αριστερά'' του συμβόλου που διαβάζεται (σελ. 149).
'''Παράδειγμα: η ολική κατάσταση του πολυάσχολου beaver αποτελούμενου από 3-καταστάσεις 2-σύμβολα μετά από 3 "κινήσεις"''' (
:: 1'''A'''1
Αυτό σημαίνει: μετά από τρεις κινήσεις η ταινία έχει ... 000110000 ... πάνω της, η κεφαλή σαρώνει το δεξιότερο 1, και η κατάσταση είναι '''A'''. Τα κενά διαστήματα (σ' αυτήν την περίπτωση αντιπροσωπεύονται με "0") μπορούν να είναι μέρος από την ολική κατάσταση όπως φαίνεται εδώ: '''B'''01; η ταινία έχει ένα μοναδικό 1 πάνω της, αλλά η κεφαλή σαρώνει το "0" ("κενό") στα αριστερά του και η κατάσταση είναι '''B'''.
| |||