Πρόβλημα τερματισμού

Στη θεωρία υπολογισμού, το πρόβλημα τερματισμού μπορεί να οριστεί ως εξής: "Δοθείσης μιας περιγραφής ενός αυθαίρετου υπολογιστικού προγράμματος αποφάσισε αν το πρόγραμμα θα σταματήσει να τρέχει ή αν θα συνεχίσει να τρέχει για πάντα". Το παραπάνω πρόβλημα είναι ισοδύναμο με το πρόβλημα της απόφασης, δοθέντος ενός προγράμματος και μιας εισόδου, αν αυτό τελικά θα σταματήσει εφόσον έχει τρέξει πεπερασμένες φορές ή αν θα συνεχίσει επ' άπειρον.

Ο Άλαν Τιούρινγκ, το 1936, απέδειξε ότι δεν υπάρχει κάποιος γενικός αλγόριθμος ο οποίος θα λύνει το πρόβλημα του τερματισμού για όλα τα πιθανά ζεύγη προβλήματος-εισόδου. Κομμάτι κλειδί της απόδειξης ήταν ένας μαθηματικός ορισμός ενός υπολογιστικού προγράμματος, γνωστού ως μηχανή Τιούρινγκ. Το πρόβλημα τερματισμού είναι μη αποφασίσιμο στις μηχανές Turing. Είναι ένα από τα πρώτα παραδείγματα προβλήματος απόφασης.

Ο Jack Copeland (2004) προσδίδει τον όρο πρόβλημα τερματισμού στον Martin Davis.

Υπόβαθρο

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

Για παράδειγμα, σε ψευδοκώδικα, το πρόγραμμα:

while (true) continue

δεν σταματάει αλλά συνεχίζει για πάντα σε έναν ατέρμονα βρόχο. Αντιθέτως, το πρόγραμμα:

print "Hello, world!"

σταματάει.

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

Για να δώσουμε μια απάντηση θα μπορούσαμε να τρέξουμε ένα πρόγραμμα για πεπερασμένο αριθμό βημάτων και να δούμε αν σταματάει. Αλλά αν το πρόγραμμα δεν σταματάει τότε δεν μπορούμε να αποφανθούμε αν τελικά κάποτε θα σταματήσει ή όχι.

Ο Τιούρινγκ απέδειξε ότι, αν υπήρχε αλγόριθμος να προσδιορίζει αν ένα ζευγάρι προγράμματος-εισόδου πέφτει σε ατέρμονα βρόχο ή όχι, τότε η δομή του αλγορίθμου θα έπρεπε να είναι τέτοια ώστε να έρχεται σε αντιπαράθεση με τον εαυτό του. Έτσι αποδείχτηκε η μη ύπαρξη τέτοιου αλγορίθμου.

Σπουδαιότητα και συνέπειες

Το πρόβλημα τερματισμού είναι ιστορικής σημασίας διότι ήταν ένα από τα πρώτα μη αποφασίσιμα προβλήματα. (Η απόδειξη του Τuring εκδόθηκε στον τύπο τον Μάιο του 1936, ενώ η απόδειξη του Alonzo Church ότι το πρόβλημα λογισμός λάμδα είναι επίσης μη αποφασίσιμο είχε εκδοθεί ένα μήνα πριν. Μεταγενέστερα περιγράφηκαν και άλλα άλυτα προβλήματα. Η πιο συνηθισμένη τεχνική για να αποδείξει κανείς ότι ένα πρόβλημα είναι άλυτο είναι η τεχνική της μείωσης. Αυτή η τεχνική εξηγείται ως εξής: έχουμε ένα νέο πρόβλημα που δεν γνωρίζουμε αν είναι επιλύσιμο ή όχι. Λαμβάνουμε μια υποθετική λύση του προβλήματος και δείχνουμε ότι αυτή η λύση θα μπορούσε να χρησιμοποιηθεί για να προσδιορίσει ένα απροσδιόριστο πρόβλημα μετατρέποντας μέρη του απροσδιόριστου προβλήματος σε περιστάσεις του νέου προβλήματος. Εφόσον ήδη γνωρίζουμε ότι δεν υπάρχει μέθοδος που να μπορεί να προσδιορίσει το παλιό πρόβλημα, καμιά μέθοδος δεν μπορεί να προσδιορίσει και το νέο. Συχνά ένα νέο πρόβλημα ανάγεται στο πρόβλημα τερματισμού για την εφαρμογή της παραπάνω τεχνικής.

Για παράδειγμα, το γεγονός ότι το πρόβλημα τερματισμού είναι άλυτο μας οδηγεί στο συμπέρασμα ότι δεν υπάρχει γενικός αλγόριθμος που να αποφασίζει αν μια δήλωση σχετική με τους φυσικούς αριθμούς είναι αλήθεια ή ψέμα. Ο λόγος είναι ότι η πρόταση που δηλώνει ότι ένα συγκεκριμένο πρόγραμμα θα σταματήσει δοθείσης συγκεκριμένης εισόδου μπορεί να μετατραπεί σε μια ισοδύναμη πρόταση σχετική με φυσικούς αριθμούς. Αν υπήρχε αλγόριθμος που θα μπορούσε να λύνει κάθε δήλωση σχετική με τους φυσικούς αριθμούς, θα μπορούσε σίγουρα να λύσει και αυτή, γεγονός άτοπο διότι τότε θα καθορίζονταν και η λύση του προβλήματος τερματισμού.

To θεώρημα Rice γενικεύει το θεώρημα που λέει ότι το πρόβλημα τερματισμού είναι άλυτο. Δηλώνει ότι για κάθε μη τετριμμένη ιδιότητα δεν υπάρχει μια γενική διαδικασία, η οποία, για όλα τα προγράμματα, να αποφασίζει αν η μερική συνάρτηση εφαρμοσμένη από το πρόγραμμα εισόδου έχει αυτήν την ιδιότητα. (Μια μερική συνάρτηση είναι μια συνάρτηση που μπορεί να μην βγάζει πάντα αποτέλεσμα, οπότε χρησιμοποιείται σε πειραματικά προγράμματα που είτε βγάζουν αποτέλεσμα είτε αδυνατούν να σταματήσουν να τρέχουν. Για παράδειγμα, η ιδιότητα "όταν η είσοδος είναι ο αριθμός 0, σταμάτα" είναι απροσδιόριστη. Εδώ, τετριμμένη ιδιότητα σημαίνει ότι το σύνολο από τις μερικές συναρτήσεις που ικανοποιούν την ιδιότητα δεν είναι ούτε το κενό σύνολο ούτε όλες οι μερικές συναρτήσεις. Η ιδιότητα "το πρόγραμμα τερματίζεται ή δεν τερματίζεται δεδομένης της εισόδου του αριθμού 0" είναι προφανώς αληθής για όλες τις μερικές συναρτήσεις, οπότε είναι τετριμμένη ιδιότητα και μπορεί να αποφασιστεί από έναν αλγόριθμο που απαντάει απλώς με "αληθής". Αυτό το θεώρημα ισχύει μόνο για ιδιότητες μιας μερικής συνάρτησης που εφαρμόζεται από το πρόγραμμα. Δηλαδή το θεώρημα Rice δεν εφαρμόζεται απευθείας σε ιδιότητες του ίδιου του προγράμματος. Για παράδειγμα, "σταμάτα όταν γίνει είσοδος ο αριθμός 0 σε 100 βήματα" δεν είναι ιδιότητα μερικής συνάρτησης που εφαρμόζεται από το πρόγραμμα-είναι μια ιδιότητα του προγράμματος που εφαρμόζει την μερική συνάρτηση και μπορεί λίγο πολύ να προσδιοριστεί.

Ο Gregory Chaitin όρισε μια πιθανότητα τερματισμού, που αναπαριστάται από το σύμβολο Ω, ένα είδος πραγματικού αριθμού που ανεπίσημα δηλώνει την πιθανότητα τερματισμού ενός τυχαίου προγράμματος. Αυτοί οι αριθμοί έχουν τον ίδιο βαθμό Turing όπως το πρόβλημα τερματισμού. Είναι ένας κανονικός και υπερβατικός αριθμός που μπορεί να προσδιορισθεί αλλά δεν μπορεί να υπολογιστεί. Αυτό σημαίνει ότι δεν υπάρχει αλγόριθμος που να παράγει όλα τα ψηφία του Ω αλλά μόνο μερικά αρχικά.

Αν και ο Turing είχε αποδείξει ότι δεν υπάρχει γενικός αλγόριθμος που να καθορίζει αν ένας αλγόριθμος τερματίζεται,υπάρχουν μεμονωμένες περιστάσεις που το πρόβλημα αυτό ξεπερνιέται. Δοθέντος συγκεκριμένου αλγορίθμου, μπορεί κανείς να δείξει ότι πρέπει να τερματίζεται για κάθε είσοδο και στην πράξη οι προγραμματιστές συχνά κάνουν αυτή τη δουλειά ως μέρος της διόρθωσης του αλγορίθμου. Αλλά κάθε απόδειξη ότι ο αλγόριθμος τερματίζεται αναπτύσσεται σύμφωνα με τον εκάστοτε αλγόριθμο. Αυτό διότι όπως προαναφέρθηκε δεν υπάρχει "μηχανικός, γενικός τρόπος" που να προσδιορίζει αν ένας αλγόριθμος που τρέχει σε μηχανή Turing τελικά σταματάει. Ωστόσο υπάρχουν ορισμένες ευριστικές τεχνικές για την κατασκευή τέτοιων αποδείξεων, που τα καταφέρνουν σε συνηθισμένα προγράμματα. Αυτό το ερευνητικό πεδίο είναι γνωστό ως αυτόματη ανάλυση τερματισμού.

Εφόσον η αρνητική απάντηση στο πρόβλημα τερματισμού δείχνει ότι υπάρχουν προβλήματα που δεν λύνονται από τις μηχανές Turing, η πρόταση Church-Turing συγκεκριμενοποιεί τι μπορεί και τι δεν μπορεί να λυθεί από μια αποτελεσματική μέθοδο. Παρ' όλα αυτά, από όλες τις μηχανές που χωράει η ανθρώπινη φαντασία υπάρχουν και κάποιες που δεν υπόκεινται στην πρόταση Church-Turing, όπως οι μηχανές μαντείας. Ανοιχτό πρόβλημα αποτελεί το ερώτημα αν θα μπορούσαν να υπάρξουν καθοριστικές φυσικές διαδικασίες που, μακροπρόθεσμα, ξεφεύγουν της προσομοίωσης από μηχανές Turing, και συγκεκριμένα αν μια τέτοια υποθετική διαδικασία θα μπορούσε να αξιοποιηθεί στη μορφή μιας υπολογιστική μηχανής (έναν υπερυπολογιστή) που να μπορεί,μεταξύ άλλων, να λύνει το πρόβλημα του τερματισμού στις μηχανές Turing.

Αναπαράσταση ως σύνολο

Η τυπική αναπαράσταση προβλημάτων απόφασης είναι το σύνολο των αντικειμένων που κατέχουν την ιδιότητα που εξετάζεται. Το "σύνολο τερματισμού" :

"K"={("i","x")| το πρόγραμμα "i" τερματίζεται όταν τρέχει με είσοδο το "x"}

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

Αυτό το σύνολο είναι αναδρομικά αριθμήσιμο, που σημαίνει ότι υπάρχει μία υπολογίσιμη συνάρτηση που "τακτοποιεί σε λίστα" όλα τα ζευγάρια ("i", x) που περιέχει. Ωστόσο , το συμπληρωματικό αυτού του συνόλου δεν είναι αναδρομικά αριθμήσιμο.

Υπάρχουν πολλές ισοδύναμες μετατροπές του προβλήματος τερματισμού. Κάθε σύνολο με βαθμό Turing ίσο με του προβλήματος τερματισμού είναι μια τέτοια μετατροπή. Παραδείγματα:

• {"i" | το πρόγραμμα "i" τελικά σταματάει όταν τρέχει με είσοδο το 0}
• {"i" | υπάρχει είσοδος "x" τέτοια ώστε το πρόγραμμα "i" να σταματάει όταν τρέχει με την είσοδο "x"}

Σχεδιάγραμμα της απόδειξης

Η απόδειξη δείχνει ότι δεν υπάρχει ολική υπολογίσιμη συνάρτηση που να αποφασίζει πότε ένα αυθαίρετο πρόγραμμα "i" τερματίζει για ένα αυθαίρετο δεδομένο "x", όπου η ακόλουθη συνάρτηση "h" είναι μη υπολογίσιμη (Penrose 1990, p. 57–63):

$h(i,x)={\begin{cases}1&{\text{if }}{\text{ program }}i{\text{ halts on input }}x,\\0&{\text{otherwise.}}\end{cases}}$

Εδώ το πρόγραμμα "i" παραπέμπει στο "i"-οστό πρόγραμμα σε ένα αριθμήσιμο σύνολο προγραμμάτων από καθορισμένα πλήρης-Turing μοντέλα υπολογισμού.

f(i,j)		i	i	i	i	i	i
		1	2	3	4	5	6
j	1	1	0	0	1	0	1
j	2	0	0	0	1	0	0
j	3	0	1	0	1	0	1
j	4	1	0	0	1	0	0
j	5	0	0	0	1	1	1
j	6	1	1	0	0	1	0
	f(i,i)	1	0	0	1	1	0
	g(i)	U	0	0	U	U	0

Πιθανές τιμές για μία ολική υπολογίσιμη συνάρτηση "f" διατεταγμένη σε ένα δισδιάστατο πίνακα. Τα πορτοκαλί κελιά αποτελούν την διαγώνιο. Οι τιμές των f(i,i) και g(i) βρίσκονται στο κάτω μέρος του πίνακα, το U υποδεικνύει ότι η συνάρτηση "g" είναι απροσδιόριστη για ορισμένες δοθείσες τιμές.

Η απόδειξη ξεκινάει άμεσα προσδιορίζοντας πως κάθε ολική υπολογίσιμη συνάρτηση με δύο ορίσματα διαφέρει από την απαιτούμενη συνάρτηση "h". Για αυτό ,αν πάρουμε μία ολική υπολογίσιμη δυαδική συνάρτησης "f", η παρακάτω συνάρτηση "g" θα είναι επίσης υπολογίσιμη από κάποιο πρόγραμμα "e" :

$g(i)={\begin{cases}0&{\text{if }}f(i,i)=0,\\{\text{undefined}}&{\text{otherwise.}}\end{cases}}$

Η επαλήθευση ότι η "g" είναι υπολογίσιμη βασίζεται στα παρακάτω παράγωγά της (ή ισοδύναμα αυτής):

• υπολογίσιμα υποπρογράμματα (το πρόγραμμα που υπολογίζει την "f" είναι ένα υποπρόγραμμα στο πρόγραμμα "e",
• διπλασιασμός των τιμών (το πρόγραμμα "e" υπολογίζει τα εισαγόμενα "i","i" για την "f" από το εισαγόμενο "i" για την "g"),
• υπό συνθήκη διακλάδωση (το πρόγραμμα "e" επιλέγει ανάμεσα σε δύο αποτελέσματα σύμφωνα με την τιμή της "f"("i","i"),
• δεν παράγει αποτέλεσμα που ορίζεται (π.χ. ατέρμων βρόχος),
• επιστρέφει μία τιμή 0.

Ο ακόλουθος ψευδοκώδικας απεικονίζει ένα απλό τρόπο υπολογισμού της "g":

procedure compute_g(i):
    if f(i,i) == 0 then
        return 0
    else
        loop forever

Επειδή η "g" είναι μερικώς υπολογίσιμη, πρέπει να υπάρχει ένα πρόγραμμα "e" που υπολογίζει την "g", από την υπόθεση πως το μοντέλο υπολογισμού είναι πλήρες-Τuring. Αυτό το πρόγραμμα είναι ένα από όλα τα προγράμματα με το οποίο ορίζεται η συνάρτηση τερματισμού/ανάσχεσης "h". Στο επόμενο βήμα βλέπουμε ότι η τιμή "h"("e","e") δεν θα είναι ίδια με την f(e,e).

Από τον ορισμό της "g", κρατάμε μία ακριβώς από τις δύο περιπτώσεις:

• f(e,e) = 0 άρα g(e) = 0. Σ'αυτή την περίπτωση h(e,e) = 1, γιατί το πρόγραμμα "e" τερματίζει για εισαγόμενο e.
• f(e,e) ≠ 0 άρα g(e) δεν ορίζεται. Σ'αυτή την περίπτωσή h(e,e) = 0, γιατί το πρόγραμμα "e" δεν τερματίζεται για εισαγόμενο "e".

Σε κάθε περίπτωση , η "f" δεν μπορεί να είναι η ίδια συνάρτηση με την "h". Επειδή "f" ήταν μία "αυθαίρετη" ολική υπολογίσιμη συνάρτηση συνάρτηση με δύο ορίσματα , όλες αυτές οι συναρτήσεις πρέπει να διαφέρουν από την "h".

Αυτή η απόδειξη είναι ανάλογη με το Διαγώνιο όρισμα του Cantor. Μπορούμε να φανταστούμε ένα δισδιάστατο πίνακα με μία στήλη και μία γραμμή για κάθε φυσικό αριθμό όπως υποδεικνύεται στον πίνακα παραπάνω. Η τιμή f(i,j) βρίσκεται στη στήλη "i", γραμμή "j". Γιατί η "f" υποτίθεται ότι είναι ολική υπολογίσιμη συνάρτηση και κάθε στοιχείο το πίνακα μπορεί να υπολογιστεί χρησιμοποιώντας την "f". Η κατασκευή της συνάρτησης "g" μπορεί να αποτυπωθεί χρησιμοποιώντας την κύρια διαγώνιο αυτού του πίνακα. Αν ο πίνακας έχει 0 στην θέση (i,i), τότε g(i) είναι 0. Διαφορετικά το g(i) δεν ορίζεται. Η αντίφαση έρχεται από το γεγονός ότι υπάρχει στήλη "e" που αντιστοιχεί στη g αυτοπροσώπως. Ας υποθέσουμε ότι η "f" ήταν η συνάρτηση τερματισμού "h", αν ορίζεται η g(e),( g(e) σ'αυτή τη περίπτωση)g(e) τερματίζει, έτσι f(e,e) = 1. Αλλά g(e) = 0 μόνο όταν f(e,e) = 0, σε αντίθεση f(e,e) = 1. Ομοίως , αν g(e) δεν ορίζεται , τότε η f(e,e) = 0 συνάρτηση τερματισμού ,το οποίο μας δίνει g(e) = 0 υπό κατασκευή της "g". Αυτό έρχεται σε αντίθεση με την υπόθεση ότι g(e) δεν ορίζεται. Και στις δύο περιπτώσεις εμφανίζεται αντίφαση. Ως εκ τούτου κάθε αυθαίρετη συνάρτηση "f" δεν μπορεί να είναι η συνάρτηση τερματισμού "h".

Τυποποίηση

Στην αρχική του απόδειξη ο Turing τυποποίησε την έννοια του "Αλγόριθμου" παρουσιάζοντας τις μηχανές Turing. Παρόλα αυτά το αποτέλεσμα δεν είναι πολύ συγκεκριμένο σε αυτές, απευθύνεται εξίσου σε κάθε άλλο μοντέλο υπολογισμού που είναι ισοδύναμο με την υπολογιστική δύναμη των μηχανών Turing, όπως είναι οι Μαρκοβιανοί αλγόριθμοι, Λογισμός λάμδα,Σύστημα Ποστ,Μηχανές καταγραφής,ή tag System.

Αυτό που έχει σημασία είναι ότι η τυποποίηση επιτρέπει μια άμεση χαρτογράφηση αλγορίθμων σε ένα είδος δεδομένων πάνω στα οποία μπορεί να λειτουργήσει ο αλγόριθμος. Για παράδειγμα αν η τυποποίηση επιτρέπει σε αλγόριθμους να ορίζουν συναρτήσεις χαρακτήρων (λέξεων),(όπως οι μηχανές Turing) τότε θα έπρεπε να υπάρχει μια χαρτογράφηση τέτοιων αλγορίθμων σε χαρακτήρες και αν η τυποποίηση επιτρέπει σε αλγόριθμους να ορίζουν συναρτήσεις φυσικών αριθμών (όπως οι υπολογίσιμες συναρτήσεις τότε θα έπρεπε να υπάρχει μια χαρτογράφηση αλγορίθμων σε φυσικούς αριθμούς. Η χαρτογράφηση σε χαρακτήρες είναι συνήθως η πιο άμεση , αλλά μεταφράζοντάς τους χαρακτήρες ως αριθμούς σε ένα n-ψήφιο αριθμητικό σύστημα

Η σχέση με τα Θεωρήματα μη Πληρότητας του Gödel

Οι έννοιες που αναπτύχθηκαν από τα Θεωρήματα μη Πληρότητας του Gödel είναι παρόμοιες με αυτές που αναπτύχθηκαν από το πρόβλημα τερματισμού, όπως και οι αποδείξεις.Για την ακρίβεια, μία πιο αδύναμη μορφή του Πρώτου Θεωρήματος μη Πληρότητας αποτελεί μια άμεση συνέπεια της μη αποφασισιμότητας του προβλήματος τερματισμού. Αυτή η αδύναμη μορφή διαφέρει από το κύριο συμπέρασμα του θεωρήματος μη πληρότητας υποστηρίζοντας οτι μία πλήρης, συνεκτική και έγκυρη αξιωματοποίηση όλων των προτάσεων για τους φυσικούς αριθμούς δεν είναι εφικτή. Το σημείο της "εγκυρότητας" αποτελεί και το αδύναμο σημείο: σημαίνει οτι χρειαζόμαστε ένα αξιωματικό σύστημα στην ερώτηση για να αποδείξουμε μόνο "αληθείς" προτάσεις για τους φυσικούς αριθμούς (είναι πολύ σημαντικό να παρατηρήσουμε οτι το συμπέρασμα της βασικής μορφής του Πρώτου Θεωρήματος της μη Πληρότητας του Gödel είναι ανεξάρτητο από την αμφισβήτηση της αλήθειας και αφορά μόνο την επίσημη αποδειξιμότητα).

Η αδύναμη μορφή του θεωρήματος μπορεί να αποδειχθεί από τη μη αποφασισιμότητα του προβλήματος τερματισμού ως εξής.Υποθέτοντας οτι έχουμε μία συνεκτική και πλήρη αξιωματοποίηση όλων των αληθών προτάσεων για τους φυσικούς αρθμούς.Τότε μπορούμε να δημιουργήσουμε έναν αλγόριθμο που απαριθμεί όλες αυτές τις προτάσεις.Αυτό σημαίνει οτι έχουμε έναν αλγόριθμο N(n),που δεδομένου ενός αριθμού n ,υπολογίζει μία πρόταση για τους φυσικούς αριθμούς όπως: για όλες τις αληθείς προτάσεις, υπάρχει τουλάχιστον ένα n τέτοιο ώστε το N(n) αποδίδει αυτή την πρόταση.Τώρα υποθέτοντας οτι θέλουμε να αποφασίσουμε,αν ο αλγόριθμος με την αναπαράσταση a σταματά για την εισαγωγή i.Χρησιμοποιώντας το Κleene's T κατηγορούμενο, μπορούμε να εκφράσουμε την πρόταση "Τοa σταματά στην εισαγωγή i όπως μια πρόταση H(a, i) στην γλώσσα της αριθμητικής. Εφόσον η αξιωματοποίση είναι πλήρης συνεπάγεται ότι είτε υπάρχει ένα n όπως το N(n) = H(a, i) είτε υπάρχει ένα n' όπως το N(n') = ¬ H(a, i). Έτσι εάν επαναλάβουμε για όλα τα n μέχρι να πάρουμε είτε H(a, i) έιτε το αρνητικό του,πάντα θα σταματάμε.Αυτό σημαίνει οτι μας δίνει έναν αλγόριθμο για να αποφασίσουμε για το πρόβλημα τερματισμού. Από τη στιγμή που ξέρουμε οτι δεν υπάρχει ένας τέτοιος αλγόριθμος, συμπεραίνουμε οτι η υπόθεση οτι υπάρχει υπάρχει μία συνεκτική και πλήρης αξιωματοποίηση όλων των αληθών προτάσεων για τους φυσικούς αριθμούς είναι εσφαλμένη.

Αναφορές

• Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230–265. online version This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
• Sipser, Michael (2006). «Section 4.2: The Halting Problem». Introduction to the Theory of Computation (2η έκδοση). PWS Publishing. σελίδες 173–182. ISBN 0-534-94728-X. 
• c2:HaltingProblem
• B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford UK, ISBN 0-19-825079-7.
• Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. . Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
• Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill. .
• Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
• Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses Chaitin proof. Includes little biographies of Emil Post, Julia Robinson.
• Marvin Minsky, Computation, Finite and Infinite Machines, Prentice-Hall, Inc., N.J., 1967. See chapter 8, Section 8.2 "The Unsolvability of the Halting Problem." Excellent, i.e. readable, sometimes fun. A classic.
• Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An over-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
• John Hopcroft and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass, 1979. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
• Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
• Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (first published 1970). Fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
• Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the Chaitin contributions.
• Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically inclined non-specialist. Discusses Gentzen's proof on pages 96–97 and footnotes. Appendices discuss the Peano Axioms briefly, gently introduce readers to formal logic.
• Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a Turing Machine model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
• Busy Beaver Programs are described in Scientific American, August 1984, also March 1985 p. 23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p. 396.
• David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
• Stephen Kleene, Introduction to Metamathematics, North-Holland, 1952. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.

Σύνδεσμοι

• Scooping the loop snooper
• animated movie
• A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium