Χρήστης:Aggelos ap/πρόχειρο
Πρόβλημα ανάσχεσης[Επεξεργασία | επεξεργασία κώδικα]
Στην θεωρητική πληροφορική, το πρόβλημα ανάσχεσης μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον.
Ο Alan Turing, το 1936, απέδειξε ότι δεν υπάρχει κάποιος γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου. Κομμάτι κλειδί της απόδειξης ήταν ένας μαθηματικός ορισμός ενός υπολογιστικού προγράμματος, γνωστού ως μηχανή Turing. Το πρόβλημα ανάσχεσης είναι αβέβαιο στις μηχανές Turing. Είναι ένα από τα πρώτα παραδείγματα προβλήματος απόφασης.
Ο Jack Copeland(2004) προσδίδει τον όρο πρόβλημα ανάσχεσης στον Martin Davis.
Υπόβαθρο[Επεξεργασία | επεξεργασία κώδικα]
Το πρόβλημα ανάσχεσης είναι ένα πρόβλημα απόφασης που αφορά υπολογιστικά προγράμματα σε ένα σταθερό Turing-ολοκληρωμένο υπολογιστικό μοντέλο, δηλαδή όλα τα προγράμματα που μπορούν να γραφούν σε κάποια γλώσσα προγραμματισμού που είναι αρκετά γενική ώστε να θεωρηθεί ισοδύναμη με μία μηχανή Turing. Πιο συγκεκριμένα, το πρόβλημα είναι ο καθορισμός, δοθέντος προγράμματος και μιας εισόδου, αν το πρόγραμμα θα σταματήσει τελικά να τρέχει. Σε αυτό το αφηρημένο πλαίσιο δεν υπάρχει περιορισμός πόρων που αφορούν τη μνήμη ή το χρόνο εκτέλεσης του προγράμματος, δηλαδή μπορεί να είναι αυθαίρετα μακρύ και να καταλάβει αυθαίρετα μεγάλο αποθηκευτικό χώρο πριν σταματήσει. Το ερώτημα είναι αν το πρόγραμμα που μας δόθηκε θα σταματήσει ποτέ με μια συγκεκριμένη είσοδο.
Για παράδειγμα, σε ψευδοκώδικα, το πρόγραμμα:
- while (true) continue
δεν σταματάει αλλά συνεχίζει για πάντα σε έναν ατέρμων βρόχο. Αντιθέτως, το πρόγραμμα:
- print "Hello, world!"
σταματάει.
Μπορεί στα δυο παραπάνω προγράμματα να αποφαινόμαστε εύκολα για το αν σταματάνε ή όχι, δεν συμβαίνει όμως το ίδιο και με πιο πολύπλοκα προγράμματα.
Για να δώσουμε μια απάντηση θα μπορούσαμε να τρέξουμε ένα πρόγραμμα για πεπερασμένο αριθμό βημάτων και να δούμε αν σταματάει. Αλλά αν το πρόγραμμα δεν σταματάει τότε δεν μπορούμε να αποφανθούμε αν τελικά κάποτε θα σταματήσει ή όχι.
Ο Τuring απέδειξε ότι αν υπήρχε αλγόριθμος που θα μπορούσε να προσδιορίσει αν ένα ζευγάρι προγράμματος-εισόδου πέφτει σε ατέρμων βρόχο ή όχι, τότε η δομή του αλγορίθμου θα έπρεπε να είναι τέτοια ώστε να έρχεται σε αντιπαράθεση με τον εαυτό του. Έτσι αποδείχτηκε η μη ύπαρξη τέτοιου αλγορίθμου.