Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων

 

Για να πραγματοποιήσουν μια εξονυχιστική μελέτη της έννοιας του υπολογισμού, οι επιστήμονες αξιοποιούν διάφορες διατυπώσεις υπολογιστικών μοντέλων, αλλά συνηθέστερη είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναν [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη [[μνήμη]], αν και η μνήμη αυτή είναι προσβάσιμη μόνο κατά μικρά διακριτά τμήματα. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή μαθηματική διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, ενώ κατά πολλούς αντιπροσωπεύει το ισχυρότερο εφικτό μοντέλο υπολογισμού. Αυτό σημαίνει ότι ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά αν και μόνο αν υπάρχει μηχανή Τούρινγκ που το επιλύει. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή με επαρκή μνήμη.