10.2 Μη υπολογίσιμες συναρτήσεις

Είναι πολύ φυσιολογικό το ερώτημα αν υπάρχουν συναρτήσεις που να μην είναι υπολογίσιμες. Για να συγκεκριμενοποιήσουμε τα πράγματα, ένα φυσιολογικό ερώτημα είναι αν υπάρχει συνάρτηση $f:{\mathbb{N}}\to{\mathbb{N}}$ για την οποία να μη μπορούμε να γράψουμε ένα πρόγραμμα που να την υπολογίζει.

Θεώρημα 10.1   Υπάρχει συνάρτηση $f:{\mathbb{N}}\to{\mathbb{N}}$ για την οποία δεν υπάρχει πρόγραμμα που να την υπολογίζει.

Απόδειξη. Η πρώτη παρατήρηση που κάνουμε είναι ότι το σύνολο των υπολογισίμων συναρτήσεων είναι αριθμήσιμο, μπορεί δηλ. κάποιος να γράψει κάτω όλες τις υπολογίσιμες συναρτήσεις ${\mathbb{N}}\to{\mathbb{N}}$ σε μια ακολουθία

$$f_1, f_2, \ldots, f_n, \ldots$$

(δεν υποθέτουμε εδώ ότι $f_i \neq f_j$ για $i \neq j$, αλλά επιτρέπουμε τις επαναλήψεις στην λίστα αυτή όλων των υπολογισίμων συναρτήσεων). Αυτό είναι άμεση συνέπεια του ότι το σύνολο όλων των προγραμμάτων είναι αριθμήσιμο. Πράγματι, αν το υποθέσουμε αυτό ως γνωστό δεν έχουμε παρά να απαριθμήσουμε όλα τα προγράμματα και για κάθε ένα από αυτά γράφουμε κάτω ποια συνάρτηση υπολογίζει (αν υπολογίζει συνάρτηση, αλλιώς δε γράφουμε τίποτα). Κάθε υπολογίσιμη συνάρτηση θα εμφανιστεί τότε στη λίστα μια και κάποια στιγμή θα εξετάσουμε ένα από τα προγράμματα που την υπολογίζουν.

Γιατί είναι τώρα το σύνολο όλων των προγραμμάτων αριθμήσιμο; Απλούστατα, κάθε πρόγραμμα δεν είναι παρά μια, συνήθως μεγάλη, λέξη πάνω από ένα συγκεκριμένο αλφάβητο $\Sigma$. Για παράδειγμα, όλα τα προγράμματα σε python γράφονται στο αλφάβητο που χρησιμοποιούν οι σύγχρονοι υπολογιστές και που περιλαμβάνει όλα τα λατινικά γράμματα, μικρά και κεφαλαία, δίαφορα σημεία στίξης, αριθμητικούς και άλλους τελεστές, ψηφία, κλπ. Απαριθμούμε πρώτα λοιπόν όλες τις λέξεις μήκους 1, μετά όλες τις λέξεις μήκους 2, όλες τις λέξεις μήκους 3, κ.ο.κ., και για κάθε λέξη που παράγουμε την αναφέρουμε στη λίστα των προγραμμάτων, αν αυτή είναι πρόγραμμα (πληροί δηλ. τους συντακτικούς κανόνες της γλώσσας προγραμματισμού που χρησιμοποιούμε). Μπορούμε να το κάνουμε αυτό ακριβώς επειδή όλες οι λέξεις πάνω από το $\Sigma$ μήκους $k$ είναι φυσικά πεπερασμένες σε πλήθος, και άρα κάποια στιγμή τελειώνουμε την απαρίθμηση των λέξεων μήκους $k$ και προχωράμε στην απαρίθμηση των λέξεων μήκους $k+1$. Κάθε πρόγραμμα λοιπόν θα εμφανιστεί στη λίστα μας κάποια στιγμή ανάλογα και με το ποιο είναι το μήκος του. Έχουμε λοιπόν μέχρι στιγμής δείξει ότι το πλήθος όλων των υπολογισίμων συναρτήσεων είναι αριθμήσιμο.

Η απόδειξη του θεωρήματος συμπληρώνεται από το ότι το πλήθος όλων των συναρτήσεων από το ${\mathbb{N}}$ στο ${\mathbb{N}}$ δεν είναι αριθμήσιμο, δε μπορούμε δηλ. να διατάξουμε όλες αυτές τις συναρτήσεις σε μια ακολουθία

$$g_1, g_2, \ldots, g_n, \ldots$$

Αν μπορούσαμε τότε ας κοιτάξουμε τη συνάρτηση

$$f(k) = g_k(k)+1.$$

Αυτή είναι προφανώς μια συνάρτηση από το ${\mathbb{N}}$ στο ${\mathbb{N}}$ άρα, αφού υποθέσαμε ότι όλες οι συναρτήσεις αυτές βρίσκονται στη λίστα $g_i$, υπάρχει κάποιο $i \in {\mathbb{N}}$ τέτοιο ώστε $f(k) = g_i(k)$ για κάθε $k \in {\mathbb{N}}$. Αυτό σημαίνει $g_k(k)+1 = g_i(k)$. Διαλέγοντας $k=i$ παίρνουμε άτοπο. (Το παραπάνω επιχείρημα ονομάζεται «διαγώνιο επιχείρημα» και βρίσκεται «πίσω» από τις περισσότερες αποδείξεις μη αριθμησιμότητας ενός συνόλου.) $\qedsymbol$

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

Αυτός είναι ένας κλασικός τρόπος απόδειξης στα μαθηματικά, η «υπαρξιακή απόδειξη», που αν και είναι αρκετά εύκολος και αποδεικνύει αυτό που θέλουμε, δεν είναι τόσο ικανοποιητικός επειδή αποδεικνύεται η ύπαρξη ενός αντικειμένου με ορισμένες ιδιότητες, αλλά, συνήθως, δεν προσδιορίζεται με κάποιο τρόπο κάποιο τέτοιο αντικείμενο. Στην προκειμένη περίπτωση γνωρίζουμε πλέον, μετά την απόδειξη του Θεωρήματος 10.1, ότι υπάρχουν συναρτήσεις από τους φυσικούς στους φυσικούς που δεν είναι υπολογίσιμες, αλλά δε γνωρίζουμε καμία συγκεκριμένη τέτοια συνάρτηση. Θα δούμε αργότερα συγκεκριμένα παραδείγματα που για το καθένα θα έχουμε και ιδιαίτερο τρόπο απόδειξης του ότι δεν είναι υπολογίσιμα.

Άσκηση 10.2   Δεν υπάρχει κάποιος ιδιαίτερος λόγος που στο Θεώρημα 10.1 αναφερόμαστε σε συναρτήσεις ${\mathbb{N}}\to{\mathbb{N}}$. Δείξτε, για παράδειγμα, ότι υπάρχουν συναρτήσεις ${\mathbb{N}}\to {\left\{{0,1}\right\}}$ και $\Sigma^*\to\Sigma^*$, που δεν είναι υπολογίσιμες ($\Sigma$ είναι ένα πεπερασμένο αλφάβητο).