Μηχανή Τούρινγκ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μΧωρίς σύνοψη επεξεργασίας Ετικέτα: επεξεργασία κώδικα 2017 |
μ Αυτόματη διόρθωση ορθογραφικών |
||
Γραμμή 1:
[[εικόνα:Turing machine.png|thumb|right|250px|]]
Η '''Μηχανή Τούρινγκ''' είναι μια υποθετική συσκευή η οποία χειρίζεται σύμβολα σύμφωνα με ένα σύνολο κανόνων. Παρά την απλότητά της, μια Μηχανή Τούρινγκ μπορεί να προσαρμοστεί ώστε να προσομοιώνει την λογική οποιουδήποτε [[αλγόριθμος|αλγορίθμου]], και
Η μηχανή του Τούρινγκ εφευρέθηκε το 1936
Η ιδέα ήρθε σ 'αυτόν στα μέσα του 1935 μετά από μια ερώτηση που έθεσε ο [[Μ. HA Newman]] στις διαλέξεις του: "Υπήρχε μια συγκεκριμένη μέθοδο, ή όπως το έθεσε Newman, μια μηχανική διαδικασία'''', η οποία θα μπορούσε να εφαρμοστεί σε μια μαθηματική δήλωση, η οποία θα απαντούσε αν ήταν αποδείξιμη "</ref> Η μηχανή Τούρινγκ δεν προορίζεται σαν μια τεχνολογία υπολογιστών αλλά κυρίως σαν μια υποθετική κατασκευή που αντιπροσωπεύει μια υπολογιστική μηχανή. Οι μηχανές Τούρινγκ βοηθούν τους επιστήμονες να καταλάβουν τα όρια του μηχανικού υπολογισμού.
Ο Τούρινγκ έδωσε έναν περιληπτικό ορισμό του πειράματος στην έκθεση του, "Ευφυή μηχανήματα". Έγραψε ότι η μηχανή Τούρινγκ, που εδώ ονομάζεται μια Λογική Υπολογιστική Μηχανή, αποτελείται από:
<blockquote>
....απεριόριστη χωρητικότητα μνήμης, σε μορφή μιας άπειρης ταινίας η οποία είναι χωρισμένη σε τετράγωνα, πάνω στο καθένα από οποία μπορεί να εκτυπωθεί ένα σύμβολο. Κάθε στιγμή, υπάρχει ένα σύμβολο στη μηχανή και ονομάζεται το σκαναριζόμενο σύμβολο. Η μηχανή μπορεί να μεταβάλλει το σκαναριζόμενο σύμβολο και η συμπεριφορά της
</blockquote>
Γραμμή 25:
# Ένας πεπερασμένος '''πίνακας''' (ενίοτε ονομαζόμενος ως '''διαδραστικός πίνακας''' ή '''συνάρτηση μετάβασης''') από οδηγίες (συνήθως πενταπλές [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>), ''και έπειτα''
*Μετακινεί την κεφαλή (η οποία περιγράφεται
*Θεωρεί την ίδια ή μια ''καινούργια κατάσταση'' όπως ορίζεται ( πηγαίνει στην κατάσταση q<sub>i1</sub>).
Στο τετραπλό μοντέλο , η απαλοιφή ή η καταγραφή ενός συμβόλου (a<sub>j1</sub>) και η μετακίνηση της κεφαλής αριστερά ή δεξιά (d<sub>k</sub>) καθορίζονται ως ξεχωριστές εντολές. Συγκεκριμένα , ο πίνακας λέει στη μηχανή (ia) να διαγράψει ή να καταγράψει ένα σύμβολο ''ή'' (ib) να κινήσει την κεφαλή αριστερά ή δεξιά , ''και έπειτα'' (ii) να θεωρήσει την ίδια ή καινούργια κατάσταση όπως ορίζεται , άλλα όχι και τις 2 ενέργειες ia) , ib), στην ίδια εντολή. Σε μερικά μοντέλα , αν δεν υπάρχει καταγραφή στον πίνακα για τον τρέχοντα συνδυασμό συμβόλων και καταστάσεων, η μηχανή θα σταματήσει. Άλλα μοντέλα απαιτούν όλα τα κελιά να είναι γεμάτα.
Γραμμή 304:
[[Image:State diagram 3 state busy beaver 2B.svg|thumb|500px|right|Ο πολυάσχολος "beaver" με τις 3-καταστάσεις της μηχανής Τούρινγκ σε μια[[Finite State Machine|πεπερασμένη παράσταση καταστάσεων]]. Κάθε κύκλος αναπαριστά μια "κατάσταση" του πίνακα-έναν "μ-σχηματισμό" ή "εντολή". Η "διεύθυνση"
Στα δεξιά: ο παραπάνω πίνακας όπως εκφράζεται σαν διάγραμμα "μετάβαση κατάστασης".
| |||