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

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

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

Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή Τούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(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)

Υπολογιστική θεωρία πολυπλοκότητας

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