Πρόβλημα τερματισμού

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

Για παράδειγμα, ένα πρόγραμμα όπως αυτό:

while True: continue,

θα επαναλαμβάνεται για πάντα, αλλά το πρόγραμμα

while False: continue,

σταματάει πολύ γρήγορα.

Υπάρχει κάποιο πρόγραμμα που να λύνει το πρόβλημα του σταματήματος; Αποδεικνύεται ότι δεν υπάρχει. Αποδεικνύουμε αυτό το γεγονός δείχνοντας ότι αν υπάρχει ένα πρόγραμμα που λύνει το πρόβλημα του σταματήματος τότε συμβαίνει κάτι αδύνατο. Έτσι, προς το παρόν θα συμπεριφερθούμε σαν να υπάρχει πράγματι ένα πρόγραμμα που λύνει το πρόβλημα της διακοπής. Εδώ, το P είναι μια συνάρτηση η οποία θα αξιολογήσει τη συνάρτηση F (που καλείται με το όρισμα I) και θα επιστρέψει true αν τρέχει για πάντα και false αλλιώς.

def P(F, I): if F(I) runs forever: return True; else: return False,

P μπορεί να κοιτάξει οποιοδήποτε πρόγραμμα και να διαπιστώσει αν θα τρέχει για πάντα ή όχι. Χρησιμοποιούμε το P για να φτιάξουμε ένα νέο πρόγραμμα το οποίο θα ονομάσουμε Q. Αυτό που κάνει το Q είναι να κοιτάξει ένα άλλο πρόγραμμα και στη συνέχεια να απαντήσει στην ακόλουθη ερώτηση: "Αν τρέξουμε αυτό το πρόγραμμα και το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του, θα τρέχει για πάντα;". Μπορούμε να φτιάξουμε το Q επειδή έχουμε το P. Το μόνο που χρειάζεται να κάνουμε είναι να πούμε στο Q να δημιουργήσει ένα νέο πρόγραμμα που είναι το παλιό πρόγραμμα που κοιτάζει τον εαυτό του και στη συνέχεια να χρησιμοποιήσουμε το P για να μάθουμε αν το νέο πρόγραμμα τρέχει για πάντα ή όχι.

def Q(F): return P(F, F),

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

def R(F): if Q(F): return; //τερματισμός else: while True: continue; //βρόχος για πάντα

Τώρα θα δούμε τι συμβαίνει αν κάνουμε την R να κοιτάξει ένα αντίγραφο του εαυτού της. Δύο πράγματα μπορούν να συμβούν: είτε θα σταματήσει είτε θα τρέχει για πάντα.

Αν η εκτέλεση του R και το να το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του δεν τρέχει για πάντα, τότε ο Q απάντησε "ναι, αν τρέξουμε αυτό το πρόγραμμα και το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του θα τρέχει για πάντα". Αλλά ο Q το είπε αυτό όταν κοιτούσε το ίδιο το R. Άρα αυτό που είπε στην πραγματικότητα ο Q είναι: "ναι, αν τρέξουμε το R και το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του θα τρέχει για πάντα". Οπότε: Αν η R τρέχοντας σε ένα αντίγραφο του εαυτού της δεν τρέχει για πάντα, τότε τρέχει για πάντα. Αυτό είναι αδύνατο.

Αν η εκτέλεση του R και το να το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του τρέχει για πάντα, τότε ο Q απάντησε "όχι, αν τρέξουμε αυτό το πρόγραμμα και το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του δεν θα τρέχει για πάντα". Αλλά ο Q το είπε αυτό όταν κοιτούσε το ίδιο το R. Άρα αυτό που είπε στην πραγματικότητα ο Q είναι: "όχι, αν τρέξουμε το R και το κάνουμε να κοιτάξει ένα αντίγραφο του εαυτού του δεν θα τρέχει για πάντα". Οπότε: Αν η R τρέχοντας σε ένα αντίγραφο του εαυτού της τρέχει για πάντα, τότε δεν τρέχει για πάντα. Αυτό είναι επίσης αδύνατο.

Ό,τι κι αν συμβεί, έχουμε μια αδύνατη κατάσταση. Κάτι κάναμε λάθος και πρέπει να βρούμε τι ήταν αυτό. Τα περισσότερα από τα πράγματα που κάναμε δεν ήταν λάθος. Δεν μπορούμε να πούμε ότι "το να βάλουμε ένα πρόγραμμα να κοιτάξει ένα αντίγραφο του εαυτού του είναι λάθος", ή ότι "το να κοιτάξουμε τι είπε ένα άλλο πρόγραμμα και μετά να μπούμε σε έναν βρόχο αν είπε ένα πράγμα και να σταματήσουμε αν είπε κάτι άλλο" είναι λάθος. Δεν έχει νόημα να πούμε ότι δεν επιτρέπεται να κάνουμε αυτά τα πράγματα. Το μόνο πράγμα που κάναμε και φαίνεται ότι θα μπορούσε να είναι λάθος είναι ότι προσποιηθήκαμε ότι ένα πρόγραμμα όπως το P υπάρχει εξ αρχής. Και αφού αυτό είναι το μόνο πράγμα που θα μπορούσε να είναι λάθος, και κάτι πρέπει να είναι λάθος, αυτό είναι. Αυτή είναι η απόδειξη ότι ένα πρόγραμμα όπως το P δεν υπάρχει. Δεν υπάρχει κανένα πρόγραμμα που να λύνει το πρόβλημα του σταματήματος.

Η απόδειξη αυτή βρέθηκε από τον Alan Turing το 1936.

Ερωτήσεις και απαντήσεις

Q: Τι είναι το πρόβλημα του Halting;

A: Το πρόβλημα Halting είναι ένα πρόβλημα στην επιστήμη των υπολογιστών που εξετάζει ένα πρόγραμμα υπολογιστή και καθορίζει αν το πρόγραμμα θα εκτελείται για πάντα ή όχι.

Ερ: Πώς ξέρουμε αν ένα πρόγραμμα λύνει το πρόβλημα Halting;

Α: Λέμε ότι ένα πρόγραμμα "λύνει το πρόβλημα halting" αν μπορεί να κοιτάξει οποιοδήποτε άλλο πρόγραμμα και να πει αν αυτό το άλλο πρόγραμμα θα τρέχει για πάντα ή όχι.

Ε: Υπάρχει τρόπος να αποδείξουμε ότι δεν υπάρχει τέτοιο πρόγραμμα;

Α: Ναι, δείχνοντας ότι αν υπήρχε ένα τέτοιο πρόγραμμα τότε θα συνέβαινε κάτι αδύνατο. Αυτή η απόδειξη βρέθηκε από τον Alan Turing το 1936.

Ε: Τι κάνει το P;

Α: Η P είναι μια συνάρτηση που αξιολογεί μια άλλη συνάρτηση F (που καλείται με όρισμα I) και επιστρέφει true αν τρέχει για πάντα και false αλλιώς.

Ε: Τι κάνει το Q;

Α: Το Q εξετάζει ένα άλλο πρόγραμμα και στη συνέχεια απαντά στο ερώτημα αν η εκτέλεση του ίδιου προγράμματος στον εαυτό του θα οδηγήσει σε έναν ατέρμονα βρόχο ή όχι. Αυτό το κάνει χρησιμοποιώντας το P για να κάνει μια αξιολόγηση της δεδομένης συνάρτησης F.

Ε: Τι κάνει το R;

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

Ερ: Τι συμβαίνει όταν κάνετε το R να κοιτάξει τον εαυτό του;

Α: Δύο πράγματα μπορούν να συμβούν - είτε το R σταματάει είτε τρέχει για πάντα - αλλά και τα δύο αποτελέσματα είναι αδύνατα σύμφωνα με όσα έχουν αποδειχθεί για προγράμματα όπως το P που δεν υπάρχουν, οπότε κάτι πρέπει να έχει πάει στραβά κάπου στην πορεία που οδηγεί στο να κάνεις το R να κοιτάξει τον εαυτό του.