“Nell'esperienza di chi sta vivendo oggi ci sono state almeno tre crisi importanti”. Così scriveva nel 1963, con un sentimento di residua ma evidente inquietudine, John von Neumann, lo scienziato a cui sono legate alcune delle innovazioni più rivoluzionarie e drammatiche del secolo XX, come l'ideazione del primo grande calcolatore costruito a Philadelphia intorno al 1945. Egli si riferiva in particolare all'“esame di coscienza” sui concetti di tempo e di spazio a cui costringeva la scoperta della teoria della relatività, alle difficoltà concettuali della meccanica quantistica e, infine, a quel breve e intenso capitolo della storia della matematica che prese il nome di “crisi dei fondamenti”. È proprio da quella crisi, che è stata poi oggetto di una ben congegnata rimozione, che occorre prendere le mosse per cogliere il significato dell'opera di Kurt Gödel, a cento anni dalla sua nascita.
La crisi dei fondamenti della matematica copre un periodo di circa tre decenni, dai due Convegni Internazionali, di matematica e di filosofia, svoltisi entrambi a Parigi nel 1900, fino alla dimostrazione, nel 1931, del celebre teorema di incompletezza di ogni (sufficientemente potente) formalizzazione dell'aritmetica da parte di Gödel. L'avvio di questo periodo ha coinciso con una dichiarazione di fiducia pressoché illimitata nei poteri del matematico, espressa da David Hilbert nella sua storica conferenza a Parigi, in cui erano pure elencati i famosi 23 problemi non ancora risolti, una sfida per la ricerca scientifica del XX Secolo. Sono proprio le parole di Hilbert a spiegare l'effetto deludente del teorema “negativo” di Gödel per le aspettative di una generazione di scienziati pronta a sottoscrivere l'audace dichiarazione del grande matematico Richard Dedekind: “noi siamo di razza divina e possediamo il potere di creare”.
La convinzione di Hilbert, che Gödel avrebbe ridimensionato, era in breve la seguente: lo spirito umano, incoraggiato dalle sue scoperte, ha ora una piena coscienza della propria indipendenza e della capacità di creare da sé problemi nuovi e fecondi, senza essere condizionato da necessità esterne. Questo potere gli viene dalla possibilità di tradurre le idee in sistemi di simboli la cui combinazione logica deriva da regole e assiomi che lui stesso è in grado di stabilire fin dall'inizio, così da poterne pure prevedere tutte le possibili conseguenze. La presentazione dei 23 problemi doveva certo risentire della forza di questo presupposto metodologico. In particolare, il secondo problema dell'elenco era quello della coerenza dell'aritmetica: dimostrare che gli assiomi che ci consentono di operare con le regole ordinarie del calcolo, unite all'assioma di continuità, non portano a risultati contraddittori dopo un numero finito di deduzioni logiche.
Dopo tre decenni, contro le aspettative di molti, Gödel dimostrò il famoso teorema di incompletezza dell'aritmetica: “non esiste alcun sistema con un numero finito di assiomi che sia completo anche soltanto rispetto alle proposizioni aritmetiche”. O, in altri termini, nei sistemi formali sufficientemente potenti (per descrivere l'aritmetica), come in particolare quello dei Principia mathematica di Whitehead e Russell, “esistono problemi relativamente semplici della teoria degli usuali numeri interi che non possono venir decisi sulla base degli assiomi” (anche se decidibili in base a “considerazioni di natura metamatematica”). Una conseguenza di questi risultati era la soluzione negativa del secondo dei 23 problemi di Hilbert: per gli stessi sistemi formali che contenevano proposizioni aritmetiche indecidibili era anche impossibile formulare, al loro interno, una dimostrazione della loro coerenza. Infine, gli stessi risultati di incompletezza escludevano una risposta positiva al secondo dei problemi, che prese il nome di Entscheidungsproblem o “problema della decisione”, posti da Hilbert e Ackermann nel 1928: trovare una procedura effettiva che stabilisse la validità di una qualsiasi formula prefissata della logica del primo ordine.
Quali furono le conseguenze di queste scoperte? La più ovvia fu il ridimensionamento del programma di Hilbert, che voleva formalizzare l'aritmetica dimostrandone la coerenza con metodi improntati al più rigoroso “finitismo”, per sventare i rischi — segnalati dai paradossi — di un uso indebito dell'infinito attuale nell'analisi e nella teoria degli insiemi. I primi e più autorevoli commenti sottolineavano la svolta critica e rivoluzionaria di questo ridimensionamento. Quine parlava di “crisi nella filosofia della matematica”. Hermann Weyl, che già nel 1921 aveva ufficializzato la “crisi dei fondamenti”, sottolineava ora l'importanza epocale dei risultati di Gödel, collegandoli a una lunga catena di esperienze filosofiche e letterarie: dall' Ars Magna di Lullo al calcolo universale di Leibniz; dalla più antica scienza dei paradossi alle innovazioni didattiche dell'Accademia di Lagado dei Gulliver's Travels di Swift. In un articolo del 1944, Emil Post ricavava la conclusione che, in assenza di un “meccanismo” decisionale, “il pensiero matematico è essenzialmente creativo”, dovendo limitarsi a un percorso spezzato ed empirico, diviso in serie di esperienze che si concatenano man mano in nuove sintesi e astrazioni. Ne derivava un “rovesciamento, almeno parziale, di tutto l'orientamento assiomatico del tardo Ottocento e del primo Novecento, con un ritorno al significato e alla verità come elementi intrinseci alla matematica”. Non troppo diversi sarebbero stati, più tardi, gli interessanti e approfonditi commenti di Jean Ladrière sui limiti dei formalismi.
I riferimenti al passato, a Lullo e a Leibniz, erano certo appropriati. E del resto le idee di Gödel avrebbero ben potuto riferirsi a concetti ed espedienti ancora più antichi. Il primo teorema di incompletezza dipendeva dal “metodo diagonale” già usato da Cantor per dimostrare la non numerabilità del corpo dei numeri reali. Questo metodo, come osserva Rogers, ha un'ampia portata, e “sembrerebbe gettare nel dubbio ogni nostra ricerca di una caratterizzazione formale. Suggerisce la possibilità che nessuna classe di funzioni algoritmiche caratterizzabile in modo formale possa corrispondere esattamente alla nozione informale di funzione algoritmica”. Il metodo diagonale di Cantor, che Émile Borel aveva interpretato come prova dell'esistenza di elementi indefinibili nel continuo geometrico, si basava su una semplice elencazione di numeri in ranghi ordinati e nella definizione di altri numeri che non potevano appartenere a questi ranghi. Ma sono proprio queste tecniche di elencazione, di numerazione e di sistemazione in ranghi che fin dai tempi più remoti rappresentavano la possibilità di definire o censire oggetti o persone. E lo stesso concetto di logos , nella letteratura matematica, filosofica, epica e tragica dell'antica Grecia, si basava sull'idea di appartenenza a ranghi definiti. I risultati di Gödel miravano dunque anche alla problematicità di questa idea, con tecniche che implicavano una perfetta simbiosi tra numeri e formule linguistiche.
La prima reazione emotiva di scoraggiamento di fronte ai risultati di incompletezza dovette tuttavia, col tempo, letteralmente capovolgersi. Quei risultati, infatti, non impediscono realizzazioni parziali del programma di Hilbert, nel senso che porzioni non trascurabili di matematica, che includono teoremi non costruttivi e l'uso dell'infinito, sono riducibili a ragionamenti puramente “finitisti”. Lo stesso Gödel era piuttosto cauto nel sancire la crisi del programma di Hilbert. Inoltre, come ha notato Gregory Chaitin, molte altre dimostrazioni dei risultati di Gödel sono ora disponibili, tanto che quegli stessi risultati appaiono oggi relativamente ovvi e facili da ottenere. Una svolta si deve alle successive ricerche, negli anni '30 e '40, di Turing, Church, Post, Kleene, Markov (e di altri ancora, come Kolmogorov e lo stesso Chaitin) sulla natura degli algoritmi, e sui limiti della calcolabilità. Alan Turing, nel celebre articolo del 1936 in cui introduceva il suo calcolatore ideale noto come “macchina di Turing”, dimostrò che l' Entscheidungsproblem non può avere soluzione. Il primo teorema di incompletezza di Gödel deriva in modo immediato dal risultato di Turing.
Un momento critico fu poi la realizzazione, intorno alla metà del XX secolo, del primo calcolatore della storia, di quella complessa macchina sintattica che realizzava in concreto il modello di Turing e spostava il progetto teorico di riduzione della matematica a pura manipolazione di segni sul piano di un calcolo scientifico di grande scala. Prese slancio, da allora, un nuovo interesse per gli algoritmi e per gli aspetti più applicativi di uno strumento che già Gödel aveva usato per dimostrare il primo teorema di incompletezza, lo strumento cioè della ricorsione. L'idea di ricorsione, sperimentata fin dai calcoli della matematica antica, era ora indispensabile per definire il concetto stesso di algoritmo e per controllarne la complessità.
Lo studio sistematico della complessità degli algoritmi divenne ben presto inevitabile e si affiancò alle ricerche più teoriche sui fondamenti del calcolo. Non ha solo importanza sapere, evidentemente, se un problema ammette una soluzione algoritmica; occorre anche assicurarsi che l'algoritmo abbia una complessità accettabile. A questo importante passaggio dalla calcolabilità teorica a quella concreta accennava lo stesso Gödel in una lettera a von Neumann del 1956. Gödel si chiedeva precisamente con quante operazioni si riesce a sapere se un numero intero è primo e se uno dei problemi che si chiamano oggi “NP completi”, secondo la definizione di Stephen Cook del 1971, poteva essere risolto in tempo polinomiale (lineare o quadratico, sperava Gödel). Quale sia la complessità dei problemi NP completi è ancora oggi una delle più importanti questioni irrisolte della scienza del calcolo, e il loro studio si avvale di tecniche, come la riducibilità, già utilizzate per l'analisi di problemi indecidibili. Se i teoremi di incompletezza dimostravano l'insufficienza dei formalismi nel legittimare l'uso matematico dell' infinito, gli studi sulla complessità e sull'efficienza degli algoritmi rivelavano le difficoltà dei calcoli con un numero finito di operazioni. Anche di questo delicato e significativo spostamento di interesse dai paradossi dell'infinito alla complessità e problematicità del finito, Gödel ebbe una precisa e precoce consapevolezza. La scienza degli algoritmi era servita sia a formulare le grandi congetture di Hilbert sia a confutarle. Ora essa si rivelava anche come la possibile via di spiegazione e di rimozione della crisi che ne era conseguita.