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

> Επιλύσιμα, ανοικτά και άλυτα προβλήματα — και το πρόβλημα του τερματισμού.

Πληροφορική, Β΄ Λυκείου. https://www.akademio.gr/el/lyk-b/informatics/problems-computability

## Τι θα μάθεις

- Να κατατάσσεις ένα πρόβλημα ως επιλύσιμο, ανοικτό ή άλυτο.
- Να ξεχωρίζεις το «δεν έχει βρεθεί λύση» από το «αποδεδειγμένα δεν υπάρχει λύση».
- Να περιγράφεις τα μέρη μιας μηχανής Turing και τη σημασία της θέσης Church–Turing.
- Να εξηγείς με το επιχείρημα της αντίφασης γιατί το πρόβλημα του τερματισμού δεν λύνεται.

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

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

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

| Κατά τη δομή τους                                            | Παράδειγμα                                   |
| ------------------------------------------------------------ | -------------------------------------------- |
| Δομημένα: η λύση ακολουθεί γνωστή, τυποποιημένη μέθοδο       | επίλυση εξίσωσης δευτέρου βαθμού             |
| Ημιδομημένα: υπάρχει μέθοδος, αλλά χρειάζεται και κρίση      | επιλογή σχολής με βάση μόρια και προτιμήσεις |
| Αδόμητα: δεν υπάρχει μέθοδος, η λύση βασίζεται στην εμπειρία | πρόβλεψη της μόδας της επόμενης χρονιάς      |

| Κατά το είδος της απάντησης                                    | Παράδειγμα                                                    |
| -------------------------------------------------------------- | ------------------------------------------------------------- |
| Απόφασης: η απάντηση είναι ναι ή όχι                           | Είναι ο $97$ πρώτος αριθμός;                                  |
| Υπολογιστικά: η απάντηση είναι μια τιμή                        | Πόσο κάνει $2^{20}$;                                          |
| Βελτιστοποίησης: η απάντηση είναι η καλύτερη από πολλές λύσεις | Ποια είναι η συντομότερη διαδρομή από την Αθήνα στα Ιωάννινα; |

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

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

| Κατηγορία | Τι ξέρουμε                                                             | Παραδείγματα                                                                  |
| --------- | ---------------------------------------------------------------------- | ----------------------------------------------------------------------------- |
| Επιλύσιμα | η λύση είναι γνωστή                                                    | η ταξινόμηση ενός πίνακα, η εξίσωση δευτέρου βαθμού                           |
| Ανοικτά   | η λύση **δεν έχει βρεθεί ακόμα**, ούτε έχει αποδειχθεί ότι δεν υπάρχει | η εικασία του Goldbach, η εικασία Collatz                                     |
| Άλυτα     | έχει **αποδειχθεί** ότι λύση δεν υπάρχει                               | ο τετραγωνισμός του κύκλου με κανόνα και διαβήτη, το πρόβλημα του τερματισμού |

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

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

> **Κλειδί**
>
> **«Δεν έχει βρεθεί λύση» και «δεν υπάρχει λύση» είναι δύο εντελώς διαφορετικές προτάσεις.**
>
> Η πρώτη περιγράφει τι **δεν ξέρουμε ακόμα**, και μπορεί να αλλάξει αύριο. Η δεύτερη είναι **θεώρημα**, και δεν θα αλλάξει ποτέ. Ένα πρόβλημα γίνεται άλυτο μόνο με απόδειξη, ποτέ με αποτυχημένες προσπάθειες, όσες κι αν είναι.

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

## Η μηχανή Turing

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

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

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

> **Θυμήσου**
>
> **Θέση Church–Turing:** ό,τι μπορεί να υπολογιστεί με αλγόριθμο μπορεί να υπολογιστεί από μια μηχανή Turing.
>
> Είναι **θέση** και όχι θεώρημα, γιατί το «αλγόριθμος» στη διαισθητική του σημασία δεν είναι μαθηματικός ορισμός. Κανείς όμως δεν έχει βρει αντιπαράδειγμα. Η συνέπεια είναι μεγάλη: ό,τι δεν μπορεί να κάνει μια μηχανή Turing, δεν μπορεί να το κάνει **κανένας** υπολογιστής, όσο γρήγορος κι αν είναι.

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

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

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

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

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

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

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

| Αν το `stops(paradox, paradox)` απαντήσει… | …τότε το `paradox(paradox)`   | Άρα το `stops` |
| ------------------------------------------ | ----------------------------- | -------------- |
| `True` («σταματά»)                         | μπαίνει σε ατέρμονη επανάληψη | έκανε λάθος    |
| `False` («δεν σταματά»)                    | επιστρέφει αμέσως             | έκανε λάθος    |

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

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

> **Πρόσεχε**
>
> **Το θεώρημα δεν λέει ότι δεν μπορούμε να ξέρουμε αν ένα συγκεκριμένο πρόγραμμα σταματά.**
>
> Για το `for i in range(10): print(i)` είναι προφανές ότι σταματά. Το θεώρημα λέει ότι δεν υπάρχει **μία γενική μέθοδος** που να δίνει τη σωστή απάντηση για **κάθε** πρόγραμμα. Γι' αυτό τα εργαλεία που ελέγχουν κώδικα είναι χρήσιμα αλλά ποτέ τέλεια: σε κάποιες περιπτώσεις θα απαντήσουν «δεν ξέρω» ή θα κάνουν λάθος.

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

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

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

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

| Ερώτημα                  | Κλάδος          | Παράδειγμα                                                  |
| ------------------------ | --------------- | ----------------------------------------------------------- |
| Λύνεται καθόλου;         | υπολογισιμότητα | το πρόβλημα του τερματισμού: όχι, και αυτό έχει αποδειχθεί  |
| Λύνεται σε λογικό χρόνο; | πολυπλοκότητα   | η συντομότερη διαδρομή από πολλές πόλεις: δεν ξέρουμε ακόμα |

## Παραδείγματα

### Παράδειγμα 1: Κατάταξε ως επιλύσιμο, ανοικτό ή άλυτο: (α) η ταξινόμηση \$1000\$ ονομάτων, (β) η εικασία του Goldbach, (γ) η τριχοτόμηση οποιασδήποτε γωνίας με κανόνα και διαβήτη.

1. **(α) Επιλύσιμο.** Υπάρχουν γνωστοί αλγόριθμοι ταξινόμησης, όπως η ταξινόμηση φυσαλίδας.
2. **(β) Ανοικτό.** Δεν έχει βρεθεί αντιπαράδειγμα, αλλά ούτε απόδειξη. Οι έλεγχοι με υπολογιστή, όσο μακριά κι αν φτάσουν, ελέγχουν πεπερασμένο πλήθος αριθμών και δεν αποδεικνύουν τίποτα για όλους.
3. **(γ) Άλυτο.** Το 1837 αποδείχθηκε ότι η τριχοτόμηση μιας τυχαίας γωνίας με κανόνα και διαβήτη είναι αδύνατη. Κάποιες ειδικές γωνίες, όπως η ορθή, τριχοτομούνται· η **γενική** μέθοδος δεν υπάρχει.

### Παράδειγμα 2: Ένας συμμαθητής λέει: «Το πρόβλημα του τερματισμού είναι άλυτο, γιατί κανείς δεν έχει καταφέρει ακόμα να γράψει τη συνάρτηση stops». Τι λάθος κάνει;

1. **Μπερδεύει το ανοικτό με το άλυτο.** Το «κανείς δεν το έχει καταφέρει ακόμα» περιγράφει ανοικτό πρόβλημα.
2. **Το πρόβλημα του τερματισμού είναι άλυτο για άλλον λόγο:** υπάρχει απόδειξη ότι η υπόθεση «υπάρχει `stops`» οδηγεί σε αντίφαση.
3. **Η σωστή διατύπωση:** «Το πρόβλημα του τερματισμού είναι άλυτο, γιατί έχει αποδειχθεί ότι κανένα πρόγραμμα δεν μπορεί να το λύσει για όλα τα προγράμματα».

### Παράδειγμα 3: Μια εταιρεία διαφημίζει πρόγραμμα που «εντοπίζει με βεβαιότητα κάθε ατέρμονη επανάληψη σε οποιοδήποτε πρόγραμμα». Είναι δυνατόν;

1. **Αν το πρόγραμμα κάνει ό,τι υπόσχεται,** τότε απαντά σωστά για κάθε πρόγραμμα αν σταματά ή όχι.
2. **Αυτό είναι ακριβώς η συνάρτηση `stops`,** που αποδείχθηκε ότι δεν μπορεί να υπάρξει.
3. **Άρα η διαφήμιση υπόσχεται κάτι αδύνατο.** Ένα τέτοιο εργαλείο μπορεί να εντοπίζει **πολλές** ατέρμονες επαναλήψεις, αλλά αναγκαστικά θα αστοχεί σε κάποια προγράμματα, είτε απαντώντας λάθος είτε μην απαντώντας καθόλου.

## Ερωτήσεις

1. Ένα πρόβλημα για το οποίο δεν έχει βρεθεί λύση, αλλά ούτε έχει αποδειχθεί ότι δεν υπάρχει, λέγεται:
   - ανοικτό
   - άλυτο
   - αδόμητο
   - επιλύσιμο
2. Η εικασία του Goldbach έχει ελεγχθεί με υπολογιστή για τεράστιο πλήθος αριθμών χωρίς εξαίρεση. Σε ποια κατηγορία ανήκει;
   - στα ανοικτά προβλήματα
   - στα επιλύσιμα, αφού ισχύει για όλους τους αριθμούς που ελέγχθηκαν
   - στα άλυτα, αφού κανείς δεν την απέδειξε σε σχεδόν τρεις αιώνες
   - στα προβλήματα βελτιστοποίησης
3. Τι χρειάζεται για να χαρακτηριστεί ένα πρόβλημα άλυτο;
   - μια απόδειξη ότι δεν υπάρχει λύση
   - να έχουν αποτύχει πολλοί ερευνητές για πολλά χρόνια
   - να μη λύνεται σε λογικό χρόνο από τους σημερινούς υπολογιστές
   - να μην έχει γραφτεί ακόμα πρόγραμμα γι' αυτό
4. Τι ακριβώς αποδεικνύει το θεώρημα του τερματισμού;
   - ότι δεν υπάρχει πρόγραμμα που να αποφασίζει σωστά για κάθε πρόγραμμα αν σταματά
   - ότι για κανένα πρόγραμμα δεν μπορούμε να ξέρουμε αν σταματά
   - ότι όλα τα προγράμματα με επαναλήψεις κινδυνεύουν να μη σταματήσουν
   - ότι οι σημερινοί υπολογιστές δεν είναι αρκετά γρήγοροι για να το ελέγξουν
5. Στην απόδειξη, το πρόγραμμα paradox τρέχει με είσοδο τον εαυτό του. Αν η stops απαντήσει «σταματά», τι κάνει το paradox;
   - μπαίνει σε ατέρμονη επανάληψη
   - σταματά, όπως προβλέφθηκε
   - καλεί ξανά τη stops με άλλη είσοδο
   - βγάζει μήνυμα σφάλματος
6. Τι είδους απόδειξη χρησιμοποιεί ο Turing για το πρόβλημα του τερματισμού;
   - απαγωγή σε άτοπο
   - δοκιμή σε όλα τα δυνατά προγράμματα
   - μαθηματική επαγωγή
   - πειραματική μέτρηση του χρόνου εκτέλεσης
7. Γιατί η θέση Church–Turing λέγεται «θέση» και όχι «θεώρημα»;
   - γιατί η διαισθητική έννοια του αλγορίθμου δεν είναι μαθηματικός ορισμός που αποδεικνύεται
   - γιατί έχει βρεθεί αντιπαράδειγμα, ένας αλγόριθμος που καμία μηχανή Turing δεν εκτελεί
   - γιατί ισχύει μόνο για τους υπολογιστές του 1936 και όχι για τους σημερινούς
   - γιατί ο Turing δεν ήταν μαθηματικός και δεν τη διατύπωσε με αυστηρό τρόπο
8. Ποιο από τα παρακάτω **δεν** είναι μέρος μιας μηχανής Turing;
   - μια κύρια μνήμη με τυχαία προσπέλαση
   - μια ταινία με κελιά
   - μια κεφαλή ανάγνωσης και εγγραφής
   - ένας πίνακας κανόνων
9. Γιατί δεν αρκεί να τρέξουμε ένα πρόγραμμα και να περιμένουμε για να δούμε αν σταματά;
   - γιατί, όσο δεν έχει σταματήσει, δεν ξέρουμε αν θα σταματήσει ποτέ
   - γιατί η εκτέλεση μπορεί να χαλάσει τον υπολογιστή
   - γιατί δεν επιτρέπεται να εκτελέσουμε πρόγραμμα που δεν ξέρουμε
   - γιατί κάθε πρόγραμμα σταματά κάποτε, οπότε η αναμονή είναι περιττή
10. Το «ποια είναι η φθηνότερη σειρά για να επισκεφθεί ένας διανομέας $20$ διευθύνσεις;» είναι πρόβλημα:
   - βελτιστοποίησης
   - απόφασης
   - άλυτο
   - αδόμητο

## Ασκήσεις

1. Σε ποια κατηγορία ανήκει ένα πρόβλημα για το οποίο έχει αποδειχθεί ότι δεν υπάρχει λύση;
2. Γράψε το $30$ ως άθροισμα δύο πρώτων αριθμών με τρεις διαφορετικούς τρόπους.
3. Το «Είναι ο $91$ πρώτος αριθμός;» είναι πρόβλημα απόφασης.
   α) Ποια είναι η απάντηση;
   β) Σε ποια κατηγορία ανήκει ως προς την ύπαρξη λύσης;
4. Στην απόδειξη του Turing, το paradox καλείται με είσοδο τον εαυτό του.
   α) Τι κάνει το paradox αν η stops απαντήσει False;
   β) Ποια υπόθεση καταρρέει στο τέλος;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-b/informatics/problems-computability
