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

 

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

 

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

 

Για πρακτικούς και διδακτικούς λόγους η ισοδύναμη [[register machine]] μπορεί να χρησιμοποιηθεί σαν μια συνηθισμένη [[Assembly language|assembly]] [[Γλώσσα προγραμματισμού]].

 

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