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

 

==Άτυπη Περιγραφή==

Η Μηχανή Τούρινγκ μοντελοποιεί μαθηματικώς μια μηχανή που μηχανικά χειρίζεται μια ταινία. Πάνω σε αυτήν την ταινία υπάρχουν σύμβολα, τα οποία η μηχανή μπορεί να διαβάσει και να καταγράψει, ένα τη φορά, χρησιμοποιώντας μια κεφαλή. Η λειτουργία της καθορίζεται από ένα πεπερασμένο σύνολο στοιχειωδών εντολών όπως "στην κατάσταση 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]]), ο Τούρινγκ δεν φαντάζεται έναν μηχανισμό, αλλά ένα άτομο το οποίο αποκαλεί ο "υπολογιστής", το οποίο εκτελεί δουλικά αυτούς τους ντετερμινιστικούς μηχανικούς κανόνες(ή όπως το θέτει ο Τούρινγκ με έναν ξεκαρφωτο τρόπο).

 

 

==Ισοδύναμα μοντέλα με τη μηχανή Τούρινγκ==

Για πολλές μηχανές που θα μπορούσαν να έχουν περισσότερη υπολογιστική ικανότητα από μια απλή γενική μηχανή Τούρινγκ μπορεί να δειχθεί ότι δεν έχουν περισσότερη δύναμη(Hopcroft και Ullman σελ. 159, cf Minsky (1967)). Ίσως υπολογίζουν γρηγορότερα, ή χρησιμοποιούν λιγότερη μνήμη ή το σύνολο εντολών τους είναι μικρότερο, αλλά δεν μπορούν να υπολογίσουν ισχυρότερα( δηλ. περισσότερες μαθηματικές συναρτήσεις). (Θυμηθείτε ότι η [[Church–Turing thesis]] ''υποθέτει'' ότι το παρακάτω είναι πραγματικό για κάθε είδους μηχανή: οτιδήποτε μπορεί να "υπολογιστεί", μπορεί να υπολογιστεί από κάποια μηχανή Τούρινγκ.)

 

 

==Γενικές μηχανές Τούρινγκ==

[[File:Model of a Turing machine.jpg|thumb|Μια εφαρμογή της μηχανής Τούρινγκ]]

Όπως έγραψε ο Τούρινγκ στο ''Undecidable'', σελ. 128 (με πλάγια γράμματα):

 

====Υπολογιστική θεωρία πολυπλοκότητας====

Ένα περιορισμός των μηχανών Τούρινγκ είναι ότι δεν μπορούν να μοντελοποιήσουν καλά την δύναμη ενός συγκεκριμένου εγχειρήματος.Για παράδειγμα, οι μοντέρνοι υπολογιστές αποθηκευμένου προγράμματος (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 μοντέλο, αντί για το μοντέλο της μηχανής Τούρινγκ.