Η μηχανή Turing

Η Μηχανή Τούρινγκ είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. H μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.

Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:

....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της είναι εν μέρει απόφαση αυτού του συμβόλου, αλλά τα σύμβολα σε άλλα σημεία της ταινίας δεν επηρεάζουν την συμπεριφορά της.

Μια μηχανή Τούρινγκ που μπορεί να προσομοιώσει μια οποιαδήποτε άλλη μηχανή Τούρινγκ λέγεται Καθολική Μηχανή Τούρινγκ (ή απλά καθολική μηχανή).

Μια Μηχανή Τούρινγκ αποτελείται από:

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

· Μία κεφαλή (read/write head) που μπορεί να διαβάζει και να γράφει σύμβολα πάνω στην ταινία και που μπορεί να μετακινεί την ταινία κατά ένα (και μόνο ένα) κελί κάθε φορά.

· Ένα μητρώο καταστάσεων (state register )που αποθηκεύει μία κατάσταση της Μηχανής Τουρινγκ, μία από ένα πεπερασμένο πλήθος. Ανάμεσα σε αυτές είναι η ειδική αρχική κατάσταση με την οποία ξεκινά το μητρώο.

· Ένα πεπερασμένος πίνακας οδηγιών (finite table of instructions) όπου, δεδομένης της κατάστασης στην όποια βρίσκεται αυτή τη στιγμή η μηχανή, και το σύμβολο που διαβάζεται στην ταινία (το σύμβολο που βρίσκεται εκείνη τη στιγμή κάτω από την κεφαλή) ορίζει στη μηχανή να κάνει τα ακόλουθα σε σειρά):

Είτε απαλείφει, είτε καταγράφει ένα σύμβολο και έπειτα

Μετακινεί την κεφαλή (ο πίνακας μπορεί να έχει τιμές : 'L' για ένα βήμα αριστερά ή 'R' για ένα βήμα δεξιά ή 'N' για να μείνει στο ίδιο μέρος), και έπειτα

Θεωρεί την ίδια ή μια καινούργια κατάσταση όπως ορίζεται.

* Πηγή: Μηχανή Τούρινγκ. (2022, Αυγούστου 31). Βικιπαίδεια, Η Ελεύθερη Εγκυκλοπαίδεια. Ανακτήθηκε 13:45, Απριλίου 18, 2023 από το //el.wikipedia.org/w/index.php?title=%CE%9C%CE%B7%CF%87%CE%B1%CE%BD%CE%AE_%CE%A4%CE%BF%CF%8D%CF%81%CE%B9%CE%BD%CE%B3%CE%BA&oldid=9646267.