Αλγόριθμοι: Διαφορά μεταξύ των αναθεωρήσεων

Παρόλο που η θεωρία υπολογισμού είχε προφανείς και θεμελιώδεις εφαρμογές στην επιστήμη
των υπολογιστών, η γνώση ότι ένα πρόβλημα μπορεί θεωρητικά να επιλυθεί σε υπολογιστή δεν
είναι αρκετή αν αυτό δεν είναι πρακτικά εφαρμόσιμο. Για παράδειγμα, ένα πρόγραμμα που
παίζει σκάκι, μπορεί θεωρητικά να γραφτεί και δεν είναι πολύ δύσκολο. Υπάρχει πεπερασμένος
αριθμός διάταξης των κξομματιών του σκάκι και το παιχνίδι θα τερματίσει μετά από
πεπερασμένο αριθμό κινήσεων αφού ακολουθηθούν συγκεκριμένοι κανόνες, με τις αντίστοιχες κινήσεις του άλλου παίκτη κοκ μέχρι τελικά το παιχνίδι να τελειώσει. Έτσι ο υπολογιστής
αφού γνωρίζει τις δυνατές συνέπειες κάθε κίνησης διαλέγει την καλύτερη. Ένα τέτοιο
πρόγραμμα δεν μπορεί να τρέξει γιατί ο αριθμός των δυνατών κινήσεων (προσεγγιστικά
10**19) είναι τόσο μεγάλος που το πρόγραμμα θα διαρκέσει χιλιάδες χρόνια.