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

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε

Ενδογραμμικά

Έκδοση από την 20:25, 15 Ιουνίου 2014

Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή του η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε αλγορίθμου, και ειναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας κεντρικής μονάδας επεξεργασίας στο εσωτερικό του υπολογιστή.

Η μηχανή του Τούρινγκ εφευρέθηκε το 1936 απο τον Άλαν Τούρινγκ.^[1] Η μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.

Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:

....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της ειναι εν μέρει αποφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της.

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

Άτυπη Περιγραφή

Η Μηχανή Τούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών όπως "στην κατάσταση 42, εάν το σύμβολο που εμφανίζεται είναι το 0, τότε γράψε 1, ενώ εάν το σύμβολο που εμφανίζεται είναι το 1, πήγαινε στην κατάσταση 17 και στην κατάσταση 17, εάν το σύμβολο που εμφανίζεται είναι 0, γράψε 1 και πήγαινε στην κατάσταση 6" κλπ. Στο πρωτότυπο άρθρο ("On computable numbers, with an application to the Entscheidungsproblem", βλέπε επίσης references below), ο Τούρινγκ δεν φαντάζεται έναν μηχανισμό, αλλά ένα άτομο το οποίο αποκαλεί ο "υπολογιστής", το οποίο εκτελεί δουλικά αυτούς τους ντετερμινιστικούς μηχανικούς κανόνες(ή όπως το θέτει ο Τούρινγκ με έναν ξεκαρφωτο τρόπο).

Πιο συγκεκριμένα, μια Μηχανή Τούρινγκ αποτελείται από:

Μία ταινία που χωρίζεται σε κελιά, το ένα δίπλα στο άλλο. Κάθε κελί περιέχει ένα σύμβολο από ένα πεπερασμένο αλφάβητο. Το αλφάβητο περιέχει ένα ειδικό κενό σύμβολο (το οποίο εδώ συμβολίζουμε με "0") και ένα ή παραπάνω άλλα σύμβολα. Υποθέτουμε πώς αυτή η ταινία είναι απείρως επεκτάσιμη προς τα αριστερά και προς τα δεξιά, δηλαδή μία μηχανή Τούρινγκ είναι πάντα προμηθευμένη με όση ταινία της χρειάζεται για τους υπολογισμούς. Κελιά τα οποία δεν έχουν συμπληρωθεί, υποθέτουμε πως είναι εξοπλισμένα με το κενό γράμμα. Σε κάποια μοντέλα, η ταινία έχει αριστερό άκρο, το οποίο είναι εξοπλισμένο με ένα ειδικό σύμβολο, όμως είναι απείρως επεκτάσιμη προς τα δεξιά.
Μία κεφαλή που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά. Σε μερικά μοντέλα κινείται μόνο η κεφαλή, ενώ η ταινία παραμένει σταθερή.
Ένα μητρώο καταστάσεων που αποθηκεύει μία κατάσταση της Μηχανής Τουρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική αρχική κατάσταση με την οποία ξεκινά το μητρώο. Αυτές οι καταστάσεις, γράφει ο Τούρινγκ, αντικαθιστούν την "πνευματική κατάσταση" στην οποία αρχικά θα ήταν το άτομο που θα έκανε τους υπολογισμούς.
Ένας πεπερασμένος πίνακας (ενίοτε ονομαζόμενος ως διαδραστικός πίνακας ή συνάρτηση μετάβασης) από οδηγίες (συνήθως πενταπλές [5-tuples] : q_ia_j→q_i1a_j1d_k, αλλά μερικές φορές τετραπλές [4-tuples] όπου, δεδομένης της κατάστασης (q_i) στην όποια βρίσκεται αυτή τη στιγμή η μηχανή, και το σύμβολο (a_j) που διαβάζεται στην ταινία (το σύμβολο που βρίσκεται εκείνη τη στιγμή κάτω από την κεφαλή) ορίζει στη μηχανή να κάνει τα ακόλουθα σε σειρά (για τα πενταπλά μοντέλα):

Είτε απαλείφει , ή καταγράφει ένα σύμβολο (αντικαθιστώντας το a_j με το a_j1), και έπειτα
Μετακινεί την κεφαλή (η οποία περιγράφεται απο d_k και μπορεί να έχει τιμές : 'L' για ένα βήμα αριστερά ή 'R' για ένα βήμα δεξιά ή 'N' για να μείνει στο ίδιο μέρος), και έπειτα
Θεωρεί την ίδια ή μια καινούργια κατάσταση όπως ορίζεται ( πηγαίνει στην κατάσταση q_i1).

Στο τετραπλό μοντέλο , η απαλοιφή ή η καταγραφή ενός συμβόλου (a_j1) και η μετακίνηση της κεφαλής αριστερά ή δεξιά (d_k) καθορίζονται ως ξεχωριστές εντολές. Συγκεκριμένα , ο πίνακας λέει στη μηχανή (ia) να διαγράψει ή να καταγράψει ένα σύμβολο ή (ib) να κινήσει την κεφαλή αριστερά ή δεξιά , και έπειτα (ii) να θεωρήσει την ίδια ή καινούργια κατάσταση όπως ορίζεται , άλλα όχι και τις 2 ενέργειες ia) , ib), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχων συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.

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

Ορισμοί

Οι Χόπκροφτ και Ούλμαν^[2] (σελ. 148) ορίζουν μια μηχανή Τούρινγκ ως την επτάδα $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},B,F)$ , όπου

$Q$ είναι το πεπερασμένο σύνολο καταστάσεων,
$\Gamma$ είναι το πεπερασμένο σύνολο των επιτρεπτών συμβόλων της ταινίας,
$B\in \Gamma$ είναι το κενό,
$\Sigma$ , ένα υποσύνολο του $\Gamma$ εκτός του $B$ είναι το σύνολο των συμβόλων εισόδου,
$\delta$ είναι η συνάρτηση της επόμενης κίνησης, μια αντιστοιχία από το $Q\times \Gamma$ στο $Q\times \Gamma \times \{L,R\}$ . Η συνάρτηση $\delta$ μπορεί να μην ορίζεται για όλα τα ορίσματά της,
$q_{0}\in Q$ είναι η αρχική κατάσταση,
$F\subseteq Q$ είναι το σύνολο των τελικών καταστάσεων (final states).

Στη βιβλιογραφία έχουν εμφανιστεί διάφοροι ορισμοί λίγο διαφορετικοί μεταξύ τους, συνήθως για να κάνουν την εξήγηση ή τις αποδείξεις πιο απλές, αλλά πάντα η μηχανή που ορίζεται είναι το ίδιο ισχυρή υπολογιστικά. Για παράδειγμα, οι Λιούις και Παπαδημητρίου ^[3] (σελ. 181) ορίζουν τη μηχανή Τούρινγκ ως την πεντάδα $(K,\Sigma ,\delta ,s,H)$ , όπου

$K$ είναι ένα πεπερασμένο σύνολο καταστάσεων,
$\Sigma$ είναι ένα αλφάβητο, που περιέχει το κενό σύνολο $\sqcup$ και το σύμβολο αριστερού τέλους $\triangleright$ , αλλά όχι τα σύμβολα $\leftarrow$ και $\rightarrow$ ,
$s\in K$ είναι η αρχική κατάσταση,
$H\subseteq K$ είναι το σύνολο των τελικών καταστάσεων (halting states),
$\delta$ , η συνάρτηση μεταφοράς, είναι μια συνάρτηση από το $(K-H)\times \Sigma$ στο $K\times (\Sigma \cup \{\leftarrow ,\rightarrow \})$ τέτοια ώστε

για κάθε $q\in K-H$ , αν $\delta (q,\triangleright )=(p,b)$ , τότε $b=\rightarrow$
για κάθε $q\in K-H$ και $\alpha \in \Sigma$ , αν $\delta (q,\alpha )=(p,b)$ , τότε $b\neq \triangleright$ .

Αναφορές

↑ Η ιδέα ήρθε σ 'αυτόν στα μέσα του 1935 μετά από μια ερώτηση που έθεσε ο Μ. HA Newman στις διαλέξεις του: "Υπήρχε μια συγκεκριμένη μέθοδο, ή όπως το έθεσε Newman, μια μηχανική διαδικασία', η οποία θα μπορούσε να εφαρμοστεί σε μια μαθηματική δήλωση, η οποία θα απαντούσε αν ήταν αποδείξιμη "
↑ John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages and computation, 1979, Addison-Wesley, Reading, Massachusetts
↑ Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Second edition, 1998, Prentice-Hall, Upper Saddle River, New Jersey

Εξωτερικοί σύνδεσμοι

Commons logo

Τα Wikimedia Commons έχουν πολυμέσα σχετικά με το θέμα
Μηχανή Τούρινγκ

Υλοποίηση μηχανής Τούρινγκ

Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Turing machine της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 4.0. (ιστορικό/συντάκτες).

Αυτό το λήμμα σχετικά με την Πληροφορική χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το.

[1] Η ιδέα ήρθε σ 'αυτόν στα μέσα του 1935 μετά από μια ερώτηση που έθεσε ο Μ. HA Newman στις διαλέξεις του: "Υπήρχε μια συγκεκριμένη μέθοδο, ή όπως το έθεσε Newman, μια μηχανική διαδικασία', η οποία θα μπορούσε να εφαρμοστεί σε μια μαθηματική δήλωση, η οποία θα απαντούσε αν ήταν αποδείξιμη "

[2] John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages and computation, 1979, Addison-Wesley, Reading, Massachusetts

[3] Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Second edition, 1998, Prentice-Hall, Upper Saddle River, New Jersey

[1]

[2]

[3]

@@ Γραμμή 17: / Γραμμή 17: @@
 Η Μηχανή Τούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών  όπως "στην κατάσταση 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).]]
@@ Γραμμή 26: / Γραμμή 24: @@
 # Μία '''κεφαλή''' που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά. Σε μερικά μοντέλα κινείται μόνο η κεφαλή, ενώ η ταινία παραμένει σταθερή.
 #Ένα '''μητρώο καταστάσεων''' που αποθηκεύει μία κατάσταση της Μηχανής Τουρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική ''αρχική'' κατάσταση με την οποία ξεκινά το μητρώο. Αυτές οι καταστάσεις, γράφει ο Τούρινγκ, αντικαθιστούν την "πνευματική κατάσταση" στην οποία αρχικά θα ήταν το άτομο που θα έκανε τους υπολογισμούς.
+# Ένας πεπερασμένος '''πίνακας''' (ενίοτε ονομαζόμενος ως '''διαδραστικός πίνακας''' ή '''συνάρτηση μετάβασης''') από οδηγίες (συνήθως πενταπλές [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), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχων συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.