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