Θεωρία υπολογισμού
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Η θεωρία υπολογισμού είναι ο κλάδος της επιστήμης υπολογιστών που πραγματεύεται με το εάν, και το πόσο αποδοτικά μπορούν να λυθεί κάποιο πρόβλημα σε ένα υπολογιστικό μοντέλο, με χρήση ενός αλγορίθμου. Ο τομέας διαιρείται σε δύο κύριους κλάδους: την θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, αλλά και οι δύο αφορούν τα μοντέλα υπολογισμού.
Για να πραγματοποιήσουν μια εξονυχιστική μελέτη των υπολογισμών, οι επιστήμονες υπολογιστών αντιμετωπίζουν τον υπολογιστή ως μια αφηρημένη μαθηματική έννοια, που λέγεται μοντέλο υπολογισμού. Υπάρχουν διάφορες διατυπώσεις που χρησιμοποιούνται, αλλά η πιο συχνή είναι η μηχανή Τούρινγκ. Μπορεί κανείς να θεωρήσει τη μηχανή Τούρινγκ σαν ένα προσωπικό υπολογιστή με άπειρη μνήμη, αν και μπορεί να την προσπελάσει μόνο σε μικρά διακριτά κομμάτια. Οι επιστήμονες υπολογιστών μελετούν τη μηχανή Τούρινγκ γιατί έχει απλή διατύπωση και μπορούν να την αναλύσουν, να την χρησιμοποιήσουν σε αποδείξεις, και λόγω του ότι κατά πολλούς αντιπροσωπεύει το πιο ισχυρό εφικτό μοντέλο υπολογισμού. Αν και η άπειρη μνήμη μπορεί να θεωρηθεί ανέφικτη, στην πραγματικότητα κάθε πρόβλημα που λύνει η μηχανή Τούρινγκ χρειάζεται πάντα πεπερασμένη μνήμη, άρα κάθε πρόβλημα που μπορεί να λυθεί από μια μηχανή Τούρινγκ, θα μπορούσε να λυθεί από έναν προσωπικό υπολογιστή που έχει αρκετή μνήμη.
- Το άρθρο αντλεί πληροφορίες από το αντίστοιχο της αγγλόφωνης Wikipedia.