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

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

{{further2|[[Computational complexity theory]]}}

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