Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
|||
Γραμμή 1:
[[εικόνα:Turing machine.png|thumb|right|250px|]]
Η '''Μηχανή Τούρινγκ''' είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωναα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε [[αλγόριθμος|αλγορίθμου]], και ειναι ιδιαίτερα χρήσιμη στο να εξηγεί τις λειτουργίες μιας [[CPU|κεντρικής μονάδας επεξεργασίας]] στο εσωτερικό του υπολογιστή.
Η μηχανή του Τούρινγκ εφευρέθηκε το 1936 απο τον [[Άλαν Τούρινγκ]].<ref>
Η ιδέα ήρθε σ 'αυτόν στα μέσα του 1935 μετά από μια ερώτηση που έθεσε ο [[Μ. HA Newman]] στις διαλέξεις του: "Υπήρχε μια συγκεκριμένη μέθοδο, ή όπως το έθεσε Newman, μια μηχανική διαδικασία'''', η οποία θα μπορούσε να εφαρμοστεί σε μια μαθηματική δήλωση, η οποία θα απαντούσε αν ήταν αποδείξιμη "</ref> Η μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.
Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:
<blockquote>
....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χαραγμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή, ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της ειναι εν μέρει αποφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της μηχανής. Παρόλα αυτά, η ταινία μπορεί να μετακινηθεί μπρος και πίσω μέσα στη μηχανή, όντας μια στοιχειώδη πράξη της μηχανής.
</blockquote>
Μια μηχανή Τούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή Τούρινγκ λέγεται [[Καθολική Μηχανή Τούρινγκ]] (ή απλά '''καθολική μηχανή'''). Ένας πιο μαθηματικός ορισμός με παρόμοια "καθολική" φύση τέθηκε από τον [[Αλόνζο Τσερτς]], του οποίου η εργασία πάνω στο [[λογισμός λάμδα|λογισμό λάμδα]] συνυφαίνεται με αυτή του Τούρινγκ σε μια τυπική θεωρία [[υπολογισμός|υπολογισμού]] που είναι γνωστή ως η [[θέση Τσερτς-Τούρινγκ]]. Η θέση λέει ότι οι μηχανές Τούρινγκ όντως εμπεριέχουν την ανεπίσημη έννοια της αποδοτικής μεθόδου στη λογική και τα μαθηματικά, και δίνουν έναν ακριβή ορισμό ενός [[αλγόριθμος|αλγορίθμου]] ή μιας ''μηχανικής διαδικασίας''.
| |||