.

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

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

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

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

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

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

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

Εδώ, η εσωτερική κατάσταση (q1) φαίνεται μέσα στην κεφαλή και η εικονογράφηση περιγράφει την περίπτωση που η ταινία είναι άπειρη και γεμάτη με "0", το σύμβολο που αντιστοιχεί στο κενό σύμβολο. Η πλήρης κατάσταση του συστήματος (η πλήρης ....) αποτελείται από την εσωτερική κατάσταση, τα μη-κενά σύμβολα στην ταινία ( σε αυτήν την περίπτωση "11Β"), και την θέση της κεφαλής σε σχέση με όλα τα σύμβολα, περιλαμβανομένων και των κενόν, δηλαδή "011Β". (Drawing after Minsky (1967) p. 121).

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

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

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

Στο τετραπλό μοντέλο , η απαλοιφή ή η καταγραφή ενός συμβόλου (aj1) και η μετακίνηση της κεφαλής αριστερά ή δεξιά (dk) καθορίζονται ως ξεχωριστές εντολές. Συγκεκριμένα , ο πίνακας λέει στη μηχανή (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. \)

Επιπλέον πληροφορίες που απαιτούνται για να υλοποιηθούν ή να εφαρμοστούν οι μηχανές Τιούρινγκ

Σύμφωνα με τα λόγια του van Emde Boas (1990) σελ.6: "Το συνολοθεωρητικό αντικείμενο [η κανονική επταπλή περιγραφή που μοιάζει με αυτήν που περιγράφηκε πριν] μας παρέχει μόνο μερικές πληροφορίες σχετικά με το πώς λειτουργεί η μηχανή και πώς θα μοιάζουν οι υπολογισμοί της."

Για παράδειγμα,

Θα πρέπει να υπάρχουν υπερβολικά πολλές αποφάσεις σχετικά με το πως τα σύμβολα μοιάζουν πραγματικά, και υπάρχουν πολλοί λανθασμένοι τρόποι για να διαβαστούν και να καταγραφούν τα σύμβολα απείρως.
Οι εντολές αριστερό shift και δεξί shift μπορούν να μετακινούν την κεφαλή κατά μήκος της ταινίας, όμως όταν χτίζεται μια μηχανή Τιούρινγκ είναι πρακτικά πιο χρήσιμο να κάνουμε την ταινία να μετακινείται προς τα μπρος και προς τα πίσω, κάτω από τη κεφαλή.
Η ταινία μπορεί να είναι πεπερασμένου μήκους και αυτόματα να επεκτείνεται με κελιά που περιέχουν το κενό σύμβολο όπου χρειάζεται (κάτι που προσεγγίζει τον μαθηματικό ορισμό), όμως είναι πιο συνηθισμένο να σκεφτόμαστε πως επεκτείνεται απείρως και προς τα δυο άκρα, και πως είναι εξ'αρχής γεμάτο με το κενό σύμβολο, με εξαίρεση κάποια συγκεκριμένα δοσμένα πεπερασμένα φράγματα πάνω από τα οποία βρίσκεται η κεφαλή. (Αυτό φυσικά, δεν είναι εφαρμόσιμο στην πραγματικότητα.) Η ταινία δεν μπορεί να έχει σταθερό μήκος, μιας και κάτι τέτοιο δεν θα ανταποκρίνεται στον δοσμένο ορισμό και θα περιόριζε σημαντικά το πλήθος των υπολογισμών που μπορεί να κάνει η μηχανή, σε όσους μπορεί να κάνει και ένα linear bounded automaton

Εναλλακτικοί Ορισμοί

Οι ορισμοί στην λογοτεχνία μερικές φορές διαφέρουν ελαφρώς, ώστε να είναι οι προτάσεις και οι αποδείξεις απλούστερες ή πιο ξεκάθαρες, αλλά αυτό γίνεται πάντα με τέτοιο τρόπο ώστε η προκύπτουσα μηχανή να έχει την ίδια υπολογιστική δύναμη. Για παράδειγμα, αλλάζοντας το σύνολο \(\{L,R\} \) με το \(\{L,R,N\} \), όπου N ("Καμία" ή "Χωρίς-Εκτέλεση") θα επέτρεπε στη μηχανή να παραμείνει στο ίδιο κελί της ταινίας, αντί να κινείται δεξιά και αριστερά, δεν αυξάνει την υπολογιστική δύναμη της μηχανής.

Η πιο κοινή σύμβαση είναι να αναπαριστάται κάθε "εντολή Τιούρινγκ" σε έναν "πίνακα Τιούρινγκ" με μία από τις εννιά πενταπλότητες, όπως η σύμβαση των Τιούρινγκ/Davis (Τιούρινγκ (1936) στο "Undecideable", σελ.126-127 και Davis(2000), σελ.152):

(ορισμός 1): (qi, Sj, Sk/E/N, L/R/N, qm)

( παρούσα κατάσταση qi , σύμβολο που διαβάζεταιSj , σύμβολο που εκτυπώνεται Sk/διαγραφή E/τίποτα N , μετακίνηση της ταινίας ένα κελί αριστερά L/δεξιά R/κανένα N , νέα κατάσταση qm )

Άλλοι συγγραφείς (Minsky (1967) σελ. 119, Hopcroft and Ullman (1979) σελ. 158, Stone (1972) σελ. 9) υιοθετούν μια διαφορετική σύμβαση, με μια νέα κατάσταση qm η οποία κατaγράφεται αμέσως μετά το σύμβολο που διαβάζεται Sj:

(ορισμός 2): (qi, Sj, qm, Sk/E/N, L/R/N)

( παρούσα κατάσταση qi , σύμβολο που διαβάζεται Sj , νέα κατάσταση qm , εκτύπωση συμβόλουSk/διαγραφή E/τίποτα N , μετακίνηση της ταινίας κατά ένα κελί αριστερά L/δεξιά R/καθόλου N )

Για το υπόλοιπο του άρθρου, θα χρησιμοποιείται ο "ορισμός 1" (ορισμός των Τιούρινγκ/Davis)

Παράδειγμα: πίνακας καταστάσεων για τον "πολυάσχολο beaver" με 3 καταστάσεις και 2 σύμβολα, που μετατρέπεται σε 5-απλό σύστημα.
Παρούσα Κατάσταση	Σύμβολο που διαβάζεται	Σύμβολο που εκτυπώνεται	Κίνηση της ταινίας	Τελική (δηλ. επόμενη) κατάσταση	5-άδα
A	0	1	R	B	(A, 0, 1, R, B)
A	1	1	L	C	(A, 1, 1, L, C)
B	0	1	L	A	(B, 0, 1, L, A)
B	1	1	R	B	(B, 1, 1, R, B)
C	0	1	L	B	(C, 0, 1, L, B)
C	1	1	N	H	(C, 1, 1, N, H)

Στον επόμενο πίνακα, η αυθεντική μηχανή του Τιούρινγκ επέτρεπε μόνο τις τρεις πρώτες γραμμές να εμφανίζονται, τις οποίες ονόμαζε Ν1, Ν2, Ν3 (βλ. Τιούρινγκ στο "Undecideable", σελ. 126). Επέτρεπε την διαγραφή του "κελιού που διαβάζεται", ονομάζοντας το 0-νικό σύμβολο S0 = "διαγραφέα" ή "κενό", κλπ, όμως, δεν επέτρεπε να μην εκτυπωθεί, και έτσι η κάθε γραμμή-εντολή περιλαμβάνει "εκτύπωση συμβόλου Sk" ή "διαγραφή" (βλ. παραπομπή 12 στο Post (1947), Undecideable σελ. 300). Οι συντομεύσεις είναι του Τιούρινγκ("Undecideable", σελ. 119). Ως επακόλουθο, του πρωτότυπου άρθρου του Τιούρινγκ το 1936-1937, οι μηχανές-μοντέλα επιτρέπουν ως και 9 διαφορετικούς τύπους από 5-άδες:

	Τρέχων μ σχηματισμός(κατάσταση Τιούρινγκ)	Σύμβολο στη ταινία	Διαδικασία Εκτύπωσης	Κίνηση της Ταινίας	Τελικός μ σχηματισμός (κατάσταση Τιούρινγκ)	5-άδα	5-άδα σχόλια	4-άδα
N1	q_i	S_j	Εκτύπωσε(S_k)	Αριστερά L	q_m	(q_i, S_j, S_k, L, q_m)	"κενό" = S₀, 1=S₁, etc.
N2	q_i	S_j	Εκτύπωσε(S_k)	Δεξιά R	q_m	(q_i, S_j, S_k, R, q_m)	"κενό" = S₀, 1=S₁, etc.
N3	q_i	S_j	Εκτύπωσε(S_k)	Τίποτα N	q_m	(q_i, S_j, S_k, N, q_m)	"κενό" = S₀, 1=S₁, etc.	(q_i, S_j, S_k, q_m)
4	q_i	S_j	Τίποτα N	Αριστερά L	q_m	(q_i, S_j, N, L, q_m)		(q_i, S_j, L, q_m)
5	q_i	S_j	Τίποτα N	Δεξιά R	q_m	(q_i, S_j, N, R, q_m)		(q_i, S_j, R, q_m)
6	q_i	S_j	Τίποτα N	Τίποτα N	q_m	(q_i, S_j, N, N, q_m)	Απευθείας "μετάβαση"	(q_i, S_j, N, q_m)
7	q_i	S_j	Διαγραφή	Αριστερά L	q_m	(q_i, S_j, E, L, q_m)
8	q_i	S_j	Διαγραφή	Δεξιά R	q_m	(q_i, S_j, E, R, q_m)
9	q_i	S_j	Διαγραφή	Τίποτα N	q_m	(q_i, S_j, E, N, q_m)		(q_i, S_j, E, q_m)

Οποιοσδήποτε πίνακας Τιούρινγκ (κατάλογος εντολών) μπορεί να κατασκευαστεί από τις παραπάνω εννιά 5-άδες. Για τεχνικούς λόγους, οι τρεις εντολές μη-εκτύπωσης ή "Ν" εντολές (4,5,6) μπορούν συνήθως να παραλειφθούν. Για παραδείγματα βλ. Turing machine examples.

Λιγότερο συχνά συναντάται η χρήση της 4-άδας: αυτές αναπαριστούν μια περαιτέρω εξατομίκευση των εντολών Τιούρινγκ (Post (1947)), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); για περισσότερα βλ. Post–Turing machine.

Η "κατάσταση"

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

Κατά αυτόν τον τρόπο η κατάσταση εξέλιξης του υπολογισμού σε κάθε στάδιο είναι εντελώς καθορισμένη από το υπόμνημα των εντολών και των συμβόλων στην ταινία. Δηλαδή, η κατάσταση του συστήματος μπορεί να περιγραφεί από μια απλή έκφραση (ακολουθία συμβόλων) αποτελούμενη από τα σύμβολα στην ταινία ακολουθούμενα από Δ (που υποθέτουμε ότι δεν θα εμφανιστεί αλλού) και έπειτα από το υπόμνημα εντολών. Αυτή η έκφραση ονομάζεται 'φόρμουλα κατάστασης' .
— Undecidable, σελ.139–140, με έμφαση

Νωρίτερα στο έγγραφο του ο Τούρινκγ το προχώρησε περαιτέρω: δίνει ένα παράδειγμα όπου τοποθέτησε ένα σύμβολο από τον τρέχων "μ-σχηματισμό" -η επιγραφή της εντολής- κάτω από το κελί που διαβάζεται , μαζί με όλα τα σύμβολα της ταινίας (Undecidable, σελ. 121); αυτό το ονομάζει "ο πλήρης σχηματισμός" (Undecidable, σελ. 118). Για να εκτυπώσει τον "πλήρη σχηματισμό" σε μία γραμμή, τοποθετεί την ετικέτα-κατάστασης/μ-σχηματισμό στα αριστερά από το σύμβολο που διαβάζεται.

Μια παραλλαγή αυτού βλέπουμε στον Kleene (1952) όπου ο Kleene δείχνει πώς να γράψεις Gödel number από μια "κατάσταση" μηχανής: τοποθετεί το σύμβολο του q4 "μ-σχηματισμού" πάνω από το κελί που διαβάζεται περίπου στο κέντρο από τα 6 μη-κενά κελιά στην ταινία (βλέπε την εικόνα της Τιούρινγκ-ταινίας σ 'αυτό το άρθρο) και το τοποθετεί στα δεξιά από το κελί που διαβάζεται. Αλλά ο Kleene αναφέρεται στο "q4" ώς την "κατάσταση μηχανής" (Kleene, σελ. 374-375). Οι Hopcroft και Ullman καλούν αυτή τη μίξη η "στιγμιαία περιγραφή" και ακολουθούν τη συνήθεια του Τιούρινγκ να τοποθετεί την "τρέχουσα κατάσταση" (επιγραφή της εντολής , μ-σχηματισμός) στα αριστερά του συμβόλου που διαβάζεται (σελ. 149).

Παράδειγμα: η ολική κατάσταση του πολυάσχολου beaver αποτελούμενου από 3-καταστάσεις 2-σύμβολα μετά από 3 "κινήσεις" (από το παράδειγμα "run" στο παρακάτω σχήμα):

1A1

Αυτό σημαίνει: μετά από τρεις κινήσεις η ταινία έχει ... 000110000 ... πάνω της, η κεφαλή σαρώνει το δεξιότερο 1, και η κατάσταση είναι A. Τα κενά διαστήματα (σ' αυτήν την περίπτωση αντιπροσωπεύονται με "0") μπορούν να είναι μέρος από την ολική κατάσταση όπως φαίνεται εδώ: B01; η ταινία έχει ένα μοναδικό 1 πάνω της, αλλά η κεφαλή σαρώνει το "0" ("κενό") στα αριστερά του και η κατάσταση είναι B.

Η "κατάσταση" στο πλαίσιο της μηχανής Τιούρινγκ πρέπει να διευκρινιστεί ως προς τι περιγράφεται: (i) η τρέχουσα εντολή, ή (ii) η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή, ή (iii) η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή τοποθετημένα στα αριστερά ή στα δεξιά από το σύμβολο που διαβάζεται. Ο βιογράφος του Τιούρινγκ Andrew Hodges (1983: 107) σημείωσε και συζήτησε αυτή τη σύγχυση.

Τα διάγραμμα "κατάστασης" της μηχανής Τιούρινγκ

Ο πίνακας για τις 3-καταστάσεις του πολυάσχολου "beaver" ("P" = εκτύπωσε/γράψε "1")
Σύμβολο ταινίας	Τρέχουσα κατάσταση A			Τρέχουσα κατάσταση B			Τρέχουσα κατάσταση C
	Κατεγράψε σύμβολο	Μετακίνησε την ταινία	Επόμενη κατάσταση	Κατέγράψε σύμβολο	Μετακίνησε την ταινία	Επόμενη κατάσταση	Κατέγράψε σύμβολο	Μετακίνησε την ταινία	Επόμενη κατάσταση
0	P	R	B	P	L	A	P	L	B
1	P	L	C	P	R	B	P	R	ΣΤΟΠ

Ο πολυάσχολος "beaver" με τις 3-καταστάσεις της μηχανής Τιούρινγκ σε μιαπεπερασμένη παράσταση καταστάσεων. Κάθε κύκλος αναπαριστά μια "κατάσταση" του πίνακα-έναν "μ-σχηματισμό" ή "εντολή". Η "διεύθυνση" απο μια μετάβαση κατάστασης φαίνεται από ένα βέλος . Η ετικέτα (δηλ. 0/P,R) δίπλα στην εξερχόμενη κατάσταση (στην ουρά του βέλους) προσδιορίζει το σύμβολο που διαβάζεται που επιφέρει μια συγκεκριμένη μετάβαση (δηλ. 0) ακολουθούμενη από κάθετο /, ακολουθούμενη απο μεταγενέστερες "συμπεριφορές" της μηχανής , δηλ. "P Εκτύπωσε" έπειτα μετακίνησε την ταινία "R Δεξιά". Δεν υπάρχει γενική αποδεκτή φόρμα. Η σύμβαση φαίνεται μετά τους McClusky (1965), Booth (1967), Hill, και Peterson (1974).

Στα δεξιά: ο παραπάνω πίνακας όπως εκφράζεται σαν διάγραμμα "μετάβαση κατάστασης". Συνήθως μεγάλοι πίνακες είναι καλύτερο να παραμένουν ως πίνακες (Booth, σελ. 74). Προσομοιώνονται ευκολότερα από τον υπολογιστή σε μορφή πίνακα (Booth, σελ. 74). Ωστόσο , ορισμένες έννοιες -π.χ. μηχανές με καταστάσεις "επαναφοράς" και μηχανές με επαναλαμβανόμενα μοτίβα(των Hill και Peterson σελ. 244ff)—μπορούν ευκολότερα να αναγνωριστούν όταν φαίνονται σαν σχήματα.

Το εάν ένα σχήμα αντιπροσωπεύει μια βελτίωση στον πίνακα του πρέπει να αποφασιστεί από τον αναγνώστη για το συγκεκριμένο πλαίσιο. Βλέπε Finite state machine για περισσότερα.

Θα έπρεπε να προειδοποιήσουμε τον αναγνώστη ότι τέτοια διαγράμματα αναπαριστούν ένα στιγμιότυπο του πίνακά παγωμένο στο χρόνο , όχι την πορεία ("τροχιά") ενός υπολογισμού διαμέσου του χρόνου και/ή του χώρου. Αν και κάθε φορά που η μηχανή πολυάσχολος "beaver" θα "τρέχει" , θα ακολουθεί πάντα την ίδια τροχιά-καταστάσεων, αυτό δεν είναι ισχύει και για το "αντίγραφο" της μηχανής το οποίο μπορεί να εφοδιάζεται με ποικίλες εισερχόμενες "παραμέτρους". Το διάγραμμα "Εξέλιξη του υπολογισμού" δείχνει την εξέλιξη των καταστάσεων (εντολών) του πολυάσχολου "beaver" 3-καταστάσεων διαμέσου του υπολογισμού του από την αρχή στο τέλος. Στο δεξιό μέρος της εικόνας είναι ο Τιούρινγκ "πληρης σχηματισμός" (Kleene "κατάσταση", Hopcroft–Ullman "στιγμιαία περιγραφή") σε κάθε βήμα. Αν η μηχανή έπρεπε να διακοπεί και να καθαριστεί και να αδειάσει τόσο το "μητρώο καταστάσεων" όσο και ολόκληρη η ταινία , αυτοί οι "σχηματισμοί" θα μπορούσαν να χρησιμοποιηθούν για να αναζωπυρωθεί ένας υπολογισμός οπουδήποτε στην εξέλιξη του (από Τιούρινγκ (1936) Undecidable pp. 139–140).

Ισοδύναμα μοντέλα με τη μηχανή Τιούρινγκ

Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή Τιούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(Hopcroft και Ullman σελ. 159, cf Minsky (1967)). Ίσως υπολογίζουν γρηγορότερα, ή χρησιμοποιούν λιγότερη μνήμη ή το σύνολο εντολών τους είναι μικρότερο, αλλά δεν μπορούν να υπολογίσουν ισχυρότερα( δηλ. περισσότερες μαθηματικές συναρτήσεις). (Θυμηθείτε ότι η Church–Turing thesis υποθέτει ότι το παρακάτω είναι πραγματικό για κάθε είδους μηχανή: οτιδήποτε μπορεί να "υπολογιστεί", μπορεί να υπολογιστεί από κάποια μηχανή Τιούρινγκ.)

Μια μηχανή Τιούρινγκ είναι ισοδύναμη με ένα pushdown automaton το οποίο έχει δημιουργηθεί πιο ευέλικτο και συνοπτικό χαλαρώνοντας το κριτήριο last-in-first-out της στοίβας του.

Στο άλλο άκρο, κάποια άλλα απλά μοντέλα μπορούν να αποδειχθούν Turing-equivalent, δηλ. να έχουν την ίδια υπολογιστική δύναμη όπως το μοντέλο της μηχανής Τιούρινγκ.

Κοινά ισοδύναμα μοντέλα είναι τα multi-tape Turing machine, multi-track Turing machine, μηχανές με είσοδο και έξοδο, και το non-deterministic Turing machine (NDTM) που αντιτίθεται στην ντετερμινιστική μηχανή Τιούρινγκ(DTM) στην οποία κάθε πίνακας πράξεων έχει το πολύ μια είσοδο για κάθε συνδυασμό από σύμβολα και καταστάσεις.

Οι μηχανές Read-only, right-moving Turing machines είναι ισοδύναμες με μη προσδιοριστά πεπερασμένα αυτόματα (NDFAs) (καθώς και με προσδιοριτστά πεπερασμένα αυτόματα (DFAs) με μετατροπή χρησιμοποιώντας τον αλγόριθμο NDFA to DFA conversion algorithm).

Για πρακτικούς και διδακτικούς λόγους η ισοδύναμη register machine μπορεί να χρησιμοποιηθεί σαν μια συνηθισμένη assembly Γλώσσα προγραμματισμού.
Γενικές μηχανές Τιούρινγκ
Μια εφαρμογή της μηχανής Τιούρινγκ

Όπως έγραψε ο Τιούρινγκ στο Undecidable, σελ. 128 (με πλάγια γράμματα):

Είναι πιθανό να εφευρεθεί μια «απλή μηχανή» η οποία μπορεί να χρησιμοποιηθεί για να υπολογίζει «οποιαδήποτε» υπολογίσιμη ακολουθία. Αν αυτή η μηχανή U τροφοδοτηθεί με την ταινία, στην αρχή της οποίας γράφεται από κάποια υπολογιστική μηχανή M η σειρά των πεντάδων διαχωριζόμενες με ερωτηματικά, τότε η U θα υπολογίσει την ίδια σειρά με την M.

Αυτή η ανακάλυψη θεωρείται πλέον δεδομένη, αλλά στον καιρό του (1936) θεωρήθηκε εκπληκτική. Το μοντέλο του υπολογισμού το οποίο καλεί ο Τιούρινγκ «γενική μηχανή» —"U" για συντομία—, θεωρείται από κάποιους (βλέπε Davis (2000)) ότι είναι η θεμελιώδης θεωρητική επανάσταση, που οδήγησε στη θεωρία του stored-program computer.

Η εργασία του Τιούρινγκ ... περιέχει, στην ουσία ,την εφεύρεση των σύγχρονων υπολογιστών και μερικών τεχνικών προγραμμάτων που τους συνόδευσαν .
— Minsky (1967),σελ. 104

Στην έννοια του computational complexity, μια γενική μηχανή Τιούρινγκ με πολλαπλή-ταινία χρειάζεται μόνο να είναι πιο αργή από λογαριθμικό παράγοντα σε σύγκριση με τις μηχανές που προσομοιώνει. Αυτό το αποτέλεσμα μαθεύτηκε το 1966 από τους F. C. Hennie και R. E. Stearns. (Arora και Barak, 2009, θεώρημα 1.9)
Σύγκριση με αληθινές μηχανές
Η πραγματοποίηση μιας μηχανής Τιούρινγκ με τουβλάκια LEGO

Συχνά λέγεται πως οι μηχανές Τιούρινγκ, αντίθετα με τα απλούστερα αυτόματα, είναι τόσο ισχυρές όσο και οι πραγματικές μηχανές, και πως είναι ικανές να εκτελέσουν οποιοδήποτε εγχείρημα θα μπορούσε και ένα πραγματικό πρόγραμμα να εκτελέσει. Αυτό που παραβλέπεται στην παραπάνω δήλωση είναι το γεγονός πως μια πραγματική μηχανή μπορεί να έχει πεπερασμένες το πλήθος διαμορφώσεις, οπότε αυτή η "πραγματική μηχανή" δεν είναι τίποτα παραπάνω από ένα linear bounded automaton.Από την άλλη πλευρά, οι μηχανές Τιούρινγκ είναι ισοδύναμες με μηχανές που έχουν απεριόριστη χωρητικότητα για τους υπολογισμούς τους. Στην πραγματικότητα, οι μηχανές Τιούρινγκ δεν χρησιμοποιούνται για να μοντελοποιούν υπολογιστές, αλλά για να μοντελοποιούν κατευθείαν τον υπολογισμό. Ιστορικά, οι υπολογιστές που είναι ικανοί να κάνουν υπολογισμούς χρησιμοποιώντας την εσωτερική (σταθερή) χωρητικότητα, αναπτύχθηκαν αργότερα.

Υπάρχουν πολλοί τρόποι για να εξηγηθεί το γιατί οι μηχανές Τιούρινγκ είναι χρήσιμες σαν μοντέλα των πραγματικών υπολογιστών:

Οτιδήποτε μπορεί να υπολογίσει ένας πραγματικός υπολογιστής, μπορεί να το υπολογίσει και μια μηχανή Τιούρινγκ. Για παράδειγμα: "Μία μηχανή Τιούρινγκ μπορεί να προσομοιώσει οποιαδήποτε υπορουτίνα εμφανίζεται και σε μια προγραμματιστική γλώσσα, συμπεριλαμβανομένων και των επαναληπτικών διαδικασιών και κάθε μορφής γνωστών μηχανισμών προώθησης παραμέτρων" (Hopcroft και Ullman σελ. 157). Ένα αρκετά μεγάλο FSA μπορεί επίσης να μοντελοποιήσει οποιοδήποτε πραγματικό υπολογιστή, ανεξάρτητα IO. Όμως μια δήλωση σχετικά με τους περιορισμούς σε μια μηχανή Τιούρινγκ, ισχύει και για τους πραγματικούς υπολογιστές.
Η διαφορά βρίσκεται μόνο στο πώς μπορεί μια μηχανή Τιούρινγκ να χειριστεί μια απεριόριστη ποσότητα δεδομένων. Παρόλ' αυτά, δοσμένου κάποιου πεπερασμένου χρόνου, μια μηχανή Τιούρινγκ (όπως και μια αληθινή μηχανή) μπορεί να χειριστεί μόνο ένα πεπερασμένο πλήθος δεδομένων.
Όπως μια μηχανή Τιούρινγκ, μια πραγματική μηχανή μπορεί να επεκτείνει την χωρητικότητα της όταν χρειάζεται, αξιοποιώντας περισσότερους δίσκους ή μέσα αποθήκευσης. Εάν η διαθεσιμότητα αυτών μειωθεί, μειώνεται και η χρησιμότητα της μηχανής Τιούρινγκ ως μοντέλο. Η αλήθεια όμως είναι πώς ούτε οι μηχανές Τιούρινγκ, ούτε οι πραγματικές μηχανές χρειάζονται αστρονομικές ποσότητες αποθηκευτικού χώρου για να μπορέσουν να εκτελέσουν χρήσιμους υπολογισμούς. Ο χρόνος εκτέλεσης που απαιτείται είναι συνήθως ένα μεγαλύτερο πρόβλημα.

Οι περιγραφές προγραμμάτων πραγματικών μηχανών που χρησιμοποιούν πιο απλά γενικά μοντέλα είναι συνήθως πιο περίπλοκες απ'ότι οι περιγραφές που χρησιμοποιούν οι μηχανές Τιούρινγκ. Για παράδειγμα, μια μηχανή Τιούρινγκ που περιγράφει έναν αλγόριθμό μπορεί να έχει μερικές εκατοντάδες καταστάσεις, ενώ ένα αντίστοιχο ντετερμινιστικό πεπερασμένο αυτόματο (DFA) μιας συγκεκριμένης αληθινής μηχανής θα έχει τετράκις εκατομμύρια. Το γεγονός αυτό κάνει την ανάλυση της DFA αναπαράστασης ακατόρθωτη.
Οι μηχανές Τιούρινγκ περιγράφουν αλγορίθμους ανεξάρτητα από το πόσο μνήμη χρησιμοποιούν. Υπάρχει ένα όριο στην μνήμη που καταλαμβάνεται από κάθε συνήθη μηχανή, αλλά αυτό το όριο μπορεί να αυξηθεί αυθαιρέτως στον χρόνο. Οι μηχανές Τιούρινγκ μας επιτρέπουν να κάνουμε δηλώσεις για αλγορίθμους οι οποίοι μπορεί (θεωρητικά) να τρέχουν για πάντα, ανεξάρτητα από την πρόοδο στην αρχιτεκτονική των συμβατικών υπολογιστικών μηχανών.
Οι μηχανές Τιούρινγκ απλοποιούν την δήλωση των αλγορίθμων. Οι αλγόριθμοι που τρέχουν σε μια γενική μηχανή ισοδύναμη μιας μηχανής Τιούρινγκ είναι συνήθως πιο γενικοί από τους αντίστοιχους που τρέχουν σε πραγματικές μηχανές, γιατί έχουν διαθέσιμους διαφορετικούς τύπους αυθαίρετης ακρίβειας και δεν έρχονται ποτέ αντιμέτωποι με απρόσμενες συνθήκες (συμπεριλαμβανομένης, χωρίς όμως να τις περιορίζει, της περίπτωσης να ξεμείνουν από μνήμη (out of memory) ).

Ένας λόγος για τον οποίο οι μηχανές Τιούρινγκ μπορούν να θεωρηθούν "φτωχές" είναι ότι αρκετά πραγματικά προγράμματα, όπως τα λειτουργικά συστήματα (operating systems) και οι επεξεργαστές κειμένου (word processors), γράφονται για να δέχονται απεριόριστες εισαγωγές μέσα στο χρόνο και γι'αυτό δεν σταματούν. Οι μηχανές Τιούρινγκ δεν μπορούν να μοντελοποιήσουν καλά τέτοιους συνεχείς υπολογισμούς (μπορούν όμως να μοντελοποιήσουν κομμάτια αυτών, όπως ανεξάρτητες διαδικασίες).
Ένα πειραματικό πρωτότυπο για να επιτευχθεί η μηχανή Τιούρινγκ
Περιορισμοί των μηχανών Τιούρινγκ
Υπολογιστική θεωρία πολυπλοκότητας

Ένα περιορισμός των μηχανών Τιούρινγκ είναι ότι δεν μπορούν να μοντελοποιήσουν καλά την δύναμη ενός συγκεκριμένου εγχειρήματος.Για παράδειγμα, οι μοντέρνοι υπολογιστές αποθηκευμένου προγράμματος (stored-program computers) είναι στην πραγματικότητα περιπτώσεις μιας πιο συγκεκριμένης μορφής της γενικής μηχανής (abstract machine), γνωστή και ως η μηχανή αποθηκευμένου προγράμματος τυχαίας πρόσβασης (random access stored program machine) ή RASP μοντέλο μηχανής. Όπως και η γενική μηχανή Τιούρινγκ, έτσι η RASP αποθηκεύει το "πρόγραμμα" στην "μνήμη" έξω από τις πεπερασμένων καταστάσεων "εντολές" της μηχανής. Αντίθετα από την γενική μηχανή Τιούρινγκ , η RASP έχει ένα απεριόριστο πλήθος από ξεχωριστά, αριθμημένα αλλά απεριόριστα "εγγραφείς"-"κελιά" μνήμης τα οποία μπορεί να περιέχουν οποιονδήποτε ακέραιο(βλ. Elgot and Robinson (1964), Hartmanis (1971), και πιο συγκεκριμένα Cook-Rechow (1973); αναφορές σε random access machine). Η πεπερασμένων-καταστάσεων μηχανή του RASP είναι εξοπλισμένη με την ικανότητα για έμμεση αντιμετώπιση (δηλαδή τα περιεχόμενα ενός εγγραφέα μπορούν να χρησιμοποιηθούν σαν μια διεύθυνση ενός ακόμα εγγραφέα), όμως το "πρόγραμμα" του RASP μπορεί να χρησιμοποιήσει οποιονδήποτε εγγραφέα από την ακολουθία των εγγραφέων. Το αποτέλεσμα αυτής της διάκρισης είναι ότι υπάρχουν υπολογιστικές βελτιστοποιήσεις, βασισμένες στους δείκτες μνήμης, οι οποίες μπορούν να εκτελεστούν, κάτι που δεν είναι εφικτό σε μια μηχανή Τιούρινγκ. Παρόλ' αυτά όταν μια μηχανή Τιούρινγκ χρησιμοποιείται σαν βάση για τον περιορισμό του χρόνου λειτουργίας, ένα "ψευδές κάτω όριο" μπορεί να βρεθεί στους χρόνους λειτουργίας συγκεκριμένων αλγορίθμων (λόγω της ψευδής υπόθεσης απλοποίησης της μηχανής Τιούρινγκ). Ένα παράδειγμα αυτού είναι η δυαδική αναζήτηση, ένας αλγόριθμος που μπορεί να δειχτεί πως λειτουργεί πιο γρήγορα όταν χρησιμοποιεί το RASP μοντέλο, αντί για το μοντέλο της μηχανής Τιούρινγκ.
Συγχρονισμός

Άλλος ένας περιορισμός των μηχανών Τιούρινγκ είναι ότι δεν μπορούν να μοντελοποιήσουν τον συγχρονισμό πολύ καλά. Για παράδειγμα, υπάρχει ένα όριο στο μέγεθος του ακεραίου που μπορεί να υπολογιστεί από μία συνεχώς-αμφιταλαντευόμενη μη-προσδιοριστή μηχανή Τιούρινγκ που ξεκινάει με μια κενή ταινία(Βλέπε το άρθρο unbounded nondeterminism.) Από την άλλη, υπάρχουν κάποια συνεχώς-αμφιταλαντευόμενα συγχρονισμένα συστήματα, που δεν έχουν καθόλου εισόδους, που μπορούν να υπολογίσουν έναν ακέραιο απεριόριστου μεγέθους.(Μια διαδικασία μπορεί να δημιουργηθεί με τοπική μνήμη που ξεκινά μετρώντας τα 0 ενώ ταυτόχρονα στέλνει στον εαυτό της τις εντολές σταμάτα και ξεκίνα. Όταν δέχεται το μήνυμα ξεκίνα, προσαυξάνει το μέτρημα κατά 1 και στέλνει στον εαυτό της ένα μήνυμα ξεκίνα. Όταν λαμβάνει ένα μήνυμα σταμάτα, σταματάει με έναν απεριόριστο αριθμό στην τοπική της μνήμη.)

Αναφορές

Η ιδέα ήρθε σ 'αυτόν στα μέσα του 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

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

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

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

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License