Teoremi di incompletezza di Gödel
La dimostrazione del 1931 che ogni sistema formale sufficientemente potente contiene verità che non può dimostrare — e non può nemmeno certificare la propria coerenza.
Kurt Gödel aveva 25 anni e lavorava a Vienna quando pubblicò l'articolo dal titolo poco accogliente Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Primo teorema: ogni sistema di assiomi coerente ed enumerabile meccanicamente, abbastanza forte per l'aritmetica, contiene enunciati che non si possono né dimostrare né confutare al suo interno. Secondo teorema: nessun sistema simile può dimostrare la propria coerenza. Il programma di Hilbert, pensato per dare alla matematica un fondamento definitivo, non era solo difficile ma impossibile.
L'eredità è la tecnica. Gödel numerò le formule: a ogni enunciato un numero, a ogni passo di dimostrazione una relazione aritmetica tra numeri, così che il sistema potesse parlare di sé senza uscire dall'aritmetica. Costruì poi un enunciato che, con quella codifica, afferma «io non sono dimostrabile». Se è dimostrabile è falso, e il sistema dimostra il falso. Se non è dimostrabile è vero — e indimostrabile.
Lo stesso argomento diagonale ricompare cinque anni dopo nel problema dell'arresto, nel teorema di Rice, nei quine e in ogni risultato su ciò che l'analisi statica non risolverà mai. Gödel codificò formule come numeri; una macchina di von Neumann conserva i programmi come dati nella stessa memoria. È un solo trucco, usato una volta come dimostrazione e una come modo di costruire cose.