ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ,

ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ,

Υπάρχει ένας κουρέας σε ένα χωρίο ο όποιος ξυρίζει οποιανδήποτε δεν ξυρίζεται μονός του. Έχουμε ακριβή περιγραφή του κουρέα. Υποθέτουμε ότι τίθεται το ερώτημα κατά ποσό ο κουρέας ξυρίζεται μονός του. Εάν ο κουρέας ξυρίζεται μονός του , τότε δεν θα πρέπει να ξυρίζεται μονός του (γιατί ξυρίζεται μόνο όσους δεν ξυρίζονται μονοί τους). Από την άλλη μεριά εάν ο κουρέας δεν ξυρίζεται μονός του τότε θα πρέπει να ξυρίζεται μονός του (γιατί ξυρίζει όσους δεν ξυρίζονται μόνοι τους). Έχουμε αντίφαση. Είναι λάθος ο τρόπος που καθορίσαμε τον κουρέα. Καταλήγουμε ότι δεν είναι δυνατόν να υπάρχει τέτοιος κουρέας RUSSELL ΚΑΙ ΜΗ ΥΠΟΛΟΓΙΣΙΜΟΤΗΤΑ




Το θεώρημα της μη πληρότητας, αποδεικνύει ουσιαστικά ότι ακόμη και στα μαθηματικά, το απώτατο προπύργιο του ορθολογισμού, η αποδεικτική δύναμη της Λογικής έχει όρια. Ότι δηλαδή σε κάθε θεωρία, όσο καλο-δομημένη κι αν είναι, με όσα μη αντιφατικά αξιώματα κι αν εξοπλισθεί, θα μείνουν πάντα αλήθειες μη-αποδείξιμες, απροσπέλαστες απ’ τη μέθοδο του «ένα και ένα κάνουν δύο». Αυτό φυσικά διόλου δεν σημαίνει ότι το θεώρημα δείχνει πως η Λογική είναι σαθρό εργαλείο. Καθόλου. Βάζει όμως φραγμό στην παντοδυναμία της.

Το θεώρημα της μη πληρότητας έχει στενή συγγένεια με αρκετά αποτελέσματα σχετικά με τα μη αποφασίσιμα σύνολα στη θεωρία αναδρομής, η οποία αποτελεί κεντρικό πυλώνα της επιστήμης υπολογιστών.

Ο Στίβεν Κλέινι (Stephen Cole Kleene) το 1943 παρουσίασε μία απόδειξη του θεωρήματος της μη πληρότητας του Γκέντελ χρησιμοποιώντας βασικά αποτελέσματα της θεωρίας υπολογισμού. Ένα τέτοιο αποτέλεσμα δείχνει ότι το πρόβλημα τερματισμού δεν έχει λύση: δεν υπάρχει πρόγραμμα υπολογιστή που δοθέντος ενός προγράμματος Π ως είσοδο, να μπορεί να αποφασίσει σωστά αν το Π τελικά σταματά όταν τρέξει χωρίς είσοδο. Ο Κλέινι έδειξε ότι η ύπαρξη μιας πλήρους, αποτελεσματικής θεωρίας της αριθμητικής με συγκεκριμένες ιδιότητες συνέπειας θα σήμαινε πως το πρόβλημα του τερματισμού είναι αποφασίσιμο (υπολογίσιμο), μια αντίφαση. Η μη υπολογισιμότητα μπορεί επομένως να περιγραφεί ως συνέπεια της μη πληρότητας του Γκέντελ.

Από μια άλλη άποψη το θεώρημα αυτό δείχνει πως για να μπορέσει να καταλάβει πλήρως το σύμπαν πρέπει να το θεωρήσει παρατηρώντας το από μια θέση έξω απ' αυτό. Μέσα στο σύμπαν υπάρχουν όρια για την κατανόηση του. Μήπως λοιπόν είναι ανώφελο να ψάχνουμε για να βρούμε όλες τις απαντήσεις για τον Κόσμο μας; μήπως τα μυστικά του Κόσμου είναι καλά κρυμμένα για τις οντότητες που είναι μέσα σε αυτόν;