10.3 Το Halting Problem. Άλλα μη αποφασίσιμα προβλήματα στα Μαθηματικά.

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

$$\Sigma = {\left\{{b_7b_6\cdots b_1b_0: b_i \in {\left\{{0,1}\right\}}, i=0,\ldots,7}\right\}}.$$

Αυτές είναι όλες οι λέξεις (bytes) με οκτώ δυαδικά ψηφία (bits) η κάθε μία και πολλές φορές ταυτίζουμε το συγκεκριμένο αλφάβητο με τους αριθμούς $0,\ldots,255$. Ένα πρόγραμμα $P$ λοιπόν είναι μια λέξη

$$P = w_1 \cdots w_N, w_i \in \Sigma$$

και δεν έχουμε παρά να αντικαταστήσουμε κάθε $w_i$ με τα δυαδικά του ψηφία ώστε να γράψουμε το $P$ σα μια δυαδική λέξη με $8N$ δυαδικά ψηφία

$$P = b_{8N-1} b_{8N-2} \cdots b_1 b_0$$

την οποία λέξη μπορούμε να ερμηνεύσουμε ως ένα φυσικό αριθμό, που τον συμβολίζουμε στο εξής ως $\alpha(P)$. Αντίστροφα, αν $n$ είναι ένας φυσικός αριθμός τον γράφουμε στο δυαδικό σύστημα και συμπληρώνουμε με μηδενικά (από τα αριστερά) το πλήθος των ψηφίων του αν χρειάζεται ώστε να είναι πολλαπλάσιο του 8, έστω $8k$. Κάθε μια από τις $k$ οκτάδες τώρα τη βλέπουμε σαν ένα στοιχείο του $\Sigma$ και ο αριθμός μας γίνεται τώρα μια λέξη του $\Sigma^*$. Αν αυτή η λέξη είναι ένα συντακτικά σωστό πρόγραμμα σε python τότε ονομάζουμε αυτό το πρόγραμμα $\pi(n)$, αν όχι, θέτουμε $\pi(n)$ να είναι το πρόγραμμα return True. (Η επιλογή αυτού του τελευταίου προγράμματος είναι τελείως τυχαία. Θα μπορούσαμε αντί γι' αυτό να επιστρέφουμε οποιοδήποτε άλλο.)

Η απεικόνιση $P \to \alpha(P)$ είναι εύκολο να δεί κανείς ότι είναι ένα προς ένα (αλλά όχι επί, αφού δεν είναι όλοι οι αριθμοί κωδικοποιήσεις συντακτικά σωστών προγραμμάτων), και ότι η απεικόνιση $n \to \pi(n)$ δεν είναι ένα προς ένα, αφού μπορεί δύο προγράμματα να μοιάζουν διαφορετικά αλλά να κάνουν την ίδια δουλειά, να υπολογίζουν δηλαδή την ίδια συνάρτηση. Είναι επίσης σημαντικό το ότι και οι δύο απεικονίσεις είναι υπολογίσιμες. Το ότι η $\alpha(P)$ είναι υπολογίσιμη είναι φανερό, ενώ το μόνο λεπτό σημείο όσον αφορά την υπολογισιμότητα της $\pi(n)$ είναι στο κομμάτι όπου πρέπει να ελέγξουμε αν η λέξη του $\Sigma^*$ που προκύπτει είναι συντακτικά σωστό python πρόγραμμα ή όχι. Το να αποδείξουμε ότι κάτι τέτοιο είναι υπολογστικά εφικτό σημαίνει ουσιαστικά να γράψουμε ένα πρόγραμμα που να αναγνωρίζει αν ένα κομμάτι κειμένου (μια λέξη του $\Sigma^*$) είναι ένα σωστό συντακτικά python πρόγραμμα ή όχι. Τέτοια προγράμματα όμως υπάρχουν και χρησιμοποιούνται ευρέως αφού αποτελούν το πρώτο τμήμα των compilers ή interpreters (μεταφραστών) που παίρνουν ένα πρόγραμμα σε python και παράγουν από αυτό ένα ισοδύναμο πρόγραμμα σε «γλώσσα μηχανής».

Προσομοίωση. Θα χρειαστούμε επίσης το εξής: Υπάρχει ένα πρόγραμμα $S(n,x,t)$ το οποίο (α) βρίσκει το πρόγραμμα $P = \pi(n)$ και (β) «Τρέχει» το πρόγραμμα $P(x)$ για τόσα βήματα όσα λέει ο αριθμός $t$ ή επ άπειρον αν ο αριθμός $t$ είναι αρνητικός. Αν και όταν το πρόγραμμα $P(x)$ τελειώσει το $S(n,x,t)$ επιστρέφει ότι επέστρεψε το $P(x)$. Δε θα δείξουμε την ύπαρξη αυτού του προγράμματος που προσμομοιώνει άλλα προγράμματα, μια και τέτοια προγράμματα υπάρχουν και χρησιμοποιούνται ευρέως στον προγραμματισμό (π.χ. interpreters, debuggers, κλπ).

Είμαστε έτοιμοι τώρα να αναφερθούμε στο Halting problem (πρόβλημα τερματισμού). Αυτό ρωτάει απλά αν υπάρχει ένα πρόγραμμα που να μπορεί να αποφασίζει αν ένα τυχόν άλλο πρόγραμμα που εμείς του προσδιορίζουμε θα τερματίσει ή όχι.

Είναι φανερό ότι υπάρχουν προγράμματα που δεν τερματίζουν ποτέ, π.χ. το παρακάτω.

def P(x):
	while True:
		x = 1
	return 1

Ένα τέτοιο πρόγραμμα θα ήταν εξαιρετικά χρήσιμο αν υπήρχε. Φανταστείτε να έχετε ένα python interpreter ο οποίος όχι μόνο θα μετάφραζε το πρόγραμμά σας σε γλώσσα μηχανής αλλά θα μπορούσε και να σας πει εκ των προτέρων αν το πρόγραμμά σας θα έπεφτε σε άπειρο βρόχο (loop) ή όχι. Δυστυχώς όμως τέτοιο πρόγραμμα δεν υπάρχει.

Στο εξής, για τυχόν πρόγραμμα $P$, θα γράφουμε $P \downarrow$ αν το πρόγραμμα $P$ τερματίζει και $P \uparrow$ αν το $P$ τρέχει επ' άπειρον.

Θεώρημα 10.2   Η συνάρτηση

$$H(n, x) = \left\{ \begin{array}{ll} 1 & \alpha\nu (\pi(n... ...ow\\ 0 & \alpha\nu (\pi(n))(x) \uparrow \end{array}\right.$$

δεν είναι υπολογίσιμη.

Απόδειξη. Ας υποθέσουμε ότι η συνάρτηση $H(n, x)$ είναι υπολογίσιμη και ας συμβολίσουμε με $P$ το πρόγραμμα που την υπολογίζει. Φτιάχνουμε τώρα το πρόγραμμα $Q(x)$ που χρησιμοποιεί το $P$ ως υποπρόγραμμα:

def Q(x):
	if P(x, x)==0:
		return 1
	else:
		while True:
			x = 1 # This does nothing and runs forever

Το πρόγραμμα $Q(x)$ που ορίσαμε έχει την ιδιότητα ότι τερματίζει αν και μόνο αν το $(\pi(x))(x)$ δεν τερματίζει.

Ποια είναι η συμπεριφορά του προγράμματος $Q(\alpha(Q))$; Τερματίζει ή όχι; Σύμφωνα με τη προηγούμενη παρατήρηση τερματίζει αν και μόνο αν το πρόγραμμα $(\pi(\alpha(Q)))(\alpha(Q))$ δεν τερματίζει. Αλλά $\pi(\alpha(Q)) = Q$, οπότε δείξαμε ότι το πρόγραμμα $Q(\alpha(Q))$ τερματίζει αν και μόνο αν δεν τερματίζει, πράγμα προφανώς αδύνατο. Το συμπέρασμα είναι ότι η συνάρτηση $H$ δεν είναι υπολογίσιμη. $\qedsymbol$

Έχουμε λοιπόν δείξει ότι η, πολύ φυσιολογική, συνάρτηση $H(n, x)$ που διακρίνει πότε το πρόγραμμα $\pi(n)$ τερματίζει με input $x$ ή όχι δεν είναι υπολογίσιμη. Έχουμε λοιπόν τώρα μια απόδειξη του ότι υπάρχουν μη υπολογίσιμες συναρτήσεις που είναι αρκετά πιο συγκεκριμένη από την προηγούμενη υπαρξιακή απόδειξη του Θεωρήματος 10.1. Μπορεί βέβαια και πάλι να πει κανείς ότι η $H(x)$ δεν έχει ίσως και τόσο ενδιαφέρον από μαθηματική άποψη μια και είναι μια συνάρτηση «κομμένη και ραμμένη» στα μέτρα της Θεωρίας Υπολογισμών, και άρα όχι, ίσως, τόσο φυσιολογική.

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

1. Δεν υπάρχει αλγόριθμος που να αποφασίζει αν ένα δοσμένο πολυώνυμο με ακεραίους συντελεστές (και οποιοδήποτε πλήθος από μεταβλητές)
   $$P(x_1,\ldots,x_n) = \sum_{0\le j_1,\ldots,j_n \le D} c_{j_1,\ldots,j_n} x_1^{j_1} \cdots x_n^{j_n}, c_{j_1,\ldots,j_n} \in {\mathbb{Z}},$$
   έχει λύση (ρίζα) ανάμεσα στους ακεραίους, αν υπάρχουν δηλ. $x_1,\ldots,x_n \in {\mathbb{Z}}$ τ.ώ. $P(x_1,\ldots,x_n) = 0$.
2. Είναι ενδιαφέρον ότι αν ρωτήσουμε αν υπάρχει ρίζα πραγματική (και όχι αναγκαστικά ακέραια), αν δηλ. υπάρχουν $x_1,\ldots,x_n \in {\mathbb{R}}$ τ.ώ. $P(x_1,\ldots,x_n) = 0$, τότε υπάρχει αλγόριθμος που να απαντάει στο ερώτημα.
3. Ένα πολυόμινο είναι μια πεπερασμένη ένωση από μη αλληλοεπικαλυπτόμενα, μοναδιαία (πλευράς 1) τετράγωνα στο επίπεδο, τέτοια ώστε οι συντεταγμένες των κορυφών τους είναι ακέραιες. Στο Σχήμα 10.1 φαίνεται ένα σύνολο από δύο πολυόμινα.
   
   Σχήμα 10.1: Ένα σύνολο από δύο πολυόμινα

   Ένα πολύ ενδιαφέρον ερώτημα είναι αν ένα δεδομένο πεπερασμένο σύνολο από πολυόμινα μπορεί να χρησιμοποιηθεί για να «πλακοστρώσει» ολόκληρο το επίπεδο. Αυτό σημαίνει ότι καλύπτουμε το επίπεδο, χωρίς αλληλοεπικαλύψεις, από κομμάτια καθ' ένα από τα οποία είναι μια παράλληλη μεταφορά κάποιου από τα δεδομένα πολυόμινα. Για παράδειγμα, είναι σχετικά εύκολο να δει κανείς πως τα δύο πολυόμινα του Σχήματος 10.1 μπορούν να πλακοστρώσουν (αγγλικά: tiling) το επίπεδο, και είναι επίσης εύκολο να φτιάξει κανείς παραδείγματα απο σύνολο πολυομίνων που δε μπορούν, όπως και να μεταφερθούν, να πλακοστρώσουν το επίπεδο. Αποδεικνύεται λοιπόν ότι το να αποφασίσει κανείς αν ένα δεδομένο σύνολο από πολυόμινα μπορεί να πλακοστρώσει το επίπεδο είναι αλγοριθμικά ανεπίλυτο πρόβλημα. Δεν υπάρχει δηλ. πρόγραμμα που να του δίνουμε ένα τυχόν πεπερασμένο σύνολο από πολυόμινα και να μας απαντά αν επιδέχεται πλακόστρωση ή όχι.