10.1 Υπολογίσιμες συναρτήσεις και αναδρομικά σύνολα

Μέχρι στιγμής έχουμε δει ουσιαστικά δύο κατηγορίες γλωσσών: τις κανονικές (regular) γλώσσες και τις context free γλώσσες. Η πρώτη κατηγορία περιέχεται στη δεύτερη. Από τη μέχρι στιγμής παρουσίαση πρέπει να έχει φανεί καθαρά ότι για κάθε μια από τις δύο κατηγορίες υπάρχει και ένα αντίστοιχο υπολογιστικό μοντέλο: τα πεπερασμένα αυτόματα (ντετερμινιστικά ή μη) για τις κανονικές γλώσσες και τα αυτόματα με στοίβα (push-down automata) για τις context free γλωσσες. Η αντιστοιχία στην οποία αναφερθήκαμε είναι ότι μια γλώσσα είναι στην κατηγορία που εξετάζουμε (κανονική ή context-free) αν και μόνο αν υπάρχει μια μηχανή του αντίστοιχου τύπου (πεπερασμένο αυτόματο ή αυτόματο με στοίβα) που αναγνωρίζει τη γλώσσα αυτή.

Είδαμε ότι το να υπάρχει ένα DFA για μια γλώσσα $L$ είναι ισοδύναμο με το μπορεί κανείς να γράψει ένα πρόγραμμα σε μια γλώσσα προγραμματισμού (ας πούμε σε python) που να αναγνωρίζει τις λέξεις της $L$ (να επιστρέφει δηλ. το πρόγραμμα αυτό 1 αν η λέξη που του δώσαμε ανήκει στην $L$ και 0 αλλιώς), το οποίο δε χρησιμοποιεί απεριόριστη μνήμη αλλά μνήμη μεγέθους σταθερού και προκαθορισμένου, το ίδιο για όλες τις λέξεις της $L$. Ισοδύναμα, μιλάμε για ένα πρόγραμμα σε python που χρησιμοποιεί ένα σταθερό αριθμό μεταβλητών (όχι πίνακες) η καθεμία από τις οποίες χρησιμοποιεί προκαθορισμένη μνήμη (π.χ. ακέραιοι των 32 bits - δυαδικών ψηφίων).

Αντίστοιχα, ένα ντετερμινιστικό αυτόματο με στοίβα είναι ακριβώς ένα πρόγραμμα σε python που χρησιμοποιεί μεν πεπερασμένη μνήμη μόνο, αλλά έχει και πρόσβαση σε μια άπειρη στοίβα με ένα περιορισμένο όμως τρόπο, που του επιτρέπει να διαβάζει και να τροποποιεί πάντα μόνο την κορυφή της στοίβας. Τα ντετερμινιστικά αυτόματα με στοίβα δεν αρκούν για να αναγνωρίσουν όλες τις context free γλώσσες όμως, αλλά μπορεί κανείς με λίγη προσοχή να δείξει ότι και τα μη ντετερμιστικά αυτόματα με στοίβα έχουν ισοδύναμα python προγράμματα.

Είναι πλέον φυσιολογικός ο ακόλουθος ορισμός.

Ορισμός 10.1   (Υπολογίσιμη συνάρτηση) Έστω $\Sigma$ ένα πεπερασμένο αλφάβητο. Μια συνάρτηση $f: \Sigma^* \to \Sigma^*$ λέγεται υπολογίσιμη συνάρτηση αν υπάρχει ένα python πρόγραμμα P που με είσοδο $x \in \Sigma^*$ επιστρέφει τη λέξη $f(x)$.

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

Ας παρατηρήσουμε εδώ ότι δεν υπάρχει κάτι μαγικό που να μας επιβάλλει το $\Sigma^*$ σα πεδίο ορισμού και πεδίο τιμών στον παραπάνω ορισμό. Στη θέση του θα μπορούσε k να είναι οποιοδήποτε σύνολο που τα στοιχεία του να μπορούν να παρασταθούν, με κάποιο τρόπο, στον υπολογιστή (ένα τέτοιο σύνολο δεν είναι το σύνολο ${\mathbb{R}}$ των πραγματικών αριθμών). Αυτό όμως σημαίνει ουσιαστικά ότι μπορούμε να γράψουμε κάτω μια λέξη από 0 ή 1 που να αντστοιχεί μοναδικά σε ένα στοιχείο του συνόλου αυτού. Πολλές φορές βλέπει κανείς τον ορισμό της υπολογίσιμης συνάρτησης να δίνεται π.χ. για συναρτήσεις από τους φυσικούς αριθμούς στους φυσικούς. Εμείς με τον όρο υπολογίσιμη συνάρτηση θα καταλαβαίνουμε οποιαδήποτε απεικόνιση την οποία μπορούμε να υπολογίζουμε χρησιμοποιώντας ένα πρόγραμμα.

Για παράδειγμα οι παρακάτω συναρτήσεις είναι υπολογίσιμες αφού εύκολα βλέπει κανείς ότι υπάρχουν προγράμματα που τις υπολογίζουν.

$$x \to x + 1 ({\mathbb{N}}\to{\mathbb{N}}),$$

$$x \to x^2 ({\mathbb{N}}\to{\mathbb{N}}).$$

Ορισμός 10.2   (Αναδρομικό σύνολο) Έστω $\Sigma$ ένα πεπερασμένο αλφάβητο. Ένα σύνολο $L \subseteq \Sigma^*$ λέγεται αναδρομικό αν η χαρακτηριστική του συνάρτηση

$$\chi_L(x) = {\bf 1}\left(x \in L\right)$$

(ισούται με 1 αν $x \in L$, αλλιώς ισούται με 0) είναι υπολογίσιμη.

Και πάλι τη θέση του $\Sigma^*$ μπορεί να πάρει οποιοδήποτε σύνολο του οποίου τα στοιχεία μπορούν να παρασταθούν στον υπολογιστή, π.χ. το σύνολο ${\mathbb{N}}$ των φυσικών αριθμών. Ένα σύνολο λοιπόν λέγεται αναδρομικό αν μπορούμε να γράψουμε ένα πρόγραμμα που να αποφασίζει πότε ένα στοιχείο $x$ ανήκει στο σύνολο ή όχι. Για παράδειγμα, το σύνολο των πρώτων αριθμών (εκείνοι οι φυσικοί αριθμοί που δεν έχουν κανένα φυσικό αριθμό ως διαιρέτη, εκτός από τον εαυτό τους και τη μονάδα) είναι ένα αναδρομικό σύνολο, αφού μπορούμε να γράψουμε ένα πρόγραμμα που να να αποφασίζει αν ένας δοσμένος φυσικός αριθμός είναι πρώτος ή όχι, εξετάζοντας κάθε μικρότερό του φυσικό αριθμό για το αν διαιρεί το δοσμένο φυσικό ή όχι. Αυτό σίγουρα δεν είναι το «καλύτερο» πρόγραμμα που μπορεί κανείς να γράψει για αυτό το σκοπό, αλλά πάντως δουλεύει.

Είναι τώρα φανερό ότι οι κανονικές και οι context free γλώσσες είναι αναδρομικά σύνολα, αφού υπάρχουν προγράμματα που τις «αποφασίζουν». Η ιεραρχία των γλωσσών που έχουμε μέχρι τώρα δεί λοιπόν είναι η

(κανονικές γλώσσες) $\subset$ (context free γλώσσες) $\subset$ (αναδρομικές γλώσσες).

Και οι δύο παραπάνω εγκλεισμοί είναι γνήσιοι, υπάρχει δηλ. context free γλώσσα που δεν είναι κανονική (π.χ. η γλώσσα των παλίνδρομων λέξεων $xx^R$ πάνω από ένα αλφάβητο) και αναδρομική γλώσσα που δεν είναι context free. Ένα παράδειγμα για το τελευταίο αποτελεί η γλώσσα ${\left\{{a^nb^nc^n: n\in{\mathbb{N}}}\right\}}$. Γι' αυτήν έχουμε δει στην §9.7 ότι δεν είναι context free γλώσσα, ενώ είναι αρκετά απλό να γράψει κανείς ένα python πρόγραμμα που να αναγνωρίζει πότε μια λέξη είναι της μορφής $a^nb^nc^n$. Ένα τέτοιο πρόγραμμα απλά μετράει το πλήθος των $a$.$b$ και $c$ και ελέγχει ότι είναι ίδια, καθώς και ότι όλα τα $b$ έρχονται μετά από όλα τα $a$ κι όλα τα $c$ μετά τα $b$.

Είναι σημαντικό να τονίσουμε εδώ ότι η μεταβλητή του python προγράμματος όπου κρατιέται, π.χ., το πλήθος των $a$, είναι μια μεταβλητή για την οποία χρειαζόμαστε απεριόριστη μνήμη. Δεν είναι δηλ. δυνατόν να προκαθορίσουμε ένα άνω όριο για το πλήθος αυτό. Και επειδή ο φυσικός αριθμός $x$ χρειάζεται περίπου $\log_2 x$ δυαδικά ψηφία για να παρασταθεί στον υπολογιστή, κι επειδή η συνάρτηση $\log_2 x$ αυξάνει (αν και αργά) χωρίς όριο όταν $x \to \infty$, αυτό το python πρόγραμμα δεν χρησιμοποιεί σταθερή μνήμη (αν αυτό συνέβαινε τότε η γλώσσα αυτή θα ήταν κανονική, ενώ δεν είναι καν context free).

Άσκηση 10.1   Αν τα σύνολα $A, B \subseteq {\mathbb{N}}$ είναι αναδρομικά δείξτε ότι το ίδιο ισχύει και για τα σύνολα $A\cap B, A \cup B, A^c$.