Μηχανή Τούρινγκ

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

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

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

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

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

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

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

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

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

1. Μία ταινία που χωρίζεται σε κελιά, το ένα δίπλα στο άλλο. Κάθε κελί περιέχει ένα σύμβολο από ένα πεπερασμένο αλφάβητο. Το αλφάβητο περιέχει ένα ειδικό κενό σύμβολο (το οποίο εδώ συμβολίζουμε με "0") και ένα ή παραπάνω άλλα σύμβολα. Υποθέτουμε πώς αυτή η ταινία είναι απείρως επεκτάσιμη προς τα αριστερά και προς τα δεξιά, δηλαδή μία μηχανή Τούρινγκ είναι πάντα προμηθευμένη με όση ταινία της χρειάζεται για τους υπολογισμούς. Κελιά τα οποία δεν έχουν συμπληρωθεί, υποθέτουμε πως είναι εξοπλισμένα με το κενό γράμμα. Σε κάποια μοντέλα, η ταινία έχει αριστερό άκρο, το οποίο είναι εξοπλισμένο με ένα ειδικό σύμβολο, όμως είναι απείρως επεκτάσιμη προς τα δεξιά.
2. Μία κεφαλή που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά. Σε μερικά μοντέλα κινείται μόνο η κεφαλή, ενώ η ταινία παραμένει σταθερή.
3. Ένα μητρώο καταστάσεων που αποθηκεύει μία κατάσταση της Μηχανής Τούρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική αρχική κατάσταση με την οποία ξεκινά το μητρώο. Αυτές οι καταστάσεις, γράφει ο Τούρινγκ, αντικαθιστούν την "πνευματική κατάσταση" στην οποία αρχικά θα ήταν το άτομο που θα έκανε τους υπολογισμούς.
4. Ένας πεπερασμένος πίνακας (ενίοτε ονομαζόμενος ως διαδραστικός πίνακας ή συνάρτηση μετάβασης) από οδηγίες (συνήθως πενταπλές [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), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχοντα συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.

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

Ορισμοί

Οι Χόπκροφτ και Ούλμαν (σελ. 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).

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

1. για κάθε $q\in K-H$, αν $\delta (q,\triangleright )=(p,b)$, τότε $b=\rightarrow$
2. για κάθε $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): (q_i, S_j, S_k/E/N, L/R/N, q_m)

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

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

(ορισμός 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

( παρούσα κατάσταση q_i , σύμβολο που διαβάζεται S_j , νέα κατάσταση q_m , εκτύπωση συμβόλουS_k/διαγραφή 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-νικό σύμβολο S₀ = "διαγραφέα" ή "κενό", κλπ, όμως, δεν επέτρεπε να μην εκτυπωθεί, και έτσι η κάθε γραμμή-εντολή περιλαμβάνει "εκτύπωση συμβόλου S_k" ή "διαγραφή" (βλ. παραπομπή 12 στο Post (1947), Undecideable σελ. 300). Οι συντομεύσεις είναι του Τούρινγκ("Undecideable", σελ. 119). Ως επακόλουθο, του πρωτότυπου άρθρου του Τούρινγκ το 1936-1937, οι μηχανές-μοντέλα επιτρέπουν ως και 9 διαφορετικούς τύπους από 5-άδες:

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

Οποιοσδήποτε πίνακας Τούρινγκ (κατάλογος εντολών) μπορεί να κατασκευαστεί από τις παραπάνω εννιά 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 από μια "κατάσταση" μηχανής: τοποθετεί το σύμβολο του q₄ "μ-σχηματισμού" πάνω από το κελί που διαβάζεται περίπου στο κέντρο από τα 6 μη-κενά κελιά στην ταινία (βλέπε την εικόνα της Τούρινγκ-ταινίας σ 'αυτό το άρθρο) και το τοποθετεί στα δεξιά από το κελί που διαβάζεται. Αλλά ο Kleene αναφέρεται στο "q₄" ώς την "κατάσταση μηχανής" (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.Από την άλλη πλευρά, οι μηχανές Τούρινγκ είναι ισοδύναμες με μηχανές που έχουν απεριόριστη χωρητικότητα για τους υπολογισμούς τους. Στην πραγματικότητα, οι μηχανές Τούρινγκ δεν χρησιμοποιούνται για να μοντελοποιούν υπολογιστές, αλλά για να μοντελοποιούν κατευθείαν τον υπολογισμό. Ιστορικά, οι υπολογιστές που είναι ικανοί να κάνουν υπολογισμούς χρησιμοποιώντας την εσωτερική (σταθερή) χωρητικότητα, αναπτύχθηκαν αργότερα.

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

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

1. Οι περιγραφές προγραμμάτων πραγματικών μηχανών που χρησιμοποιούν πιο απλά γενικά μοντέλα είναι συνήθως πιο περίπλοκες απ'ότι οι περιγραφές που χρησιμοποιούν οι μηχανές Τούρινγκ. Για παράδειγμα, μια μηχανή Τούρινγκ που περιγράφει έναν αλγόριθμό μπορεί να έχει μερικές εκατοντάδες καταστάσεις, ενώ ένα αντίστοιχο ντετερμινιστικό πεπερασμένο αυτόματο (DFA) μιας συγκεκριμένης αληθινής μηχανής θα έχει τετράκις εκατομμύρια. Το γεγονός αυτό κάνει την ανάλυση της DFA αναπαράστασης ακατόρθωτη.
2. Οι μηχανές Τούρινγκ περιγράφουν αλγορίθμους ανεξάρτητα από το πόσο μνήμη χρησιμοποιούν. Υπάρχει ένα όριο στην μνήμη που καταλαμβάνεται από κάθε συνήθη μηχανή, αλλά αυτό το όριο μπορεί να αυξηθεί αυθαιρέτως στον χρόνο. Οι μηχανές Τούρινγκ μας επιτρέπουν να κάνουμε δηλώσεις για αλγορίθμους οι οποίοι μπορεί (θεωρητικά) να τρέχουν για πάντα, ανεξάρτητα από την πρόοδο στην αρχιτεκτονική των συμβατικών υπολογιστικών μηχανών.
3. Οι μηχανές Τούρινγκ απλοποιούν την δήλωση των αλγορίθμων. Οι αλγόριθμοι που τρέχουν σε μια γενική μηχανή ισοδύναμη μιας μηχανής Τούρινγκ είναι συνήθως πιο γενικοί από τους αντίστοιχους που τρέχουν σε πραγματικές μηχανές, γιατί έχουν διαθέσιμους διαφορετικούς τύπους αυθαίρετης ακρίβειας και δεν έρχονται ποτέ αντιμέτωποι με απρόσμενες συνθήκες (συμπεριλαμβανομένης, χωρίς όμως να τις περιορίζει, της περίπτωσης να ξεμείνουν από μνήμη (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 και στέλνει στον εαυτό της ένα μήνυμα ξεκίνα. Όταν λαμβάνει ένα μήνυμα σταμάτα, σταματάει με έναν απεριόριστο αριθμό στην τοπική της μνήμη.)

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

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