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

καμία σύνοψη επεξεργασίας
μ (Ο Cplakidas μετακίνησε τη σελίδα Μηχανή Τούρινγκ στη Μηχανή Τιούρινγκ πάνω από την ανακατεύθυνση)
[[εικόνα:Turing machine.png|thumb|right|250px|]]
Η '''Μηχανή ΤούρινγκΤιούρινγκ''' είναι μια υποθετική συσκευή του η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή ΤούρινγκΤιούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε [[αλγόριθμος|αλγορίθμου]], και ειναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας [[CPU|κεντρικής μονάδας επεξεργασίας]] στο εσωτερικό του υπολογιστή.
 
Η μηχανή του ΤούρινγκΤιούρινγκ εφευρέθηκε το 1936 απο τον [[Άλαν ΤούρινγκΤιούρινγκ]].<ref>
Η ιδέα ήρθε σ 'αυτόν στα μέσα του 1935 μετά από μια ερώτηση που έθεσε ο [[Μ. HA Newman]] στις διαλέξεις του: "Υπήρχε μια συγκεκριμένη μέθοδο, ή όπως το έθεσε Newman, μια μηχανική διαδικασία'''', η οποία θα μπορούσε να εφαρμοστεί σε μια μαθηματική δήλωση, η οποία θα απαντούσε αν ήταν αποδείξιμη "</ref> Η μηχανή ΤούρινγκΤιούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές ΤούρινγκΤιούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.
 
Ο ΤούρινγκΤιούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή ΤούρινγκΤιούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:
<blockquote>
....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της ειναι εν μέρει αποφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της.
</blockquote>
 
Μια μηχανή ΤούρινγκΤιούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή ΤούρινγκΤιούρινγκ λέγεται [[Καθολική Μηχανή ΤούρινγκΤιούρινγκ]] (ή απλά '''καθολική μηχανή'''). Ένας πιο μαθηματικός ορισμός με παρόμοια "καθολική" φύση τέθηκε από τον [[Αλόνζο Τσερτς]], του οποίου η εργασία πάνω στο [[λογισμός λάμδα|λογισμό λάμδα]] συνυφαίνεται με αυτή του ΤούρινγκΤιούρινγκ σε μια τυπική θεωρία [[υπολογισμός|υπολογισμού]] που είναι γνωστή ως η [[θέση Τσερτς-ΤούρινγκΤιούρινγκ]]. Η θέση λέει ότι οι μηχανές ΤούρινγκΤιούρινγκ όντως εμπεριέχουν την ανεπίσημη έννοια της αποδοτικής μεθόδου στη λογική και τα μαθηματικά, και δίνουν έναν ακριβή ορισμό ενός [[αλγόριθμος|αλγορίθμου]] ή μιας ''μηχανικής διαδικασίας''.
 
 
==Άτυπη Περιγραφή==
Η Μηχανή ΤούρινγκΤιούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών όπως "στην κατάσταση 42, εάν το σύμβολο που εμφανίζεται είναι το 0, τότε γράψε 1, ενώ εάν το σύμβολο που εμφανίζεται είναι το 1, πήγαινε στην κατάσταση 17 και στην κατάσταση 17, εάν το σύμβολο που εμφανίζεται είναι 0, γράψε 1 και πήγαινε στην κατάσταση 6" κλπ. Στο πρωτότυπο άρθρο ("On computable numbers, with an application to the [[Entscheidungsproblem]]", βλέπε επίσης [[#The Entscheidungsproblem (the "decision problem"): Hilbert's tenth question of 1900|references below]]), ο ΤούρινγκΤιούρινγκ δεν φαντάζεται έναν μηχανισμό, αλλά ένα άτομο το οποίο αποκαλεί ο "υπολογιστής", το οποίο εκτελεί δουλικά αυτούς τους ντετερμινιστικούς μηχανικούς κανόνες(ή όπως το θέτει ο ΤούρινγκΤιούρινγκ με έναν ξεκαρφωτο τρόπο).
 
 
[[Image:Turing machine 2b.svg|thumb|right|300px|Εδώ, η εσωτερική κατάσταση (q<sub>1</sub>) φαίνεται μέσα στην κεφαλή και η εικονογράφηση περιγράφει την περίπτωση που η ταινία είναι άπειρη και γεμάτη με "0", το σύμβολο που αντιστοιχεί στο κενό σύμβολο. Η πλήρης κατάσταση του συστήματος (η πλήρης ....) αποτελείται από την εσωτερική κατάσταση, τα μη-κενά σύμβολα στην ταινία ( σε αυτήν την περίπτωση "11Β"), και την θέση της κεφαλής σε σχέση με όλα τα σύμβολα, περιλαμβανομένων και των κενόν, δηλαδή "011Β". (Drawing after Minsky (1967) p. 121).]]
 
Πιο συγκεκριμένα, μια Μηχανή ΤούρινγκΤιούρινγκ αποτελείται από:
#Μία '''ταινία''' που χωρίζεται σε κελιά, το ένα δίπλα στο άλλο. Κάθε κελί περιέχει ένα σύμβολο από ένα πεπερασμένο αλφάβητο. Το αλφάβητο περιέχει ένα ειδικό ''κενό'' σύμβολο (το οποίο εδώ συμβολίζουμε με "0") και ένα ή παραπάνω άλλα σύμβολα. Υποθέτουμε πώς αυτή η ταινία είναι απείρως επεκτάσιμη προς τα αριστερά και προς τα δεξιά, δηλαδή μία μηχανή ΤούρινγκΤιούρινγκ είναι πάντα προμηθευμένη με όση ταινία της χρειάζεται για τους υπολογισμούς. Κελιά τα οποία δεν έχουν συμπληρωθεί, υποθέτουμε πως είναι εξοπλισμένα με το κενό γράμμα. Σε κάποια μοντέλα, η ταινία έχει αριστερό άκρο, το οποίο είναι εξοπλισμένο με ένα ειδικό σύμβολο, όμως είναι απείρως επεκτάσιμη προς τα δεξιά.
# Μία '''κεφαλή''' που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά. Σε μερικά μοντέλα κινείται μόνο η κεφαλή, ενώ η ταινία παραμένει σταθερή.
#Ένα '''μητρώο καταστάσεων''' που αποθηκεύει μία κατάσταση της Μηχανής Τουρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική ''αρχική'' κατάσταση με την οποία ξεκινά το μητρώο. Αυτές οι καταστάσεις, γράφει ο ΤούρινγκΤιούρινγκ, αντικαθιστούν την "πνευματική κατάσταση" στην οποία αρχικά θα ήταν το άτομο που θα έκανε τους υπολογισμούς.
# Ένας πεπερασμένος '''πίνακας''' (ενίοτε ονομαζόμενος ως '''διαδραστικός πίνακας''' ή '''συνάρτηση μετάβασης''') από οδηγίες (συνήθως πενταπλές [5-tuples] : q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, αλλά μερικές φορές τετραπλές [4-tuples] όπου, δεδομένης της κατάστασης (q<sub>i</sub>) στην όποια βρίσκεται αυτή τη στιγμή η μηχανή, ''και'' το ''σύμβολο'' (a<sub>j</sub>) που διαβάζεται στην ταινία (το σύμβολο που βρίσκεται εκείνη τη στιγμή κάτω από την κεφαλή) ορίζει στη μηχανή να κάνει τα ακόλουθα σε σειρά (για τα πενταπλά μοντέλα):
*Είτε απαλείφει , ή καταγράφει ένα σύμβολο (αντικαθιστώντας το a<sub>j</sub> με το a<sub>j1</sub>), ''και έπειτα''
== Ορισμοί ==
 
Οι Χόπκροφτ και Ούλμαν<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>Q</math> είναι το πεπερασμένο σύνολο ''καταστάσεων'',
* <math>\Gamma</math> είναι το πεπερασμένο σύνολο των επιτρεπτών ''συμβόλων της ταινίας'',
* <math>F \subseteq Q</math> είναι το σύνολο των ''τελικών καταστάσεων'' (final states).
 
Στη βιβλιογραφία έχουν εμφανιστεί διάφοροι ορισμοί λίγο διαφορετικοί μεταξύ τους, συνήθως για να κάνουν την εξήγηση ή τις αποδείξεις πιο απλές, αλλά πάντα η μηχανή που ορίζεται είναι το ίδιο ισχυρή υπολογιστικά. Για παράδειγμα, οι Λιούις και Παπαδημητρίου <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>K</math> είναι ένα πεπερασμένο σύνολο ''καταστάσεων'',
* <math>\Sigma</math> είναι ένα [[αλφάβητο]], που περιέχει το ''κενό σύνολο'' <math>\sqcup</math> και το ''σύμβολο αριστερού τέλους'' <math>\triangleright</math>, αλλά όχι τα σύμβολα <math>\leftarrow</math> και <math>\rightarrow</math>,
# για κάθε <math>q \in K - H</math> και <math>\alpha \in \Sigma</math>, αν <math>\delta(q,\alpha) = (p,b)</math>, τότε <math>b \neq \triangleright</math>.
 
== Επιπλέον πληροφορίες που απαιτούνται για να υλοποιηθούν ή να εφαρμοστούν οι μηχανές ΤούρινγκΤιούρινγκ ==
 
Σύμφωνα με τα λόγια του van Emde Boas (1990) σελ.6: "Το συνολοθεωρητικό αντικείμενο [η κανονική επταπλή περιγραφή που μοιάζει με αυτήν που περιγράφηκε πριν] μας παρέχει μόνο μερικές πληροφορίες σχετικά με το πώς λειτουργεί η μηχανή και πώς θα μοιάζουν οι υπολογισμοί της."
Για παράδειγμα,
*Θα πρέπει να υπάρχουν υπερβολικά πολλές αποφάσεις σχετικά με το πως τα σύμβολα μοιάζουν πραγματικά, και υπάρχουν πολλοί λανθασμένοι τρόποι για να διαβαστούν και να καταγραφούν τα σύμβολα απείρως.
*Οι εντολές αριστερό shift και δεξί shift μπορούν να μετακινούν την κεφαλή κατά μήκος της ταινίας, όμως όταν χτίζεται μια μηχανή ΤούρινγκΤιούρινγκ είναι πρακτικά πιο χρήσιμο να κάνουμε την ταινία να μετακινείται προς τα μπρος και προς τα πίσω, κάτω από τη κεφαλή.
*Η ταινία μπορεί να είναι πεπερασμένου μήκους και αυτόματα να επεκτείνεται με κελιά που περιέχουν το κενό σύμβολο όπου χρειάζεται (κάτι που προσεγγίζει τον μαθηματικό ορισμό), όμως είναι πιο συνηθισμένο να σκεφτόμαστε πως επεκτείνεται απείρως και προς τα δυο άκρα, και πως είναι εξ'αρχής γεμάτο με το κενό σύμβολο, με εξαίρεση κάποια συγκεκριμένα δοσμένα πεπερασμένα φράγματα πάνω από τα οποία βρίσκεται η κεφαλή. (Αυτό φυσικά, δεν είναι εφαρμόσιμο στην πραγματικότητα.) Η ταινία ''δεν μπορεί'' να έχει σταθερό μήκος, μιας και κάτι τέτοιο δεν θα ανταποκρίνεται στον δοσμένο ορισμό και θα περιόριζε σημαντικά το πλήθος των υπολογισμών που μπορεί να κάνει η μηχανή, σε όσους μπορεί να κάνει και ένα [[linear bounded automaton]]
 
Οι ορισμοί στην λογοτεχνία μερικές φορές διαφέρουν ελαφρώς, ώστε να είναι οι προτάσεις και οι αποδείξεις απλούστερες ή πιο ξεκάθαρες, αλλά αυτό γίνεται πάντα με τέτοιο τρόπο ώστε η προκύπτουσα μηχανή να έχει την ίδια υπολογιστική δύναμη. Για παράδειγμα, αλλάζοντας το σύνολο <math>\{L,R\}</math> με το <math>\{L,R,N\}</math>, όπου ''N'' ("Καμία" ή "Χωρίς-Εκτέλεση") θα επέτρεπε στη μηχανή να παραμείνει στο ίδιο κελί της ταινίας, αντί να κινείται δεξιά και αριστερά, δεν αυξάνει την υπολογιστική δύναμη της μηχανής.
 
Η πιο κοινή σύμβαση είναι να αναπαριστάται κάθε "εντολή ΤούρινγκΤιούρινγκ" σε έναν "πίνακα ΤούρινγκΤιούρινγκ" με μία από τις εννιά πενταπλότητες, όπως η σύμβαση των ΤούρινγκΤιούρινγκ/Davis (ΤούρινγκΤιούρινγκ (1936) στο "Undecideable", σελ.126-127 και Davis(2000), σελ.152):
: (ορισμός 1): '''(q<sub>i</sub>, S<sub>j</sub>, S<sub>k</sub>/E/N, L/R/N, q<sub>m</sub>)'''
:: '''(''' παρούσα κατάσταση '''q<sub>i</sub>''' ''',''' σύμβολο που διαβάζεται'''S<sub>j</sub>''' ''',''' σύμβολο που εκτυπώνεται '''S<sub>k</sub>'''/διαγραφή '''E'''/τίποτα '''N''' ''',''' μετακίνηση της ταινίας ένα κελί αριστερά '''L'''/δεξιά '''R'''/κανένα '''N''' ''',''' νέα κατάσταση '''q<sub>m</sub>''' ''')'''
:: '''(''' παρούσα κατάσταση '''q<sub>i</sub>''' ''',''' σύμβολο που διαβάζεται '''S<sub>j</sub>''' ''',''' νέα κατάσταση '''q<sub>m</sub>''' ''',''' εκτύπωση συμβόλου'''S<sub>k</sub>'''/διαγραφή '''E'''/τίποτα '''N''' ''',''' μετακίνηση της ταινίας κατά ένα κελί αριστερά '''L'''/δεξιά '''R'''/καθόλου '''N''' ''')'''
 
Για το υπόλοιπο του άρθρου, θα χρησιμοποιείται ο "ορισμός 1" (ορισμός των ΤούρινγκΤιούρινγκ/Davis)
 
{| class="wikitable" style="text-align: center"
|}
 
Στον επόμενο πίνακα, η αυθεντική μηχανή του ΤούρινγκΤιούρινγκ επέτρεπε μόνο τις τρεις πρώτες γραμμές να εμφανίζονται, τις οποίες ονόμαζε Ν1, Ν2, Ν3 (βλ. ΤούρινγκΤιούρινγκ στο "Undecideable", σελ. 126). Επέτρεπε την διαγραφή του "κελιού που διαβάζεται", ονομάζοντας το 0-νικό σύμβολο S<sub>0</sub> = "διαγραφέα" ή "κενό", κλπ, όμως, δεν επέτρεπε να μην εκτυπωθεί, και έτσι η κάθε γραμμή-εντολή περιλαμβάνει "εκτύπωση συμβόλου S<sub>k</sub>" ή "διαγραφή" (βλ. παραπομπή 12 στο Post (1947), ''Undecideable'' σελ. 300). Οι συντομεύσεις είναι του ΤούρινγκΤιούρινγκ("Undecideable", σελ. 119). Ως επακόλουθο, του πρωτότυπου άρθρου του ΤούρινγκΤιούρινγκ το 1936-1937, οι μηχανές-μοντέλα επιτρέπουν ως και 9 διαφορετικούς τύπους από 5-άδες:
{| class="wikitable" style="text-align: center"
|-
!
! style="width:15%" | Τρέχων μ σχηματισμός(κατάσταση ΤούρινγκΤιούρινγκ)
! Σύμβολο στη ταινία
! Διαδικασία Εκτύπωσης
! Κίνηση της Ταινίας
! style="width:15%" | Τελικός μ σχηματισμός (κατάσταση ΤούρινγκΤιούρινγκ)
! 5-άδα
! 5-άδα σχόλια
|}
 
Οποιοσδήποτε πίνακας ΤούρινγκΤιούρινγκ (κατάλογος εντολών) μπορεί να κατασκευαστεί από τις παραπάνω εννιά 5-άδες. Για τεχνικούς λόγους, οι τρεις εντολές μη-εκτύπωσης ή "Ν" εντολές (4,5,6) μπορούν συνήθως να παραλειφθούν. Για παραδείγματα βλ. [[Turing machine examples]].
 
Λιγότερο συχνά συναντάται η χρήση της 4-άδας: αυτές αναπαριστούν μια περαιτέρω εξατομίκευση των εντολών ΤούρινγκΤιούρινγκ (Post (1947)), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); για περισσότερα βλ. [[Post–Turing machine]].
 
===Η "κατάσταση"===
Η λέξη "κατάσταση" που χρησιμοποείται στο πλαίσιο της μηχανής ΤούρινγκΤιούρινγκ μπορεί να είναι πηγή σύγχυσης, μιας και έχει διπλή σημασία. Οι περισσότεροι σχολιαστές μετά τον ΤούρινγκΤιούρινγκ χρησιμοποιούν την "κατάσταση" για να εννοήσουν το όνομα/προσδιορισμό της τρέχουσας εντολής που πρέπει να εκτελεστεί- δηλ. τα περιεχόμενα του μητρώου κατάστασης. Αλλά ο ΤούρινγκΤιούρινγκ (1936) έκανε μια ισχυρή διάκριση μεταξύ μιας καταγραφής αυτού που ονόμαζε "μ-σχηματισμός" της μηχανής, (της εσωτερικής κατάστασής του)και την "κατάσταση εξέλιξης" της μηχανής (ή του ατόμου)μέσω του υπολογισμού- η τρέχουσα κατάσταση του ολικού συστήματος. Αυτό που ο ΤούρινγκΤιούρινγκ ονόμαζε "φόρμουλα κατάστασης" περιλαμβάνει και την τρέχουσα εντολή και ''όλα'' τα σύμβολα στην ταινία:
 
{{quote|Κατά αυτόν τον τρόπο η κατάσταση εξέλιξης του υπολογισμού σε κάθε στάδιο είναι εντελώς καθορισμένη από το υπόμνημα των εντολών και των συμβόλων στην ταινία. Δηλαδή, η '''κατάσταση του συστήματος''' μπορεί να περιγραφεί από μια απλή έκφραση (ακολουθία συμβόλων) αποτελούμενη από τα σύμβολα στην ταινία ακολουθούμενα από Δ (που υποθέτουμε ότι δεν θα εμφανιστεί αλλού) και έπειτα από το υπόμνημα εντολών. Αυτή η έκφραση ονομάζεται 'φόρμουλα κατάστασης' .|''Undecidable'', σελ.139–140, με έμφαση}}
 
 
Μια παραλλαγή αυτού βλέπουμε στον Kleene (1952) όπου ο [[Stephen Cole Kleene|Kleene]] δείχνει πώς να γράψεις [[Gödel number]] από μια "κατάσταση" μηχανής: τοποθετεί το σύμβολο του q<sub>4</sub> "μ-σχηματισμού" πάνω από το κελί που διαβάζεται περίπου στο κέντρο από τα 6 μη-κενά κελιά στην ταινία (βλέπε την εικόνα της ΤούρινγκΤιούρινγκ-ταινίας σ 'αυτό το άρθρο) και το τοποθετεί στα ''δεξιά'' από το κελί που διαβάζεται. Αλλά ο Kleene αναφέρεται στο "q<sub>4</sub>" ώς την "κατάσταση μηχανής" (Kleene, σελ.&nbsp;374-375). Οι Hopcroft και Ullman καλούν αυτή τη μίξη η "στιγμιαία περιγραφή" και ακολουθούν τη συνήθεια του ΤούρινγκΤιούρινγκ να τοποθετεί την "τρέχουσα κατάσταση" (επιγραφή της εντολής , μ-σχηματισμός) στα ''αριστερά'' του συμβόλου που διαβάζεται (σελ.&nbsp;149).
 
'''Παράδειγμα: η ολική κατάσταση του πολυάσχολου beaver αποτελούμενου από 3-καταστάσεις 2-σύμβολα μετά από 3 "κινήσεις"''' (από το παράδειγμα "run" στο παρακάτω σχήμα):
Αυτό σημαίνει: μετά από τρεις κινήσεις η ταινία έχει ... 000110000 ... πάνω της, η κεφαλή σαρώνει το δεξιότερο 1, και η κατάσταση είναι '''A'''. Τα κενά διαστήματα (σ' αυτήν την περίπτωση αντιπροσωπεύονται με "0") μπορούν να είναι μέρος από την ολική κατάσταση όπως φαίνεται εδώ: '''B'''01; η ταινία έχει ένα μοναδικό 1 πάνω της, αλλά η κεφαλή σαρώνει το "0" ("κενό") στα αριστερά του και η κατάσταση είναι '''B'''.
 
Η "κατάσταση" στο πλαίσιο της μηχανής ΤούρινγκΤιούρινγκ πρέπει να διευκρινιστεί ως προς τι περιγράφεται: (''i'') η τρέχουσα εντολή, ή (''ii'') η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή, ή (''iii'') η λίστα από τα σύμβολα στην ταινία μαζί με την τρέχουσα εντολή τοποθετημένα στα αριστερά ή στα δεξιά από το σύμβολο που διαβάζεται.
Ο βιογράφος του ΤούρινγκΤιούρινγκ Andrew Hodges (1983: 107) σημείωσε και συζήτησε αυτή τη σύγχυση.
 
===Τα διάγραμμα "κατάστασης" της μηχανής ΤούρινγκΤιούρινγκ===
 
{|class="wikitable"
 
 
[[Image:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|Ο πολυάσχολος "beaver" με τις 3-καταστάσεις της μηχανής ΤούρινγκΤιούρινγκ σε μια[[Finite State Machine|πεπερασμένη παράσταση καταστάσεων]]. Κάθε κύκλος αναπαριστά μια "κατάσταση" του πίνακα-έναν "μ-σχηματισμό" ή "εντολή". Η "διεύθυνση" απο μια μετάβαση κατάστασης φαίνεται από ένα βέλος . Η ετικέτα (δηλ. '''0/P,R''') δίπλα στην εξερχόμενη κατάσταση (στην ουρά του βέλους) προσδιορίζει το σύμβολο που διαβάζεται που επιφέρει μια συγκεκριμένη μετάβαση (δηλ. '''0''') ακολουθούμενη από κάθετο '''/''', ακολουθούμενη απο μεταγενέστερες "συμπεριφορές" της μηχανής , δηλ. "'''P''' '''Ε'''κτύπωσε" έπειτα μετακίνησε την ταινία "'''R''' '''Δ'''εξιά". Δεν υπάρχει γενική αποδεκτή φόρμα. Η σύμβαση φαίνεται μετά τους McClusky (1965), Booth (1967), Hill, και Peterson (1974).]]
 
Στα δεξιά: ο παραπάνω πίνακας όπως εκφράζεται σαν διάγραμμα "μετάβαση κατάστασης".
 
Θα έπρεπε να προειδοποιήσουμε τον αναγνώστη ότι τέτοια διαγράμματα αναπαριστούν ένα στιγμιότυπο του πίνακά παγωμένο στο χρόνο , ''όχι'' την πορεία ("τροχιά") ενός υπολογισμού ''διαμέσου'' του χρόνου και/ή του χώρου. Αν και κάθε φορά που η μηχανή πολυάσχολος "beaver" θα "τρέχει" , θα ακολουθεί πάντα την ίδια τροχιά-καταστάσεων, αυτό δεν είναι ισχύει και για το "αντίγραφο" της μηχανής το οποίο μπορεί να εφοδιάζεται με ποικίλες εισερχόμενες "παραμέτρους".
Το διάγραμμα "Εξέλιξη του υπολογισμού" δείχνει την εξέλιξη των καταστάσεων (εντολών) του πολυάσχολου "beaver" 3-καταστάσεων διαμέσου του υπολογισμού του από την αρχή στο τέλος. Στο δεξιό μέρος της εικόνας είναι ο ΤούρινγκΤιούρινγκ "πληρης σχηματισμός" (Kleene "κατάσταση", Hopcroft–Ullman "στιγμιαία περιγραφή") σε κάθε βήμα. Αν η μηχανή έπρεπε να διακοπεί και να καθαριστεί και να αδειάσει τόσο το "μητρώο καταστάσεων" όσο και ολόκληρη η ταινία , αυτοί οι "σχηματισμοί" θα μπορούσαν να χρησιμοποιηθούν για να αναζωπυρωθεί ένας υπολογισμός οπουδήποτε στην εξέλιξη του (από ΤούρινγκΤιούρινγκ (1936) ''Undecidable'' pp.&nbsp;139–140).
 
==Ισοδύναμα μοντέλα με τη μηχανή ΤούρινγκΤιούρινγκ==
Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή ΤούρινγκΤιούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(Hopcroft και Ullman σελ.&nbsp;159, cf Minsky (1967)). Ίσως υπολογίζουν γρηγορότερα, ή χρησιμοποιούν λιγότερη μνήμη ή το σύνολο εντολών τους είναι μικρότερο, αλλά δεν μπορούν να υπολογίσουν ισχυρότερα( δηλ. περισσότερες μαθηματικές συναρτήσεις). (Θυμηθείτε ότι η [[Church–Turing thesis]] ''υποθέτει'' ότι το παρακάτω είναι πραγματικό για κάθε είδους μηχανή: οτιδήποτε μπορεί να "υπολογιστεί", μπορεί να υπολογιστεί από κάποια μηχανή ΤούρινγκΤιούρινγκ.)
 
Μια μηχανή ΤούρινγκΤιούρινγκ είναι ισοδύναμη με ένα [[pushdown automaton]] το οποίο έχει δημιουργηθεί πιο ευέλικτο και συνοπτικό χαλαρώνοντας το κριτήριο [[LIFO (computing)|last-in-first-out]] της στοίβας του.
 
Στο άλλο άκρο, κάποια άλλα απλά μοντέλα μπορούν να αποδειχθούν [[Turing completeness|Turing-equivalent]], δηλ. να έχουν την ίδια υπολογιστική δύναμη όπως το μοντέλο της μηχανής ΤούρινγκΤιούρινγκ.
 
Κοινά ισοδύναμα μοντέλα είναι τα [[multi-tape Turing machine]], [[multi-track Turing machine]], μηχανές με είσοδο και έξοδο, και το [[Non-deterministic Turing machine|''non-deterministic'' Turing machine]] (NDTM) που αντιτίθεται στην ''ντετερμινιστική'' μηχανή ΤούρινγκΤιούρινγκ(DTM) στην οποία κάθε πίνακας πράξεων έχει το πολύ μια είσοδο για κάθε συνδυασμό από σύμβολα και καταστάσεις.
 
Οι μηχανές [[Read-only right moving Turing machines|Read-only, right-moving Turing machines]] είναι ισοδύναμες με μη προσδιοριστά πεπερασμένα αυτόματα ([[Nondeterministic finite automaton|NDFAs]]) (καθώς και με προσδιοριτστά πεπερασμένα αυτόματα ([[Deterministic finite automaton|DFAs]]) με μετατροπή χρησιμοποιώντας τον αλγόριθμο [[NDFA to DFA conversion algorithm]]).
Για πρακτικούς και διδακτικούς λόγους η ισοδύναμη [[register machine]] μπορεί να χρησιμοποιηθεί σαν μια συνηθισμένη [[Assembly language|assembly]] [[Γλώσσα προγραμματισμού]].
 
==Γενικές μηχανές ΤούρινγκΤιούρινγκ==
[[File:Model of a Turing machine.jpg|thumb|Μια εφαρμογή της μηχανής ΤούρινγκΤιούρινγκ]]
Όπως έγραψε ο ΤούρινγκΤιούρινγκ στο ''Undecidable'', σελ.&nbsp;128 (με πλάγια γράμματα):
{{quote|Είναι πιθανό να εφευρεθεί μια «απλή μηχανή» η οποία μπορεί να χρησιμοποιηθεί για να υπολογίζει «οποιαδήποτε» υπολογίσιμη ακολουθία. Αν αυτή η μηχανή '''U''' τροφοδοτηθεί με την ταινία, στην αρχή της οποίας γράφεται από κάποια υπολογιστική μηχανή '''M''' η σειρά των πεντάδων διαχωριζόμενες με ερωτηματικά, τότε η '''U''' θα υπολογίσει την ίδια σειρά με την '''M'''.}}
 
Αυτή η ανακάλυψη θεωρείται πλέον δεδομένη, αλλά στον καιρό του (1936) θεωρήθηκε εκπληκτική. Το μοντέλο του υπολογισμού το οποίο καλεί ο ΤούρινγκΤιούρινγκ «γενική μηχανή» —"'''U'''" για συντομία—, θεωρείται από κάποιους (βλέπε Davis (2000)) ότι είναι η θεμελιώδης θεωρητική επανάσταση, που οδήγησε στη θεωρία του [[stored-program computer]].
 
{{quote|Η εργασία του ΤούρινγκΤιούρινγκ ... περιέχει, στην ουσία ,την εφεύρεση των σύγχρονων υπολογιστών και μερικών τεχνικών προγραμμάτων που τους συνόδευσαν .|Minsky (1967),σελ. 104}}
 
Στην έννοια του [[computational complexity]], μια γενική μηχανή ΤούρινγκΤιούρινγκ με πολλαπλή-ταινία χρειάζεται μόνο να είναι πιο αργή από [[Λογάριθμος|λογαριθμικό]] παράγοντα σε σύγκριση με τις μηχανές που προσομοιώνει. Αυτό το αποτέλεσμα μαθεύτηκε το 1966 από τους F. C. Hennie και [[R. E. Stearns]]. (Arora και Barak, 2009, θεώρημα 1.9)
 
==Σύγκριση με αληθινές μηχανές==
[[File:Lego Turing Machine.jpg|thumb|Η πραγματοποίηση μιας μηχανής ΤούρινγκΤιούρινγκ με τουβλάκια LEGO]]
 
Συχνά λέγεται πως οι μηχανές ΤούρινγκΤιούρινγκ, αντίθετα με τα απλούστερα αυτόματα, είναι τόσο ισχυρές όσο και οι πραγματικές μηχανές, και πως είναι ικανές να εκτελέσουν οποιοδήποτε εγχείρημα θα μπορούσε και ένα πραγματικό πρόγραμμα να εκτελέσει. Αυτό που παραβλέπεται στην παραπάνω δήλωση είναι το γεγονός πως μια πραγματική μηχανή μπορεί να έχει πεπερασμένες το πλήθος ''διαμορφώσεις'', οπότε αυτή η "πραγματική μηχανή" δεν είναι τίποτα παραπάνω από ένα [[linear bounded automaton]].Από την άλλη πλευρά, οι μηχανές ΤούρινγκΤιούρινγκ είναι ισοδύναμες με μηχανές που έχουν απεριόριστη χωρητικότητα για τους υπολογισμούς τους. Στην πραγματικότητα, οι μηχανές ΤούρινγκΤιούρινγκ δεν χρησιμοποιούνται για να μοντελοποιούν υπολογιστές, αλλά για να μοντελοποιούν κατευθείαν τον υπολογισμό. Ιστορικά, οι υπολογιστές που είναι ικανοί να κάνουν υπολογισμούς χρησιμοποιώντας την εσωτερική (σταθερή) χωρητικότητα, αναπτύχθηκαν αργότερα.
 
Υπάρχουν πολλοί τρόποι για να εξηγηθεί το γιατί οι μηχανές ΤούρινγκΤιούρινγκ είναι χρήσιμες σαν μοντέλα των πραγματικών υπολογιστών:
# Οτιδήποτε μπορεί να υπολογίσει ένας πραγματικός υπολογιστής, μπορεί να το υπολογίσει και μια μηχανή ΤούρινγκΤιούρινγκ. Για παράδειγμα: "Μία μηχανή ΤούρινγκΤιούρινγκ μπορεί να προσομοιώσει οποιαδήποτε υπορουτίνα εμφανίζεται και σε μια προγραμματιστική γλώσσα, συμπεριλαμβανομένων και των επαναληπτικών διαδικασιών και κάθε μορφής γνωστών μηχανισμών προώθησης παραμέτρων" (Hopcroft και Ullman σελ. 157). Ένα αρκετά μεγάλο FSA μπορεί επίσης να μοντελοποιήσει οποιοδήποτε πραγματικό υπολογιστή, ανεξάρτητα IO. Όμως μια δήλωση σχετικά με τους περιορισμούς σε μια μηχανή ΤούρινγκΤιούρινγκ, ισχύει και για τους πραγματικούς υπολογιστές.
#Η διαφορά βρίσκεται μόνο στο πώς μπορεί μια μηχανή ΤούρινγκΤιούρινγκ να χειριστεί μια απεριόριστη ποσότητα δεδομένων. Παρόλ' αυτά, δοσμένου κάποιου πεπερασμένου χρόνου, μια μηχανή ΤούρινγκΤιούρινγκ (όπως και μια αληθινή μηχανή) μπορεί να χειριστεί μόνο ένα πεπερασμένο πλήθος δεδομένων.
#Όπως μια μηχανή ΤούρινγκΤιούρινγκ, μια πραγματική μηχανή μπορεί να επεκτείνει την χωρητικότητα της όταν χρειάζεται, αξιοποιώντας περισσότερους δίσκους ή μέσα αποθήκευσης. Εάν η διαθεσιμότητα αυτών μειωθεί, μειώνεται και η χρησιμότητα της μηχανής ΤούρινγκΤιούρινγκ ως μοντέλο. Η αλήθεια όμως είναι πώς ούτε οι μηχανές ΤούρινγκΤιούρινγκ, ούτε οι πραγματικές μηχανές χρειάζονται αστρονομικές ποσότητες αποθηκευτικού χώρου για να μπορέσουν να εκτελέσουν χρήσιμους υπολογισμούς. Ο χρόνος εκτέλεσης που απαιτείται είναι συνήθως ένα μεγαλύτερο πρόβλημα.
 
#Οι περιγραφές προγραμμάτων πραγματικών μηχανών που χρησιμοποιούν πιο απλά γενικά μοντέλα είναι συνήθως πιο περίπλοκες απ'ότι οι περιγραφές που χρησιμοποιούν οι μηχανές ΤούρινγκΤιούρινγκ. Για παράδειγμα, μια μηχανή ΤούρινγκΤιούρινγκ που περιγράφει έναν αλγόριθμό μπορεί να έχει μερικές εκατοντάδες καταστάσεις, ενώ ένα αντίστοιχο ντετερμινιστικό πεπερασμένο αυτόματο (DFA) μιας συγκεκριμένης αληθινής μηχανής θα έχει τετράκις εκατομμύρια. Το γεγονός αυτό κάνει την ανάλυση της DFA αναπαράστασης ακατόρθωτη.
#Οι μηχανές ΤούρινγκΤιούρινγκ περιγράφουν αλγορίθμους ανεξάρτητα από το πόσο μνήμη χρησιμοποιούν. Υπάρχει ένα όριο στην μνήμη που καταλαμβάνεται από κάθε συνήθη μηχανή, αλλά αυτό το όριο μπορεί να αυξηθεί αυθαιρέτως στον χρόνο. Οι μηχανές ΤούρινγκΤιούρινγκ μας επιτρέπουν να κάνουμε δηλώσεις για αλγορίθμους οι οποίοι μπορεί (θεωρητικά) να τρέχουν για πάντα, ανεξάρτητα από την πρόοδο στην αρχιτεκτονική των ''συμβατικών'' υπολογιστικών μηχανών.
#Οι μηχανές ΤούρινγκΤιούρινγκ απλοποιούν την δήλωση των αλγορίθμων. Οι αλγόριθμοι που τρέχουν σε μια γενική μηχανή ισοδύναμη μιας μηχανής ΤούρινγκΤιούρινγκ είναι συνήθως πιο γενικοί από τους αντίστοιχους που τρέχουν σε πραγματικές μηχανές, γιατί έχουν διαθέσιμους διαφορετικούς τύπους αυθαίρετης ακρίβειας και δεν έρχονται ποτέ αντιμέτωποι με απρόσμενες συνθήκες (συμπεριλαμβανομένης, χωρίς όμως να τις περιορίζει, της περίπτωσης να ξεμείνουν από μνήμη ([[out of memory]]) ).
 
Ένας λόγος για τον οποίο οι μηχανές ΤούρινγκΤιούρινγκ μπορούν να θεωρηθούν "φτωχές" είναι ότι αρκετά πραγματικά προγράμματα, όπως τα λειτουργικά συστήματα ([[operating system]]s) και οι επεξεργαστές κειμένου ([[word processor]]s), γράφονται για να δέχονται απεριόριστες εισαγωγές μέσα στο χρόνο και γι'αυτό δεν σταματούν. Οι μηχανές ΤούρινγκΤιούρινγκ δεν μπορούν να μοντελοποιήσουν καλά τέτοιους συνεχείς υπολογισμούς (μπορούν όμως να μοντελοποιήσουν κομμάτια αυτών, όπως ανεξάρτητες διαδικασίες).
[[File:Turingmachine.jpg|thumb| Ένα πειραματικό πρωτότυπο για να επιτευχθεί η μηχανή ΤούρινγκΤιούρινγκ]]
 
===Περιορισμοί των μηχανών ΤούρινγκΤιούρινγκ===
 
====Υπολογιστική θεωρία πολυπλοκότητας====
Ένα περιορισμός των μηχανών ΤούρινγκΤιούρινγκ είναι ότι δεν μπορούν να μοντελοποιήσουν καλά την δύναμη ενός συγκεκριμένου εγχειρήματος.Για παράδειγμα, οι μοντέρνοι υπολογιστές αποθηκευμένου προγράμματος (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 και στέλνει στον εαυτό της ένα μήνυμα ξεκίνα. Όταν λαμβάνει ένα μήνυμα σταμάτα, σταματάει με έναν απεριόριστο αριθμό στην τοπική της μνήμη.)
 
 
== Εξωτερικοί σύνδεσμοι ==
{{Commonscat|Turing machines}}
* [http://aturingmachine.com/index.php Υλοποίηση μηχανής ΤούρινγκΤιούρινγκ]
 
{{Ενσωμάτωση κειμένου|en|Turing machine}}
8.695

επεξεργασίες