Τα όρια του Υπολογισµού και η Πολυπλοκότητα: Οι θεµελιώσεις της Επιστήµης των Υπολογιστών

Περίληψη

Στις αρχές του αιώνα µας, ένας από τους µεγαλύτερους µαθηµατικούς, ο David Hilbert,
στα πλαίσια της περίφηµης διάλεξής του στο ∆ιεθνές Συνέδριο Μαθηµατικών στο
Παρίσι το 1900 αναφέρθηκε σε 23 ανοικτά προβλήµατα τα οποία θεωρούσε ως τα πιο
σηµαντικά για εκείνη την εποχή. Το δέκατο από αυτά ρωτούσε εάν µπορούσε να βρεθεί
µια διαδικασία που να απαντά στο εάν µία δοσµένη διοφαντική εξίσωση έχει λύση ή
όχι. Αρκετά χρόνια µετά, το 1928, στο ∆ιεθνές Συνέδριο Μαθηµατικών στη Μπολόνια
και ως συνέχεια της προηγούµενης διάλεξής του, έθετε το πρόβληµα του να βρεθεί
διαδικασία που θα µπορούσε να ελέγχει εάν ένα µαθηµατικό (λογικό) σύστηµα, όπως
είναι για παράδειγµα η Ευκλείδειος Γεωµετρία, είναι συνεπές, δηλαδή δεν εµπεριέχει
αντιφάσεις. Είναι προφανές το πόσο χρήσιµη θα ήταν µια τέτοια διαδικασία, καθώς
ένας µαθηµατικός που προτείνει ένα πολύπλοκο µαθηµατικό σύστηµα, το οποίο λόγω
του όγκου των αξιωµάτων ή της πληθώρας των αποδεικτικών µεθόδων που περιέχει
ξεφεύγει από την δυνατότητα ελέγχου από τον άνθρωπο, απλά θα τροφοδοτούσε (µε
µια κατάλληλη αναπαράσταση) το µαθηµατικό του σύστηµα στη µηχανική διαδικασία
και η διαδικασία θα απαντούσε στο ερώτηµα του αν το σύστηµα αυτό περικλείει
αντιφάσεις. Ένα άλλο πρόβληµα που έθεσε ο Hilbert στη διάλεξή του το 1928 και που
ήταν κατά κάποιον τρόπο γενίκευση του δέκατου προβλήµατος της διάλεξης του 1900,
ήταν δοθέντος ενός µαθηµατικού συστήµατος να διαπιστωθεί εάν µια δοσµένη
µαθηµατική πρόταση αποτελεί θεώρηµα του συστήµατος ή όχι, το περίφηµο
Entscheidungsproblem. Ο Hilbert ήλπιζε ότι για τα παραπάνω προβλήµατα θα έπρεπε
να υπήρχε κάποια διαδικασία που να τα απαντά µέσα σε πεπερασµένο αριθµό βηµάτων
(περατοκρατική διαδικασία ή αλγόριθµος, όπως θα δούµε πιο κάτω).