Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων

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

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

== Ορισμοί ==

Οι Χόπκροφτ και Ούλμαν<ref>John E. Hopcroft and Jeffrey D. Ullman. ''Introduction to automata theory, languages and computation'', 1979, Addison-Wesley, Reading, Massachusetts</ref> (σελ. 148) ορίζουν μια μηχανή Τούρινγκ ως η επτάδα <math>M= (Q, \Sigma, \Gamma, \delta, q_0, B, F)</math>, όπου

* <math>\delta</math> είναι η ''συνάρτηση της επόμενης κίνησης'', μια αντιστοιχία από το <math>Q \times \Gamma</math> στο <math>Q \times \Gamma \times \{L,R\}</math>. Η συνάρτηση <math>\delta</math> μπορεί να μην ορίζεται για όλα τα ορίσματά της,

Στη βιβλιογραφία έχουν εμφανιστεί διάφοροι ορισμοί λίγο διαφορετικοί μεταξύ τους, συνήθως για να κάνουν την εξήγηση ή τις αποδείξεις πιο απλές, αλλά πάντα η μηχανή που ορίζεται είναι το ίδιο ισχυρή υπολογιστικά. Για παράδειγμα, οι Λιούις και Παπαδημητρίου <ref>Harry R. Lewis and Christos H. Papadimitriou, ''Elements of the theory of computation'', Second edition, 1998, Prentice-Hall, Upper Saddle River, New Jersey</ref> (σελ. 181) ορίζουν τη μηχανή Τούρινγκ ως την πεντάδα <math>(K, \Sigma, \delta, s, H)</math>, όπου

* <math>\Sigma</math> είναι ένα [[αλφάβητο]], που περιέχει το ''κενό σύνολο'' <math>\sqcup</math> και το ''σύμβολο αριστερού τέλους'' <math>\triangleright</math>, αλλά όχι τα σύμβολα <math>\leftarrow</math> και <math>\rightarrow</math>,

{{μεταφρασμένοΕνσωμάτωση κειμένου|en|Turing machine}}