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

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

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

Ορισμοί

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

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

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