Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας Ετικέτα: μεγάλη προσθήκη |
Χωρίς σύνοψη επεξεργασίας Ετικέτα: μεγάλη προσθήκη |
||
Γραμμή 243:
Λιγότερο συχνά συναντάται η χρήση της 4-άδας: αυτές αναπαριστούν μια περαιτέρω εξατομίκευση των εντολών Τούρινγκ (Post (1947)), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); για περισσότερα βλ. [[Post–Turing machine]].
===Η "κατάσταση"===
Η λέξη "κατάσταση" που χρησιμοποείται στο πλαίσιο της μηχανής Τούρινγκ μπορεί να είναι πηγή σύγχυσης, μιας και έχει διπλή σημασία. Οι περισσότεροι σχολιαστές μετά τον Τούρινγκ χρησιμοποιούν την "κατάσταση" για να εννοήσουν το όνομα/προσδιορισμό της τρέχουσας εντολής που πρέπει να εκτελεστεί- δηλ. τα περιεχόμενα του μητρώου κατάστασης. Αλλά ο Τούρινγκ (1936) έκανε μια ισχυρή διάκριση μεταξύ μιας καταγραφής αυτού που ονόμαζε "μ-σχηματισμός" της μηχανής, (της εσωτερικής κατάστασής του)και την "κατάσταση εξέλιξης" της μηχανής (ή του ατόμου)μέσω του υπολογισμού- η τρέχουσα κατάσταση του ολικού συστήματος. Αυτό που ο Τούρινγκ ονόμαζε "φόρμουλα κατάστασης" περιλαμβάνει και την τρέχουσα εντολή και ''όλα'' τα σύμβολα στην ταινία:
{{quote|Κατά αυτόν τον τρόπο η κατάσταση εξέλιξης του υπολογισμού σε κάθε στάδιο είναι εντελώς καθορισμένη από το υπόμνημα των εντολών και των συμβόλων στην ταινία. Δηλαδή, η '''κατάσταση του συστήματος''' μπορεί να περιγραφεί από μια απλή έκφραση (ακολουθία συμβόλων) αποτελούμενη από τα σύμβολα στην ταινία ακολουθούμενα από Δ (που υποθέτουμε ότι δεν θα εμφανιστεί αλλού) και έπειτα από το υπόμνημα εντολών. Αυτή η έκφραση ονομάζεται 'φόρμουλα κατάστασης' .|''Undecidable'', σελ.139–140, με έμφαση}}
Νωρίτερα στο έγγραφο του ο Τούρινκγ το προχώρησε περαιτέρω: δίνει ένα παράδειγμα όπου τοποθέτησε ένα σύμβολο από τον τρέχων "μ-σχηματισμό" -η επιγραφή της εντολής- κάτω από το κελί που διαβάζεται , μαζί με όλα τα σύμβολα της ταινίας (''Undecidable'', σελ. 121); αυτό το ονομάζει "ο ''πλήρης σχηματισμός''" (''Undecidable'', σελ. 118). Για να εκτυπώσει τον "πλήρη σχηματισμό" σε μία γραμμή, τοποθετεί την ετικέτα-κατάστασης/μ-σχηματισμό στα ''αριστερά'' από το σύμβολο που διαβάζεται.
Μια παραλλαγή αυτού βλέπουμε στον 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 "κινήσεις"''' (παρμένο από το παράδειγμα "run" στο παρακάτω σχήμα):
:: 1'''A'''1
Αυτό σημαίνει: μετά από τρεις κινήσεις η ταινία έχει ... 000110000 ... πάνω της, η κεφαλή σαρώνει το δεξιότερο 1, και η κατάσταση είναι '''A'''. Τα κενά διαστήματα (σ' αυτήν την περίπτωση αντιπροσωπεύονται με "0") μπορούν να είναι μέρος από την ολική κατάσταση όπως φαίνεται εδώ: '''B'''01; η ταινία έχει ένα μοναδικό 1 πάνω της, αλλά η κεφαλή σαρώνει το "0" ("κενό") στα αριστερά του και η κατάσταση είναι '''B'''.
Η "κατάσταση" στο πλαίσιο της μηχανής Τούρινγκ πρέπει να διευκρινιστεί ως προς τι περιγράφεται: (''i'') η τρέχουσα εντολή, ή (''ii'') η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή, ή (''iii'') η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή τοποθετημένα στα αριστερά ή στα δεξιά από το σύμβολο που διαβάζεται.
Ο βιογράφος του Τούρινγκ Andrew Hodges (1983: 107) σημείωσε και συζήτησε αυτή τη σύγχυση.
===Τα διάγραμμα "κατάστασης" της μηχανής Τούρινγκ===
{|class="wikitable"
|+ Ο πίνακας για τις 3-καταστάσεις του πολυάσχολου "beaver" ("P" = εκτύπωσε/γράψε "1")
|-
! Σύμβολο ταινίας
! colspan="3" | Τρέχουσα κατάσταση A
! colspan="3" | Τρέχουσα κατάσταση B
! colspan="3" | Τρέχουσα κατάσταση C
|-
|
| Κατεγράψε σύμβολο
| Μετακίνησε την ταινία
| Επόμενη κατάσταση
| Κατέγράψε σύμβολο
| Μετακίνησε την ταινία
| Επόμενη κατάσταση
| Κατέγράψε σύμβολο
| Μετακίνησε την ταινία
| Επόμενη κατάσταση
|-
| '''0'''
| P
| R
| '''B'''
| P
| L
| '''A'''
| P
| L
| '''B'''
|-
| '''1'''
| P
| L
| '''C'''
| P
| R
| '''B'''
| P
| R
| '''ΣΤΟΠ'''
|}
[[Image:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|Ο πολυάσχολος "beaver" με τις 3-καταστάσεις της μηχανής Τούρινγκ σε μια[[Finite State Machine|πεπερασμένη παράσταση καταστάσεων]]. Κάθε κύκλος αναπαριστά μια "κατάσταση" του πίνακα-έναν "μ-σχηματισμό" ή "εντολή". Η "διεύθυνση" απο μια μετάβαση κατάστασης φαίνεται από ένα βέλος . Η ετικέτα (δηλ. '''0/P,R''') δίπλα στην εξερχόμενη κατάσταση (στην ουρά του βέλους) προσδιορίζει το σύμβολο που διαβάζεται που επιφέρει μια συγκεκριμένη μετάβαση (δηλ. '''0''') ακολουθούμενη από κάθετο '''/''', ακολουθούμενη απο μεταγενέστερες "συμπεριφορές" της μηχανής , δηλ. "'''P''' '''Ε'''κτύπωσε" έπειτα μετακίνησε την ταινία "'''R''' '''Δ'''εξιά". Δεν υπάρχει γενική αποδεκτή φόρμα. Η σύμβαση φαίνεται μετά τους McClusky (1965), Booth (1967), Hill, και Peterson (1974).]]
Στα δεξιά: ο παραπάνω πίνακας όπως εκφράζεται σαν διάγραμμα "μετάβαση κατάστασης".
Συνήθως μεγάλοι πίνακες είναι καλύτερο να παραμένουν ως πίνακες (Booth, σελ. 74). Προσομοιώνονται ευκολότερα από τον υπολογιστή σε μορφή πίνακα (Booth, σελ. 74). Ωστόσο , ορισμένες έννοιες -π.χ. μηχανές με καταστάσεις "επαναφοράς" και μηχανές με επαναλαμβανόμενα μοτίβα(των Hill και Peterson σελ. 244ff)—μπορούν ευκολότερα να αναγνωριστούν όταν φαίνονται σαν σχήματα.
Το εάν ένα σχήμα αντιπροσωπεύει μια βελτίωση στον πίνακα του πρέπει να αποφασιστεί από τον αναγνώστη για το συγκεκριμένο πλαίσιο. Βλέπε [[Finite state machine]] για περισσότερα.
[[Image:State diagram 3 state busy beaver 4 .JPG|thumbnail|500px|right|Η εξέλιξη του υπολογισμού του πολυάσχολου "beaver" ξεκινάει στην κορυφή και προχωρά προς το κάτω μέρος.]]
Θα έπρεπε να προειδοποιήσουμε τον αναγνώστη ότι τέτοια διαγράμματα αναπαριστούν ένα στιγμιότυπο του πίνακά παγωμένο στο χρόνο , ''όχι'' την πορεία ("τροχιά") ενός υπολογισμού ''διαμέσου'' του χρόνου και/ή του χώρου. Αν και κάθε φορά που η μηχανή πολυάσχολος "beaver" θα "τρέχει" , θα ακολουθεί πάντα την ίδια τροχιά-καταστάσεων, αυτό δεν είναι ισχύει και για το "αντίγραφο" της μηχανής το οποίο μπορεί να εφοδιάζεται με ποικίλες εισερχόμενες "παραμέτρους".
Το διάγραμμα "Εξέλιξη του υπολογισμού" δείχνει την εξέλιξη των καταστάσεων (εντολών) του πολυάσχολου "beaver" 3-καταστάσεων διαμέσου του υπολογισμού του από την αρχή στο τέλος. Στο δεξιό μέρος της εικόνας είναι ο Τούρινγκ "πληρης σχηματισμός" (Kleene "κατάσταση", Hopcroft–Ullman "στιγμιαία περιγραφή") σε κάθε βήμα. Αν η μηχανή έπρεπε να διακοπεί και να καθαριστεί και να αδειάσει τόσο το "μητρώο καταστάσεων" όσο και ολόκληρη η ταινία , αυτοί οι "σχηματισμοί" θα μπορούσαν να χρησιμοποιηθούν για να αναζωπυρωθεί ένας υπολογισμός οπουδήποτε στην εξέλιξη του (από Τούρινγκ (1936) ''Undecidable'' pp. 139–140).
== Αναφορές ==
| |||