ΕΝΑ ΑΛΥΤΟ (ή καλύτερα ΜΗ ΑΠΟΚΡΙΣΙΜΟ) ΠΡΟΒΛΗΜΑ ΤΗΣ ΠΛΗΡΟΦΟΡΙΚΗΣ
Κατ’αρχάς να συμφωνήσουμε ότι : αν θεωρήσουμε έναν αλγόριθμο Α και κάποιες εισόδους προς αυτόν (δηλ. δεδομένα του) δ1, ..., δν , τότε η έξοδος του Α με δεδομένα δ1, ..., δν θα συμβολίζεται με Α(δ1, ..., δν).
Τότε μπορούμε να ορίσουμε το ακόλουθο :
Πρόβλημα Τερματισμού (Halting Problem)
Απόδειξη Με απαγωγή στο άτοπο. Έστω ότι το πρόβλημα τερματισμού ήταν επιλύσιμο, υπήρχε δηλ. αλγόριθμος Α, ο οποίος με είσοδο οποιονδήποτε αλγόριθμο Β (μίας εισόδου) και δεδομένο δ, έχει ως έξοδο «ΝΑΙ» αν ο Β με είσοδο δ τερματίζει, ενώ έχει ως έξοδο «ΟΧΙ» αν ο Β με είσοδο δ δεν τερματίζει. Δηλ. σχηματικά, έστω ότι ίσχυε:
Τότε θα μπορούσαμε να κατασκευάσουμε τον ακόλουθο αλγόριθμο Τ (μίας εισόδου Β) :
Τότε, τι θα συνέβαινε αν δίναμε τον αλγόριθμο Τ ως είσοδο στον Τ ; Δηλ. θα τερμάτιζε ο Τ(Τ) ;
· Αν τερμάτιζε ο Τ(Τ), τότε αυτό σημαίνει ότι στο βήμα 2 δεν θα ίσχυε Α(Τ, Τ) = «ΝΑΙ», δηλ. Α(Τ, Τ) = «ΟΧΙ» που σημαίνει ότι Τ(Τ) δεν τερματίζει. Άτοπο.
· Αν δεν τερμάτιζε ο Τ(Τ), τότε αυτό σημαίνει ότι στο βήμα 2 θα ίσχυε Α(Τ, Τ) = «ΝΑΙ» που σημαίνει ότι Τ(Τ) τερματίζει. Άτοπο.
Δηλ. ο Τ(Τ) ούτε τερματίζει, ούτε δεν τερματίζει ! Πράγμα που είναι προφανώς άτοπο, άρα η αρχική παραδοχή που κάναμε, ότι το πρόβλημα τερματισμού είναι επιλύσιμο, δεν ισχύει.
Δηλ. το πρόβλημα τερματισμού δεν είναι επιλύσιμο. ¨ |
|