Due ricercatori del MIT stanno mettendo alla prova la matematica così come la conosciamo oggi con l'aiuto di tre macchine di Turing. Chi vincerà la sfida?
Alan Turing (1912-1954). Le sue teorie potrebbero rivoluzionare la matematica come la conosciamo oggi.
Gli sguardi degli scienziati di tutto il mondo sono in questi giorni puntati su un software che sta funzionando su alcuni computer del MIT: se smetterà di funzionare, molte delle teorie matematiche sviluppate negli ultimi 150 anni saranno da cestinare. C’è da preoccuparsi? Probabilmente no, ma questa è una congettura...
Il programma è stato sviluppato da Scott Aaronson e Adam Yedidia e simula tre macchine di Turing. Si tratta cioè di una versione virtuale del modello computazionale creato nel 1936 dall’omonimo matematico.
LA MACCHINA DI TURING. Secondo Alan Turing ogni algoritmo informatico può essere eseguito da una macchina capace di leggere e scrivere sequenze di 0 e 1 su un nastro infinitamente lungo, in base a un set di regole elementari chiamate “stati”. All’aumentare della complessità dell’algoritmo cresce il numero di stati necessari a far funzionare la macchina.
Le macchine create da Aaronson e Yedidia stanno verificando problemi complessi della matematica, a volte irrisolti, come le Ipotesi di Riemann e gli schemi di distribuzione dei numeri primi.
NÉ VERO NÉ FALSO. Le macchine di Turing sono state utilizzate fin dagli anni ‘30 del secolo scorso per mettere alla prova ipotesi di questo tipo.
Il programma è stato sviluppato da Scott Aaronson e Adam Yedidia e simula tre macchine di Turing. Si tratta cioè di una versione virtuale del modello computazionale creato nel 1936 dall’omonimo matematico.
LA MACCHINA DI TURING. Secondo Alan Turing ogni algoritmo informatico può essere eseguito da una macchina capace di leggere e scrivere sequenze di 0 e 1 su un nastro infinitamente lungo, in base a un set di regole elementari chiamate “stati”. All’aumentare della complessità dell’algoritmo cresce il numero di stati necessari a far funzionare la macchina.
Le macchine create da Aaronson e Yedidia stanno verificando problemi complessi della matematica, a volte irrisolti, come le Ipotesi di Riemann e gli schemi di distribuzione dei numeri primi.
NÉ VERO NÉ FALSO. Le macchine di Turing sono state utilizzate fin dagli anni ‘30 del secolo scorso per mettere alla prova ipotesi di questo tipo.
Tra i primi a utilizzarle ci fu Kurt Gödel, il quale riuscì a provare che alcune formalizzazioni della matematica non possono mai essere dimostrate né confutate (primo teorema di incompletezza di Gödel): sono cioè indeterminate.
L’unico trucco per uscire da questa impasse è modificare le assunzioni che stanno alla base delle formalizzazioni. Ma questo porta a rendere indeterminate altre formalizzazioni. Ciò significa che non esistono assiomi di base che permettono di dimostrare tutto.
L’unico trucco per uscire da questa impasse è modificare le assunzioni che stanno alla base delle formalizzazioni. Ma questo porta a rendere indeterminate altre formalizzazioni. Ciò significa che non esistono assiomi di base che permettono di dimostrare tutto.
LA ZONA ZFC. Seguendo le ipotesi di Gödel, Turing dimostrò che era possibile costruire una macchina il cui comportamento non fosse prevedibile sulla base degli assiomi standard della teoria degli insiemi.
Questi ultimi, noti anche come ZFC (Zermelo-Fraenkel-Choice), sono 10 assiomi del tipo “due insiemi sono uguali se e solo se hanno gli stessi elementi”, dai quali derivano tutti i concetti alla base della matematica: numero, relazione, funzione, ordine eccetera.
IL TEST DI AARONSON E YEDIDIA. Aaronson e Yedidia sono quindi riusciti a costruire una macchina di Turing con 7.918 stati che risponde a queste caratteristiche e l’hanno battezzata Z. «Abbiamo provato a rendere concrete le ipotesi di Turing e a calcolare quanti stati erano necessari per portare la macchina in uno stato di indeterminatezza», spiega alla stampa Aaronson.
I due ricercatori hanno simulato la macchina su un computer, ma è teoricamente possibile costruirne una versione meccanica: una volta accesa, se tutte le ipotesi sottostanti fossero corrette, non dovrebbe mai smettere di funzionare (al netto di attriti, inefficienze varie e necessità di energia).
Z è programmata per funzionare all’infinito, in un ciclo virtualmente eterno attraverso i suoi 7918 stati. Se invece dovesse fermarsi, allora qualcosa all’interno di ZCF non è corretto. Se anche dovesse succedere, però, per risolvere il problema basterebbe utilizzare un set più stringente di assiomi, e sarebbe ancora possibile costruire un macchina di Turing in grado di soddisfare le nuove regole.
DIMOSTRARE IL FALSO. Non contenti, Aaronson e Yedidia hanno quindi costruito altre due macchine di Turing, che si fermeranno solo quando due teorie, oggi considerate vere, dovessero risultare false.
La prima è la congettura di Golbach, secondo la quale ogni numero pari maggiore di 2 è la somma di due numeri primi.
La seconda è l’ipotesi di Riemann, secondo la quale i numeri primi si distribuiscono secondo uno schema preciso. Quest’ultima è alla base di parte della moderna teoria dei numeri ed effettivamente, se si scoprisse che è falsa, potrebbe creare ben più di un problema.
A CHE COSA SERVE? Esprimere problemi di questo tipo come macchine di Turing permette di comprenderne in modo chiaro il livello di complessità: Z ha 7918 stati, la macchina di Goldbach 4888, la macchina di Rieman 5372.
Aaronson e Yedidia hanno pubblicato online il codice dei loro tre progetti e hanno sfidato i matematici di tutto il mondo a ridurre il numero di stati delle loro creature. Sul loro blog l’utente code golf addict sostiene di aver creato una macchina di Goldbach con soli 31 stati (ma è tutto da dimostrare). In ogni caso, l'obiettivo di Aaronson e Yedidia è quello: ridurre Z per scoprire i limiti di ZFC e della matematica così come la conosciamo oggi.
Commenti
Posta un commento