Η '''θεωρία υπολογισμού''' είναι ο κλάδος της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]] που πραγματεύεται με το εάν, και το πόσο αποδοτικά μπορούνμπορεί να λυθεί κάποιο πρόβλημα σε ένα [[υπολογιστικό μοντέλο]], με χρήση ενός [[αλγόριθμος|αλγορίθμου]]. Ο τομέας διαιρείται σε δύο κύριους κλάδους: την [[θεωρία υπολογισιμότητας]] και τη [[θεωρία πολυπλοκότητας]], αλλά και οι δύο αφορούν τα [[μοντέλο υπολογισμού|μοντέλα υπολογισμού]].
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη των υπολογισμών, οι επιστήμονες υπολογιστών αντιμετωπίζουν τον υπολογιστή ως μια αφηρημένη μαθηματική έννοια, που λέγεταιτο μοντέλο υπολογισμού. Υπάρχουν διάφορες διατυπώσεις που χρησιμοποιούνται, αλλά η πιο συχνή είναι η [[μηχανή Τούρινγκ]]. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν έναέναν [[προσωπικός υπολογιστής|προσωπικό υπολογιστή]] με άπειρη μνήμη, αν και μπορείη ναμνήμη τηναυτή προσπελάσειείναι προσβάσιμη μόνο σε μικρά διακριτά κομμάτιατμήματα. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή μαθηματική διατύπωση και μπορούν να την αναλύσουν, να τηντη χρησιμοποιήσουν σε αποδείξεις, και λόγω του ότιενώ κατά πολλούς αντιπροσωπεύει το πιο ισχυρό εφικτό μοντέλο υπολογισμού. Αυτό σημαίνει ότι ένα πρόβλημα μπορεί να λυθεί αλγοριθμικά μόνο αν υπάρχει μηχανή Τούρινγκ που το επιλύει. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή με επαρκή μνήμη.
== Τυπική Γραμματική ==
Γραμμή 56:
== Βιβλιογραφία ==
''Στοιχεία ΘεωρίαΘεωρίας Υπολογισμού'', Harry Lewis και Χρήστος Παπαδημητρίου, Εκδόσεις Κριτική
