zikos.edu.gr < το σχολείο <

ΕΝΑ  ΑΛΥΤΟ  (ή καλύτερα  ΜΗ  ΑΠΟΚΡΙΣΙΜΟ)

ΠΡΟΒΛΗΜΑ  ΤΗΣ  ΠΛΗΡΟΦΟΡΙΚΗΣ

 

Κατ’αρχάς να συμφωνήσουμε ότι :

αν θεωρήσουμε έναν αλγόριθμο Α και κάποιες εισόδους προς αυτόν (δηλ. δεδομένα του) δ1, ..., δν ,

τότε η έξοδος του Α με δεδομένα δ1, ..., δν θα συμβολίζεται με Α(δ1, ..., δν).

 

Τότε μπορούμε να ορίσουμε το ακόλουθο :

 

 

Πρόβλημα Τερματισμού (Halting Problem)

 

 

Να κατασκευαστεί αλγόριθμος Α, ο οποίος:

α)   να έχει ως είσοδο έναν αλγόριθμο Β (μίας εισόδου)

       καθώς και ένα δεδομένο δ

β)   να έχει ως έξοδο:

       τη λέξη «ΝΑΙ» αν ο Β(δ) τερματίζει

       (δηλ. αν ο αλγόριθμος Β με είσοδο δ τερματίζει)

ή

       τη λέξη «ΟΧΙ» αν ο Β(δ) δεν τερματίζει

       (δηλ. αν ο αλγόριθμος Β με είσοδο δ δεν τερματίζει)

 

 

 

Ο γνωστός μαθηματικός Alan Turing (1912 − 1954) −

που θεωρείται από πολλούς ως ένας από τους «πατέρες» της Πληροφορικής −

απέδειξε ότι το πρόβλημα τερματισμού είναι μη αποκρίσιμο.

Απόδειξη

Με απαγωγή στο άτοπο. Έστω ότι το πρόβλημα τερματισμού ήταν επιλύσιμο, υπήρχε δηλ. αλγόριθμος Α, ο οποίος με είσοδο οποιονδήποτε αλγόριθμο Β (μίας εισόδου) και δεδομένο δ, έχει ως έξοδο «ΝΑΙ» αν ο Β με είσοδο δ τερματίζει, ενώ έχει ως έξοδο «ΟΧΙ» αν ο Β με είσοδο δ δεν τερματίζει. Δηλ. σχηματικά, έστω ότι ίσχυε:

 

Α(Β, δ) =

{

«ΝΑΙ» ,  αν Β(δ) τερματίζει

 

«ΟΧΙ» ,  αν Β(δ) δεν τερματίζει

 

 

 

 

 

Τότε θα μπορούσαμε να κατασκευάσουμε τον ακόλουθο αλγόριθμο Τ (μίας εισόδου Β) :

 

Αλγόριθμος  Τ

 

1.      Ρώτησε για έναν αλγόριθμο Β

 

2.      Αν  Α(Β, Β) = «ΝΑΙ», τότε πήγαινε στο βήμα 2.

 

 

 

 

 

 

 

 

 

Τότε, τι θα συνέβαινε αν δίναμε τον αλγόριθμο Τ ως είσοδο στον Τ ;

Δηλ. θα τερμάτιζε ο Τ(Τ) ;

 

·         Αν τερμάτιζε ο Τ(Τ), τότε αυτό σημαίνει ότι στο βήμα 2 δεν θα ίσχυε

Α(Τ, Τ) = «ΝΑΙ», δηλ. Α(Τ, Τ) = «ΟΧΙ» που σημαίνει ότι Τ(Τ) δεν τερματίζει.   Άτοπο.

 

·         Αν δεν τερμάτιζε ο Τ(Τ), τότε αυτό σημαίνει ότι στο βήμα 2 θα ίσχυε

Α(Τ, Τ) = «ΝΑΙ» που σημαίνει ότι Τ(Τ) τερματίζει.   Άτοπο.

 

Δηλ. ο Τ(Τ) ούτε τερματίζει, ούτε δεν τερματίζει !

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

 

Δηλ. το πρόβλημα τερματισμού δεν είναι επιλύσιμο.

¨

 

zikos.edu.gr < το σχολείο <