Entscheidungsproblem

[image error]

Al grande pubblico, il nome di David Hilbert dice ben poco ed è un vero peccato, perchè oltre a essere uno dei più grandi matematici della storia, era un tipo un gran donnaiolo, un abile ballerino e un apprezzato oratore.

Aveva una vena irriverente ed era assolutamento al conservatorismo della Germania guglielmina: scandalizzava i ben pensanti di Gottinga per la sua passione per le operette, per il suo smodato amore per il biliardo, passava le nottate a giocare con i suoi studenti nei retro dei peggiori bar e fu il primo nella sua facoltà, ad avere un’assistente donna.

Ovviamente, ogni tanto ne combinava qualcuna delle sue: ad esempio, un giorno uno studente gli consegnò uno scritto in cui asseriva di dimostrare l’ipotesi di Riemann. Hilbert studiò attentamente il lavoro e rimase davvero impressionato dalla profondità dell’argomentazione; purtroppo però vi trovò un errore che neppure lui fu in grado di eliminare. Un anno dopo quello studente morì. Hilbert chiese ai genitori afflitti il permesso di tenere un’orazione funebre. Mentre sotto la pioggia i parenti e gli amici piangevano sulla tomba, Hilbert sì fece avanti.

Cominciò con il dire quale tragedia fosse che un giovane così dotato fosse morto prima dì aver avuto l’opportunità di mostrare Ì successi che avrebbe potuto conseguire. Ma, continuò, anche se la dimostrazione dell’ipotesi dì Riemann elaborata da questo giovane conteneva un errore, era ancora possibile che un giorno si trovasse una dimostrazione del famoso problema seguendo le linee che il defunto aveva indicato.

In effetti – proseguì con entusiasmo, in piedi sotto la pioggia vicino alla tomba del morto – si consideri una funzione di variabile complessa…

Un’altra volta, Hilbert era stato visto in giro per diversi giorni con un paio dì pantaloni strappati, cosa che per molti sarebbe stata fonte di imbarazzo. Il compito di avvertirlo con tatto venne affidato al suo assistente, Richard Courant. Sapendo quanto Hilbert amasse passeggiare in campagna discutendo di matematica, Courant Io invitò per una camminata. Courant fece in modo di passare attraverso alcuni cespugli spinosi, e a quel punto fece notare a Hilbert di essersi strappato in maniera vistosa i pantaloni su uno dei cespugli.

«Oh no – replicò Hilbert – sono così da settimane, ma nessuno se ne è accorto».

Ora, per capire il suo genio, Hilbert, più per hobby e per sbeffeggiare Einstein, che per effettivo interesse, fu il primo a scoprire le equazioni di campo per la teoria della relatività generale, ma non fare venire un coccolone a zio Albert, sotto alcuni aspetti molto suscettibile, evitò di rivendicarne la paternità: a essere sinceri, la dimostrazione di Hilbert è assai più contorta, meno pratica ed elegante di quella di Einstein.

Nel 1899, Hilbert aveva pubblicato il saggio Grundlagen der Geometrie (in italiano: Fondamenti della Geometria), allo scopo di fornire un rigore e un formalismo assiomatico (confrontabili con quelli dell’algebra e dell’analisi matematica) anche alla geometria; per far questo, sostituì agli assiomi di Euclide un insieme formale, composto di 20 assiomi, per evitarne le contraddizioni formali.

Dato che l’appetito vien mangiando, Hilbert si mise in testa di estendere questo approccio all’intera matematica: la sua idea era di ricondurre logicamente teorie complesse ad altre più, fino a basare l’intera matematica sull’aritmetica; provando la consistenza di questa ne sarebbe seguita la completezza e la non contraddittorietà di tutta la matematica. In tal modo, per qualsiasi congettura matematica si fosse formulata, si sarebbe potuto dimostrare in maniera rigorosa, se questa fosse vera o falsa.

Per cui, nel 1928, formulò il Entscheidungsproblem, che non è un colorito insulto in tedesco, ma significa “problema della decisione”; determinare, se esiste, un metodo meccanico, noi biechi tizi che bazzicano l’IT lo chiameremmo algoritmo che permetta di stabilire per ogni possibile affermazione matematica se questa è vera oppure no, appunto deciderne la verità.

[image error]

Ahimè, il sogno di Hilbert fu messo in crisi da un tizio ancora più bizzarro Kurt Gödel, tanto geniale, quanto fuori di cocuzza: ipocondriaco e paranoico, aveva l’irrazionale paura di venire avvelenato, tanto che sua moglie, Adele Nimbursky, ballerina in un night, divorziata, più vecchia di lui di sei anni, divenne la sua “assaggiatrice” ufficiale.

Kurt, nel 1930, dimostrò i due famigerati teoremi di incompletezza: il primo, semplificato all’osso, i miei amici matematici mi sputeranno in un occhio, afferma come una costruzione assiomatica non possa soddisfare contemporaneamente le proprietà di coerenza e completezza. Se dagli assiomi viene dedotta l’intera aritmetica, essi portano ad una contraddizione; se i teoremi derivati non sono contraddittori, esiste almeno un teorema non dimostrabile a partire da quei soli assiomi, un caso indecidibile del quale non si può dire se sia vero oppure falso.

Biecamente, in un sistema formale sufficientemente complesso, esisteranno sempre concetti che potrebbero essere veri, ma che non possiamo dimostrare.

Il secondo teorema, invece, sempre semplificando il più possibile, afferma

Nessun sistema, che sia abbastanza coerente ed espressivo da contenere l’aritmetica, può essere utilizzato per dimostrare la sua stessa coerenza.

Indi per cui, esisteranno enunciati matematici relativi ai numeri interi che non solo non potranno essere dimostrati, ma neppure confutati: di conseguenza, se l’aritmetica non è coerente, non lo è neppure una matematica più complessa da questa derivata.

[image error]

A peggiorare il tutto, ci si mise il buon Alan Turing, che si mise di buzzo buono per risolvere l’Entscheidungsproblem. Per far questo, immaginò una sorta di computer ideale, che noi, in suo onore, chiamiamo macchina di Turing.

Questa computer immaginario, è costituito un nastro infinito in entrambe le direzioni, diviso in caselle ciascuna delle quali può contenere il simbolo 0 oppure il simbolo 1, che ne rappresenta la memoria, eda una testina che può leggere il simbolo, 0 oppure 1, contenuto in una casella e scrivere un simbolo in una casella, e può muoversi lungo il nastro, una casella per volta. L’input di tale computer è costituito dai simboli scritti originariamente sul nastro, l’output da ciò che rimane sopra quando la macchina di Turing smette di funzionare.

Dopo avere costruito il suo immaginario modello matematico di computer, Alan dimostò come esiste una domanda semplice relativa alle Macchine di Turing a cui nessuna procedura matematica potrà dare una risposta. Ossia, dato un algoritmo e i suoi input, non possibile determinare a priori se la Macchina di Turing terminerà i suoi calcoli in un tempo finito o entrerà in loop, continuando all’infinito.

Per cui, non può esistere un algoritmo che permetta di appurare la verità di tutte le affermazioni matematiche. Tutto questo cinema, oltre a dare origine all’Informatica, e quindi farmi portare ogni mese a casa lo stipendio, cosa per cui sono sommmamente grato a Hilbert, Gödel e Turing, senza di loro starei a zappare la terra, è estendibile a diversi sistemi formali.

Ad esempio, è il motivo perchè la Teologia, con buona pace di San Tommaso d’Aquino, non può dimostrare razionalmente l’esistenza di Dio. O perchè l’Intelligenza Artificiale ha gli stessi limiti di quella Umana.

In tempi recenti, Toby Cubitt dello University College London ha esteso la questione anche alla Meccanica quantistica, in relazione a un problema apparentemente semplice, quello del calcolo del gap spettrale di un materiale, ossia la differenza tra il più basso livello di energia che gli elettroni possono occupare in un materiale e quello successivo. Si tratta di un parametro da cui dipende, per esempio, l’eventuale trasformazione del materiale in superconduttore.

Utilizzando un modello teorico, che simula un reticolo bidimensionale di atomi e, sfruttando le analogie tra stati quantistici degli atomi e processi di una macchina di Turing, Cubitt ha scoperto che nel caso di reticoli infiniti è impossibile sapere se il calcolo del gap termina.

Li er Barista se ne uscirebbe con espressione romanesca alquanto volgare, dato che gli oggetti reali sono finiti e che quindi vuoi o non vuoi, il calcolo ha sempre una soluzione: Il problema però, ha spiegato Cubitt, è che anche in caso di reticoli finiti per i quali il gap spettrale sia noto, è impossibile dimostrare se, aggiungendo anche un solo atomo, sia ancora possibile calcolarlo.

Ciò impatta anche su un complesso problema matematico, la congettura di Yang-Mills (o del gap di massa): si tratta di uno di quei Problemi del Millennio che frutterebbe a chi riesce a dimostrarne la veridicità o la falsità un milione di dollari messo in palio dal Clay Mathematics Institute. Il problema del gap di massa riguarda il fatto che le particelle che trasportano la forza nucleare debole e quella forte hanno massa, mentre i fotoni, che portano la forza elettromagnetica, sono privi di massa: per risolverlo Chen-Ning Yang e Robert Mills ipotizzarono nel 1954 l’esistenza di un analogo quantistico della teoria di Maxwell, adottando una matematica non commutativa, ossia in cui a+b da un risultato diverso da b+a. Cubitt e colleghi potrebbero dimostrare che non si può decidere se la congettura Yang-Mills sia vera o falsa.