Προβλήματα και υπολογισιμότητα

Τι είναι πρόβλημα

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

Τα προβλήματα κατατάσσονται με δύο τρόπους.

Επιλύσιμα, ανοικτά, άλυτα

Η πιο σημαντική διάκριση αφορά το αν η λύση υπάρχει.

Η εικασία του Goldbach (1742) λέει ότι κάθε άρτιος μεγαλύτερος του $2$ γράφεται ως άθροισμα δύο πρώτων: $10 = 3 + 7$, $28 = 11 + 17$. Έχει ελεγχθεί με υπολογιστή για τεράστιους αριθμούς και δεν έχει βρεθεί ούτε μία εξαίρεση. Απόδειξη όμως δεν υπάρχει, άρα το πρόβλημα μένει ανοικτό.

Ο τετραγωνισμός του κύκλου ζητά να κατασκευαστεί με κανόνα και διαβήτη τετράγωνο με εμβαδόν ίσο με ενός δοσμένου κύκλου. Το 1882 αποδείχθηκε ότι αυτό είναι αδύνατο, γιατί ο αριθμός $\pi$ δεν είναι ρίζα καμίας πολυωνυμικής εξίσωσης με ακέραιους συντελεστές. Το πρόβλημα είναι άλυτο: όχι επειδή κανείς δεν τα κατάφερε, αλλά επειδή αποδείχθηκε ότι κανείς δεν θα τα καταφέρει ποτέ.

Ένα ανοικτό πρόβλημα μπορεί να καταλήξει σε οποιαδήποτε από τις δύο άλλες κατηγορίες. Το «τελευταίο θεώρημα του Fermat» ήταν ανοικτό για πάνω από τρεισήμισι αιώνες, ώσπου το 1994 ο Andrew Wiles το απέδειξε. Ο τετραγωνισμός του κύκλου ήταν ανοικτός για δύο χιλιετίες, ώσπου αποδείχθηκε αδύνατος.

Η μηχανή Turing

Για να αποδείξεις ότι κανένα πρόγραμμα δεν λύνει ένα πρόβλημα, πρέπει πρώτα να ορίσεις με ακρίβεια τι είναι «πρόγραμμα». Αυτό έκανε ο Alan Turing το 1936. Η μηχανή του έχει τρία μέρη:

• μια ταινία χωρισμένη σε κελιά, απεριόριστη σε μήκος, όπου σε κάθε κελί γράφεται ένα σύμβολο
• μια κεφαλή που διαβάζει και γράφει ένα κελί τη φορά και μετακινείται ένα κελί αριστερά ή δεξιά
• έναν πίνακα κανόνων: «αν είσαι στην κατάσταση Α και διαβάζεις 1, γράψε 0, πήγαινε δεξιά και πέρνα στην κατάσταση Β»

Αυτό είναι όλο. Φαίνεται υπερβολικά απλό για να κάνει κάτι χρήσιμο, κι όμως μπορεί να εκτελέσει οποιονδήποτε αλγόριθμο εκτελεί ο πιο σύγχρονος υπολογιστής. Πιο αργά, αλλά οποιονδήποτε.

Το πρόβλημα του τερματισμού

Κάθε προγραμματιστής έχει γράψει κάποτε μια ατέρμονη επανάληψη. Θα ήταν πολύτιμο ένα εργαλείο που διαβάζει οποιοδήποτε πρόγραμμα με τα δεδομένα του και απαντά σωστά «θα σταματήσει» ή «θα τρέχει για πάντα».

Το 1936 ο Turing απέδειξε ότι ένα τέτοιο εργαλείο δεν μπορεί να υπάρξει. Η απόδειξη είναι απαγωγή σε άτοπο: υποθέτουμε ότι υπάρχει και καταλήγουμε σε αντίφαση.

Ας υποθέσουμε ότι κάποιος έγραψε τη συνάρτηση stops(program, data), που επιστρέφει True αν το program σταματά όταν τρέξει με είσοδο data, και False αλλιώς. Τότε μπορούμε να γράψουμε το εξής πρόγραμμα:

def stops(program, data):
    # Η υποθετική συνάρτηση. Η απόδειξη δείχνει ότι κανείς δεν μπορεί να τη γράψει.
    raise NotImplementedError("δεν υπάρχει τέτοια συνάρτηση")


def paradox(program):
    if stops(program, program):
        while True:  # αν «σταματά», κάνε ατέρμονη επανάληψη
            pass
    else:
        return "σταμάτησα"  # αν «δεν σταματά», σταμάτα αμέσως

Το paradox κάνει πάντα το αντίθετο από ό,τι προβλέπει το stops. Τώρα το ερώτημα-παγίδα: τι γίνεται με το paradox(paradox);

Και οι δύο απαντήσεις είναι λάθος. Αφού όμως υποθέσαμε ότι το stops απαντά πάντα σωστά, η υπόθεση ήταν ψευδής: η συνάρτηση stops δεν μπορεί να γραφτεί, από κανέναν, σε καμία γλώσσα, σε κανέναν υπολογιστή.

Το επιχείρημα θυμίζει το αρχαίο παράδοξο του ψεύτη, «αυτή η πρόταση είναι ψευδής»: ένα αντικείμενο που μιλά για τον εαυτό του και αντιστρέφει ό,τι λέγεται γι' αυτό.

«Γιατί να μην τρέξουμε απλώς το πρόγραμμα και να δούμε;» Αν σταματήσει, έχουμε απάντηση. Αν όμως τρέχει ακόμα μετά από μια ώρα, δεν ξέρουμε αν θα σταματήσει στο επόμενο λεπτό ή ποτέ. Η αναμονή δίνει μόνο τη μία από τις δύο απαντήσεις.

Επιλύσιμο δεν σημαίνει εύκολο

Ανάμεσα στα επιλύσιμα υπάρχει μια ακόμα διαφορά: κάποια λύνονται γρήγορα και κάποια μόνο θεωρητικά. Για να βρεις τη συντομότερη διαδρομή που περνά από $20$ πόλεις, μπορείς να δοκιμάσεις όλες τις σειρές. Είναι όμως περισσότερες από $10^{18}$, και κανένας υπολογιστής δεν θα τελείωνε σε όλη σου τη ζωή.

Για πολλά τέτοια προβλήματα δεν ξέρουμε αν υπάρχει γρήγορος αλγόριθμος. Το ερώτημα αυτό, γνωστό ως P εναντίον NP, είναι ίσως το πιο διάσημο ανοικτό πρόβλημα της πληροφορικής. Κανείς δεν έχει βρει γρήγορο αλγόριθμο, αλλά κανείς δεν έχει αποδείξει ότι δεν υπάρχει. Το πώς μετράμε το «γρήγορα» είναι το θέμα του επόμενου μαθήματος.

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση