Filosofia dell'informazione/Computazione: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 55:
==The Entscheidungsproblem==
L'Entscheidungsproblem, o problema decisionale, era la principale preda di Turing in "Numeri OnComputabili". Il problema decisionale fu portato alla ribalta dalla matematica dal matematico tedesco David Hilbert Hilbert ei suoi seguaci sostenevano che i matematici dovrebbero cercare di esprimere la matematica nella forma di un sistema formale completo, coerente, decidibile - un sistema che esprime "l'intero contenuto del pensiero della matematica in modo uniforme" (Hilbert 1927: 475).
Il progetto di formulare la matematica in questo modo divenne noto come "Hilbertprogram". Un sistema coerente è quello che non contiene contraddizioni; un sistema completo in cui ogni vera affermazione matematica è dimostrabile. Un sistema completo, coerente, decidibile bandirebbe l'ignoranza dalla matematica. Data qualsiasi affermazione matematica, si sarebbe in grado di dire se l'affermazione è vera o falsa decidendo se è dimostrabile nel sistema. Hilbert ha dichiarato importante il sistema che esprime "tutto il contenuto del pensiero della matematica" dove questo deve essere coerente.
Un sistema incoerente - un sistema che contiene contraddizioni - è inutile, dal momento che qualsiasi affermazione, vera o falsa, può essere derivata da una contraddizione mediante semplici passaggi logici.
Quindi in un sistema incoerente, sono dimostrabili assurdità come 0 = 1 e 6 ≠ 6. Un sistema indecidibile potrebbe, a volte, lasciarci nell'ignoranza. Solo se il sistema matematico fosse decidibile potremmo essere fieri di poter sempre dire se una determinata affermazione è dimostrabile o meno.
Sfortunatamente per il programma ''Hilbert'' è diventato chiaro che i sistemi matematici più interessanti sono, se coerenti, incompleti e indecidibili. Nel 1931 Gödel dimostrò che l'ideale di Hilbert è impossibile da soddisfare, anche nel caso della semplice aritmetica. Ha dimostrato che il sistema chiamato aritmetica Peano è, se coerente, incompleto. Questo è noto come il primo teorema di incompletezza di Gödel. (In seguito, Gödel ha generalizzato questo risultato, sottolineando che "a causa del lavoro di Turing, può ora essere fornita una definizione precisa e indiscutibilmente adeguata del concetto generale di sistema formale", con la conseguenza che l'incompletezza può "essere dimostrata rigorosamente per ogni coerente sistema contenente un certo importo.
| |||