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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Turing machine.png

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

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

Ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

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

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

  1. John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages and computation, 1979, Addison-Wesley, Reading, Massachusetts
  2. Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Second edition, 1998, Prentice-Hall, Upper Saddle River, New Jersey

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Commons logo
Τα Wikimedia Commons έχουν πολυμέσα σχετικά με το θέμα
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Turing machine της Αγγλόγλωσσης Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).