From Wikipedia, the free encyclopedia
Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε αλγορίθμου, και είναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας κεντρικής μονάδας επεξεργασίας στο εσωτερικό του υπολογιστή.
Η μηχανή του Τούρινγκ εφευρέθηκε το 1936 από τον Άλαν Τούρινγκ.[1] Η μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.
Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:
....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της είναι εν μέρει αποφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της.
Μια μηχανή Τούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή Τούρινγκ λέγεται Καθολική Μηχανή Τούρινγκ (ή απλά καθολική μηχανή). Ένας πιο μαθηματικός ορισμός με παρόμοια "καθολική" φύση τέθηκε από τον Αλόνζο Τσερτς, του οποίου η εργασία πάνω στο λογισμό λάμδα συνυφαίνεται με αυτή του Τούρινγκ σε μια τυπική θεωρία υπολογισμού που είναι γνωστή ως η θέση Τσερτς-Τούρινγκ. Η θέση λέει ότι οι μηχανές Τούρινγκ όντως εμπεριέχουν την ανεπίσημη έννοια της αποδοτικής μεθόδου στη λογική και τα μαθηματικά, και δίνουν έναν ακριβή ορισμό ενός αλγορίθμου ή μιας μηχανικής διαδικασίας.
Η Μηχανή Τούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών όπως "στην κατάσταση 42, εάν το σύμβολο που εμφανίζεται είναι το 0, τότε γράψε 1, ενώ εάν το σύμβολο που εμφανίζεται είναι το 1, πήγαινε στην κατάσταση 17 και στην κατάσταση 17, εάν το σύμβολο που εμφανίζεται είναι 0, γράψε 1 και πήγαινε στην κατάσταση 6" κλπ. Στο πρωτότυπο άρθρο ("On computable numbers, with an application to the Entscheidungsproblem", βλέπε επίσης references below), ο Τούρινγκ δεν φαντάζεται έναν μηχανισμό, αλλά ένα άτομο το οποίο αποκαλεί ο "υπολογιστής", το οποίο εκτελεί δουλικά αυτούς τους ντετερμινιστικούς μηχανικούς κανόνες (ή όπως το θέτει ο Τούρινγκ με έναν "ξεκάρφωτο" τρόπο).
Πιο συγκεκριμένα, μια Μηχανή Τούρινγκ αποτελείται από:
Στο τετραπλό μοντέλο , η απαλοιφή ή η καταγραφή ενός συμβόλου (aj1) και η μετακίνηση της κεφαλής αριστερά ή δεξιά (dk) καθορίζονται ως ξεχωριστές εντολές. Συγκεκριμένα , ο πίνακας λέει στη μηχανή (ia) να διαγράψει ή να καταγράψει ένα σύμβολο ή (ib) να κινήσει την κεφαλή αριστερά ή δεξιά , και έπειτα (ii) να θεωρήσει την ίδια ή καινούργια κατάσταση όπως ορίζεται , άλλα όχι και τις 2 ενέργειες ia) , ib), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχοντα συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.
Παρατηρήστε ότι κάθε κομμάτι της μηχανής (δηλαδή οι καταστάσεις και τα σύμβολα) και οι πράξεις της (όπως η εκτύπωση, η διαγραφή και η κίνηση της ταινίας) είναι πεπερασμένα, ευδιάκριτα και διακεκριμένα. Το πιθανώς απεριόριστο μήκος της ταινίας είναι που δίνει στη μηχανή μια απεριόριστη χωρητικότητα.
Οι Χόπκροφτ και Ούλμαν[2] (σελ. 148) ορίζουν μια μηχανή Τούρινγκ ως την επτάδα , όπου
Στη βιβλιογραφία έχουν εμφανιστεί διάφοροι ορισμοί λίγο διαφορετικοί μεταξύ τους, συνήθως για να κάνουν την εξήγηση ή τις αποδείξεις πιο απλές, αλλά πάντα η μηχανή που ορίζεται είναι το ίδιο ισχυρή υπολογιστικά. Για παράδειγμα, οι Λιούις και Παπαδημητρίου [3] (σελ. 181) ορίζουν τη μηχανή Τούρινγκ ως την πεντάδα , όπου
Σύμφωνα με τα λόγια του van Emde Boas (1990) σελ.6: "Το συνολοθεωρητικό αντικείμενο [η κανονική επταπλή περιγραφή που μοιάζει με αυτήν που περιγράφηκε πριν] μας παρέχει μόνο μερικές πληροφορίες σχετικά με το πώς λειτουργεί η μηχανή και πώς θα μοιάζουν οι υπολογισμοί της."
Για παράδειγμα,
Οι ορισμοί στην λογοτεχνία μερικές φορές διαφέρουν ελαφρώς, ώστε να είναι οι προτάσεις και οι αποδείξεις απλούστερες ή πιο ξεκάθαρες, αλλά αυτό γίνεται πάντα με τέτοιο τρόπο ώστε η προκύπτουσα μηχανή να έχει την ίδια υπολογιστική δύναμη. Για παράδειγμα, αλλάζοντας το σύνολο με το , όπου N ("Καμία" ή "Χωρίς-Εκτέλεση") θα επέτρεπε στη μηχανή να παραμείνει στο ίδιο κελί της ταινίας, αντί να κινείται δεξιά και αριστερά, δεν αυξάνει την υπολογιστική δύναμη της μηχανής.
Η πιο κοινή σύμβαση είναι να αναπαριστάται κάθε "εντολή Τούρινγκ" σε έναν "πίνακα Τούρινγκ" με μία από τις εννιά πενταπλότητες, όπως η σύμβαση των Τούρινγκ/Davis (Τούρινγκ (1936) στο "Undecideable", σελ.126-127 και Davis (2000), σελ.152):
Άλλοι συγγραφείς (Minsky (1967) σελ. 119, Hopcroft and Ullman (1979) σελ. 158, Stone (1972) σελ. 9) υιοθετούν μια διαφορετική σύμβαση, με μια νέα κατάσταση qm η οποία κατaγράφεται αμέσως μετά το σύμβολο που διαβάζεται Sj:
Για το υπόλοιπο του άρθρου, θα χρησιμοποιείται ο "ορισμός 1" (ορισμός των Τούρινγκ/Davis)
Παρούσα Κατάσταση | Σύμβολο που διαβάζεται | Σύμβολο που εκτυπώνεται | Κίνηση της ταινίας | Τελική (δηλ. επόμενη) κατάσταση | 5-άδα | |
---|---|---|---|---|---|---|
A | 0 | 1 | R | B | (A, 0, 1, R, B) | |
A | 1 | 1 | L | C | (A, 1, 1, L, C) | |
B | 0 | 1 | L | A | (B, 0, 1, L, A) | |
B | 1 | 1 | R | B | (B, 1, 1, R, B) | |
C | 0 | 1 | L | B | (C, 0, 1, L, B) | |
C | 1 | 1 | N | H | (C, 1, 1, N, H) |
Στον επόμενο πίνακα, η αυθεντική μηχανή του Τούρινγκ επέτρεπε μόνο τις τρεις πρώτες γραμμές να εμφανίζονται, τις οποίες ονόμαζε Ν1, Ν2, Ν3 (βλ. Τούρινγκ στο "Undecideable", σελ. 126). Επέτρεπε την διαγραφή του "κελιού που διαβάζεται", ονομάζοντας το 0-νικό σύμβολο S0 = "διαγραφέα" ή "κενό", κλπ, όμως, δεν επέτρεπε να μην εκτυπωθεί, και έτσι η κάθε γραμμή-εντολή περιλαμβάνει "εκτύπωση συμβόλου Sk" ή "διαγραφή" (βλ. παραπομπή 12 στο Post (1947), Undecideable σελ. 300). Οι συντομεύσεις είναι του Τούρινγκ("Undecideable", σελ. 119). Ως επακόλουθο, του πρωτότυπου άρθρου του Τούρινγκ το 1936-1937, οι μηχανές-μοντέλα επιτρέπουν ως και 9 διαφορετικούς τύπους από 5-άδες:
Τρέχων μ σχηματισμός(κατάσταση Τούρινγκ) | Σύμβολο στη ταινία | Διαδικασία Εκτύπωσης | Κίνηση της Ταινίας | Τελικός μ σχηματισμός (κατάσταση Τούρινγκ) | 5-άδα | 5-άδα σχόλια | 4-άδα | |
---|---|---|---|---|---|---|---|---|
N1 | qi | Sj | Εκτύπωσε(Sk) | Αριστερά L | qm | (qi, Sj, Sk, L, qm) | "κενό" = S0, 1=S1, etc. | |
N2 | qi | Sj | Εκτύπωσε(Sk) | Δεξιά R | qm | (qi, Sj, Sk, R, qm) | "κενό" = S0, 1=S1, etc. | |
N3 | qi | Sj | Εκτύπωσε(Sk) | Τίποτα N | qm | (qi, Sj, Sk, N, qm) | "κενό" = S0, 1=S1, etc. | (qi, Sj, Sk, qm) |
4 | qi | Sj | Τίποτα N | Αριστερά L | qm | (qi, Sj, N, L, qm) | (qi, Sj, L, qm) | |
5 | qi | Sj | Τίποτα N | Δεξιά R | qm | (qi, Sj, N, R, qm) | (qi, Sj, R, qm) | |
6 | qi | Sj | Τίποτα N | Τίποτα N | qm | (qi, Sj, N, N, qm) | Απευθείας "μετάβαση" | (qi, Sj, N, qm) |
7 | qi | Sj | Διαγραφή | Αριστερά L | qm | (qi, Sj, E, L, qm) | ||
8 | qi | Sj | Διαγραφή | Δεξιά R | qm | (qi, Sj, E, R, qm) | ||
9 | qi | Sj | Διαγραφή | Τίποτα N | qm | (qi, Sj, E, N, qm) | (qi, Sj, E, qm) |
Οποιοσδήποτε πίνακας Τούρινγκ (κατάλογος εντολών) μπορεί να κατασκευαστεί από τις παραπάνω εννιά 5-άδες. Για τεχνικούς λόγους, οι τρεις εντολές μη-εκτύπωσης ή "Ν" εντολές (4,5,6) μπορούν συνήθως να παραλειφθούν. Για παραδείγματα βλ. Turing machine examples.
Λιγότερο συχνά συναντάται η χρήση της 4-άδας: αυτές αναπαριστούν μια περαιτέρω εξατομίκευση των εντολών Τούρινγκ (Post (1947)), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); για περισσότερα βλ. Post–Turing machine.
Η λέξη "κατάσταση" που χρησιμοποιείται στο πλαίσιο της μηχανής Τούρινγκ μπορεί να είναι πηγή σύγχυσης, μιας και έχει διπλή σημασία. Οι περισσότεροι σχολιαστές μετά τον Τούρινγκ χρησιμοποιούν την "κατάσταση" για να εννοήσουν το όνομα/προσδιορισμό της τρέχουσας εντολής που πρέπει να εκτελεστεί- δηλ. τα περιεχόμενα του μητρώου κατάστασης. Αλλά ο Τούρινγκ (1936) έκανε μια ισχυρή διάκριση μεταξύ μιας καταγραφής αυτού που ονόμαζε "μ-σχηματισμός" της μηχανής, (της εσωτερικής κατάστασής του)και την "κατάσταση εξέλιξης" της μηχανής (ή του ατόμου)μέσω του υπολογισμού- η τρέχουσα κατάσταση του ολικού συστήματος. Αυτό που ο Τούρινγκ ονόμαζε "φόρμουλα κατάστασης" περιλαμβάνει και την τρέχουσα εντολή και όλα τα σύμβολα στην ταινία:
Κατά αυτόν τον τρόπο η κατάσταση εξέλιξης του υπολογισμού σε κάθε στάδιο είναι εντελώς καθορισμένη από το υπόμνημα των εντολών και των συμβόλων στην ταινία. Δηλαδή, η κατάσταση του συστήματος μπορεί να περιγραφεί από μια απλή έκφραση (ακολουθία συμβόλων) αποτελούμενη από τα σύμβολα στην ταινία ακολουθούμενα από Δ (που υποθέτουμε ότι δεν θα εμφανιστεί αλλού) και έπειτα από το υπόμνημα εντολών. Αυτή η έκφραση ονομάζεται 'φόρμουλα κατάστασης' .
— Undecidable, σελ.139–140, με έμφαση
Νωρίτερα στο έγγραφο του ο Τούρινγκ το προχώρησε περαιτέρω: δίνει ένα παράδειγμα όπου τοποθέτησε ένα σύμβολο από τον τρέχων "μ-σχηματισμό" -η επιγραφή της εντολής- κάτω από το κελί που διαβάζεται , μαζί με όλα τα σύμβολα της ταινίας (Undecidable, σελ. 121); αυτό το ονομάζει "ο πλήρης σχηματισμός" (Undecidable, σελ. 118). Για να εκτυπώσει τον "πλήρη σχηματισμό" σε μία γραμμή, τοποθετεί την ετικέτα-κατάστασης/μ-σχηματισμό στα αριστερά από το σύμβολο που διαβάζεται.
Μια παραλλαγή αυτού βλέπουμε στον Kleene (1952) όπου ο Kleene δείχνει πώς να γράψεις Gödel number από μια "κατάσταση" μηχανής: τοποθετεί το σύμβολο του q4 "μ-σχηματισμού" πάνω από το κελί που διαβάζεται περίπου στο κέντρο από τα 6 μη-κενά κελιά στην ταινία (βλέπε την εικόνα της Τούρινγκ-ταινίας σ 'αυτό το άρθρο) και το τοποθετεί στα δεξιά από το κελί που διαβάζεται. Αλλά ο Kleene αναφέρεται στο "q4" ώς την "κατάσταση μηχανής" (Kleene, σελ. 374-375). Οι Hopcroft και Ullman καλούν αυτή τη μίξη η "στιγμιαία περιγραφή" και ακολουθούν τη συνήθεια του Τούρινγκ να τοποθετεί την "τρέχουσα κατάσταση" (επιγραφή της εντολής , μ-σχηματισμός) στα αριστερά του συμβόλου που διαβάζεται (σελ. 149).
Παράδειγμα: η ολική κατάσταση του πολυάσχολου beaver αποτελούμενου από 3-καταστάσεις 2-σύμβολα μετά από 3 "κινήσεις" (από το παράδειγμα "run" στο παρακάτω σχήμα):
Αυτό σημαίνει: μετά από τρεις κινήσεις η ταινία έχει ... 000110000 ... πάνω της, η κεφαλή σαρώνει το δεξιότερο 1, και η κατάσταση είναι A. Τα κενά διαστήματα (σ' αυτήν την περίπτωση αντιπροσωπεύονται με "0") μπορούν να είναι μέρος από την ολική κατάσταση όπως φαίνεται εδώ: B01; η ταινία έχει ένα μοναδικό 1 πάνω της, αλλά η κεφαλή σαρώνει το "0" ("κενό") στα αριστερά του και η κατάσταση είναι B.
Η "κατάσταση" στο πλαίσιο της μηχανής Τούρινγκ πρέπει να διευκρινιστεί ως προς τι περιγράφεται: (i) η τρέχουσα εντολή, ή (ii) η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή, ή (iii) η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή τοποθετημένα στα αριστερά ή στα δεξιά από το σύμβολο που διαβάζεται. Ο βιογράφος του Τούρινγκ Andrew Hodges (1983: 107) σημείωσε και συζήτησε αυτή τη σύγχυση.
Σύμβολο ταινίας | Τρέχουσα κατάσταση A | Τρέχουσα κατάσταση B | Τρέχουσα κατάσταση C | ||||||
---|---|---|---|---|---|---|---|---|---|
Κατεγράψε σύμβολο | Μετακίνησε την ταινία | Επόμενη κατάσταση | Κατέγράψε σύμβολο | Μετακίνησε την ταινία | Επόμενη κατάσταση | Κατέγράψε σύμβολο | Μετακίνησε την ταινία | Επόμενη κατάσταση | |
0 | P | R | B | P | L | A | P | L | B |
1 | P | L | C | P | R | B | P | R | ΣΤΟΠ |
Στα δεξιά: ο παραπάνω πίνακας όπως εκφράζεται σαν διάγραμμα "μετάβαση κατάστασης". Συνήθως μεγάλοι πίνακες είναι καλύτερο να παραμένουν ως πίνακες (Booth, σελ. 74). Προσομοιώνονται ευκολότερα από τον υπολογιστή σε μορφή πίνακα (Booth, σελ. 74). Ωστόσο , ορισμένες έννοιες -π.χ. μηχανές με καταστάσεις "επαναφοράς" και μηχανές με επαναλαμβανόμενα μοτίβα(των Hill και Peterson σελ. 244ff)—μπορούν ευκολότερα να αναγνωριστούν όταν φαίνονται σαν σχήματα.
Το εάν ένα σχήμα αντιπροσωπεύει μια βελτίωση στον πίνακα του πρέπει να αποφασιστεί από τον αναγνώστη για το συγκεκριμένο πλαίσιο. Βλέπε Finite-state machine για περισσότερα.
Θα έπρεπε να προειδοποιήσουμε τον αναγνώστη ότι τέτοια διαγράμματα αναπαριστούν ένα στιγμιότυπο του πίνακά παγωμένο στο χρόνο , όχι την πορεία ("τροχιά") ενός υπολογισμού διαμέσου του χρόνου και/ή του χώρου. Αν και κάθε φορά που η μηχανή πολυάσχολος "beaver" θα "τρέχει" , θα ακολουθεί πάντα την ίδια τροχιά-καταστάσεων, αυτό δεν είναι ισχύει και για το "αντίγραφο" της μηχανής το οποίο μπορεί να εφοδιάζεται με ποικίλες εισερχόμενες "παραμέτρους". Το διάγραμμα "Εξέλιξη του υπολογισμού" δείχνει την εξέλιξη των καταστάσεων (εντολών) του πολυάσχολου "beaver" 3-καταστάσεων διαμέσου του υπολογισμού του από την αρχή στο τέλος. Στο δεξιό μέρος της εικόνας είναι ο Τούρινγκ "πλήρης σχηματισμός" (Kleene "κατάσταση", Hopcroft–Ullman "στιγμιαία περιγραφή") σε κάθε βήμα. Αν η μηχανή έπρεπε να διακοπεί και να καθαριστεί και να αδειάσει τόσο το "μητρώο καταστάσεων" όσο και ολόκληρη η ταινία , αυτοί οι "σχηματισμοί" θα μπορούσαν να χρησιμοποιηθούν για να αναζωπυρωθεί ένας υπολογισμός οπουδήποτε στην εξέλιξη του (από Τούρινγκ (1936) Undecidable pp. 139–140).
Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή Τούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(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)
Συχνά λέγεται πως οι μηχανές Τούρινγκ, αντίθετα με τα απλούστερα αυτόματα, είναι τόσο ισχυρές όσο και οι πραγματικές μηχανές, και πως είναι ικανές να εκτελέσουν οποιοδήποτε εγχείρημα θα μπορούσε και ένα πραγματικό πρόγραμμα να εκτελέσει. Αυτό που παραβλέπεται στην παραπάνω δήλωση είναι το γεγονός πως μια πραγματική μηχανή μπορεί να έχει πεπερασμένες το πλήθος διαμορφώσεις, οπότε αυτή η "πραγματική μηχανή" δεν είναι τίποτα παραπάνω από ένα linear bounded automaton.Από την άλλη πλευρά, οι μηχανές Τούρινγκ είναι ισοδύναμες με μηχανές που έχουν απεριόριστη χωρητικότητα για τους υπολογισμούς τους. Στην πραγματικότητα, οι μηχανές Τούρινγκ δεν χρησιμοποιούνται για να μοντελοποιούν υπολογιστές, αλλά για να μοντελοποιούν κατευθείαν τον υπολογισμό. Ιστορικά, οι υπολογιστές που είναι ικανοί να κάνουν υπολογισμούς χρησιμοποιώντας την εσωτερική (σταθερή) χωρητικότητα, αναπτύχθηκαν αργότερα.
Υπάρχουν πολλοί τρόποι για να εξηγηθεί το γιατί οι μηχανές Τούρινγκ είναι χρήσιμες σαν μοντέλα των πραγματικών υπολογιστών:
Ένας λόγος για τον οποίο οι μηχανές Τούρινγκ μπορούν να θεωρηθούν "φτωχές" είναι ότι αρκετά πραγματικά προγράμματα, όπως τα λειτουργικά συστήματα (operating systems) και οι επεξεργαστές κειμένου (word processors), γράφονται για να δέχονται απεριόριστες εισαγωγές μέσα στο χρόνο και γι' αυτό δεν σταματούν. Οι μηχανές Τούρινγκ δεν μπορούν να μοντελοποιήσουν καλά τέτοιους συνεχείς υπολογισμούς (μπορούν όμως να μοντελοποιήσουν κομμάτια αυτών, όπως ανεξάρτητες διαδικασίες).
Ένα περιορισμός των μηχανών Τούρινγκ είναι ότι δεν μπορούν να μοντελοποιήσουν καλά την δύναμη ενός συγκεκριμένου εγχειρήματος.Για παράδειγμα, οι μοντέρνοι υπολογιστές αποθηκευμένου προγράμματος (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 και στέλνει στον εαυτό της ένα μήνυμα ξεκίνα. Όταν λαμβάνει ένα μήνυμα σταμάτα, σταματάει με έναν απεριόριστο αριθμό στην τοπική της μνήμη.)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.