10.4 Αναδρομικά απαριθμήσιμα (α.α.) σύνολα.

Ορισμός 10.3   (Αναδρομικά απαριθμήσιμο σύνολο) Ένα μη κενό σύνολο $A \subseteq {\mathbb{N}}$ ονομάζεται αναδρομικά απαριθμήσιμο (α.α.) αν υπάρχει πρόγραμμα $P(x)$ που να απαριθμεί τα στοιχεία του $A$, δηλ. να έχουμε

$$A = {\left\{{P(1), P(2), P(3), \ldots}\right\}},$$

με ενδεχόμενη επανάληψη των στοιχείων του $A$ στο δεξί μέλος. Με άλλα λόγια, για κάθε $a \in A$ υπάρχει $n \in {\mathbb{N}}$, όχι κατ' ανάγκη μοναδικό, τέτοιο ώστε $a = P(n)$.

Παρατήρηση 10.1   Και πάλι, δεν υπάρχει, στον Ορισμό 10.3, τίποτα το μαγικό με το σύνολο ${\mathbb{N}}$ και θα μπορούσαμε στη θέση του να έχουμε, π.χ. το σύνολο $\Sigma^*$, όπου $\Sigma$ ένα πεπερασμένο αλφάβητο.

Είναι σχεδόν άμεσο ότι κάθε αναδρομικό σύνολο είναι και α.α. Πράγματι, αν $\emptyset \neq A \subseteq {\mathbb{N}}$ είναι αναδρομικό τότε υπάρχει πρόγραμμα $Q(x)$ τέτοιο ώστε $Q(x)=1 \Leftrightarrow x \in A$. Τότε το ακόλουθο πρόγραμμα απαριθμεί τα στοιχεία του $A$.$m$ είναι, π.χ., το μικρότερο στοιχείο του $A$):

def P(x):
	if Q(x):
		return x
	else:
		return m

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

Από την άλλη μεριά είναι εύκολο να κατασκευάσουμε α.α. σύνολα που δεν είναι αναδρομικά. Για παράδειγμα, το σύνολο

$$A = {\left\{{x\in{\mathbb{N}}: \pi(x)\downarrow}\right\}}$$

δεν είναι αναδρομικό (αν ήταν τότε το πρόβλημα του τερματισμού θα ήταν υπολογίσιμο, ενώ έχουμε δείξει ότι δεν είναι) αλλά είναι α.α. Για να δούμε αυτό τον τελευταίο ισχυρισμό κάνουμε το εξής. Χρειαζόμαστε ένα πρόγραμμα που να απαριθμεί τα $x \in {\mathbb{N}}$ για τα οποία το πρόγραμμα $\pi(x)$ τερματίζει. Ισοδύναμα, φτιάχνουμε ένα πρόγραμμα που λειτουργεί επ' άπειρον και τυπώνει συνέχεια στην έξοδό του στοιχεία του $A$, χωρίς να παραλείψει κανένα. Το πρόγραμμα αυτό

• Βήμα 1: Πρώτα τρέχει (προσομοιώνει) το πρόγραμμα $\pi(1)$ για 1 βήμα.
• Βήμα 2: Έπειτα τρέχει (προσομοιώνει) τα προγράμματα $\pi(1), \pi(2)$ για 2 βήματα το καθένα
• $\ldots$
• Βήμα $k$: Τρέχει τα προγράμματα $\pi(1), \pi(2), \ldots, \pi(k)$ για $k$ βήματα το καθένα,
• Συνεχίζει έτσι επ' άπειρον.

Στο τέλος του βήματος $k$ το πρόγραμμά μας ελέγχει ποια από τα προγράμματα $\pi(1),\ldots,\pi(k)$ τελείωσαν μέσα στα πρώτα $k$ τους βήματα, και τυπώνει τα αντίστοιχα $x$ για αυτά που τελείωσαν στην έξοδό του. Είναι έτσι φανερό ότι κάθε $x$ για το οποίο $\pi(x)\downarrow$ θα εμφανιστεί στην έξοδο του προγράμματός μας, και ότι σε αυτή την έξοδο εμφανίζονται μόνο τέτοια $x$ (δηλ. στοιχεία του $A$). Αν $x \in A$ και το πρόγραμμα $\pi(x)$ τερματίζει μετά από $t$ βήματα τότε ο αριθμός $x$ εμφανίζεται για πρώτη φορά στην έξοδο του προγράμματός μας μετά το βήμα υπ' αριθμόν $\max{\left\{{x, t}\right\}}$, και εμφανίζεται και σε όλα τα μεταγενέστερα βήματα.

Έχουμε λοιπόν δείξει:

Θεώρημα 10.3   Κάθε αναδρομικό σύνολο είναι αναδρομικά απαριθμήσιμο αλλά το αντίστροφο δεν ισχύει.

Η ιεραρχία των γλωσσών τώρα γίνεται

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

και όλοι οι εγκλεισμοί είναι γνήσιοι.

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

Θεώρημα 10.4   $A \subseteq {\mathbb{N}}$ είναι αναδρομικό αν και μόνο αν τα $A, A^c$ είναι και τα δύο α.α.

Απόδειξη. Αν το $A$ είναι αναδρομικό τότε αναδρομικό είναι και το $A^c$, άρα και τα δύο είναι α.α. Αντίστροφα τώρα, έστω ότι τα $A, A^c$ είναι και τα δύο α.α., και ότι τα προγράμματα $P$ και $Q$ τα απαριθμούν, έχουμε δηλ.

$$A = {\left\{{P(1), P(2), \ldots }\right\}}, A^c = {\left\{{Q(1), Q(2), \ldots }\right\}}.$$

Το παρακάτω πρόγραμμα $R(x)$, που χρησιμοποιεί τα $P$ και $Q$ ως υποπρογράμματα, επιστρέφει 1 αν $x \in A$ και 0 αλλιώς.

def R(x):
	i=1
	while True:
		if P(i) == x:
			return 1
		if Q(i) == x:
			return 0
		i = i+1

Το πρόγραμμα $R$ απλούστατα παράγει όλους τους αριθμούς $P(1), Q(1), P(2), Q(2), \ldots$ και μόλις εμφανιστεί το $x$ επιστρέφει 0 ή 1 ανάλογα με το αν το $x$ εμφανίστηκε στην έξοδο του $Q$ ή του $P$. Είναι σίγουρο ότι το $x$ κάποτε θα εμφανιστεί (μια και είτε θα ανήκει στο $A$ είτε στο $A^c$) και άρα για κάθε $x$ το πρόγραμμα $R(x)$ τερματίζει. $\qedsymbol$

Θεώρημα 10.5   Ένα σύνολο $A \subseteq {\mathbb{N}}$ είναι α.α. αν και μόνο αν υπάρχει πρόγραμμα $Q(x)$ τέτοιο ώστε

• Αν $x \in A$ τότε $Q(x)=1$, και
• Αν $x \notin A$ τότε $Q(x)=0$ ή $Q(x) \uparrow$.

Το πρόγραμμα $Q$ στο θεώρημα λέει την αλήθεια για το αν $x \in A$, αν τελειώνει, μπορεί όμως και να τρέχει επ' άπειρον (αλλά αυτό μπορεί να συμβαίνει μόνο αν $x \in A$. Παρατηρήστε ότι υπάρχει ασυμμετρία στις δύο περιπτώσεις $x \in A$ και $x \notin A$, και αυτή η ασυμμετρία εκδηλώνεται και με το ότι υπάρχουν α.α. σύνολα που τα συμπληρώματά τους δεν είναι α.α.

Απόδειξη. Έστω ότι το πρόγραμμα $P$ απαριθμεί τα στοιχεία του $A$:

$$A = {\left\{{P(1), P(2), \ldots}\right\}}.$$

Ορίζουμε το πρόγραμμα $Q(x)$ ως εξής:

def Q(x):
	i=1
	while True:
		if P(i)==x:
			return 1
		i = i+1

Το πρόγραμμα $Q(x)$ επιστρέφει 1 αν και μόνο αν το $x$ εμφανιστεί στη λίστα των τιμών του $P$, αλλιώς τρέχει επ' άπειρον.

Η άλλη κατεύθυνση του Θεωρήματος 10.5 αφήνεται ως άσκηση. $\qedsymbol$

Άσκηση 10.4   Αποδείξτε την κατεύθυνση του Θεωρήματος 10.5 που λείπει από την απόδειξη που δόθηκε παραπάνω.