Scienze

La macchina di Turing che sfida la matematica

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?

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.

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.


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.

14 maggio 2016 Rebecca Mantovani
Ora in Edicola
Scopri il mondo Focus. Ogni mese in edicola potrai scegliere la rivista che più di appassiona. Focus il magazine di divulgazione scientifica più letto in Italia, Focus Storia per conoscere la storia in modo nuovo ed avvincente e Focus Domande & Risposte per chi ama l'intrattenimento curioso e intelligente.

Focus Storia ci porta indietro al 1914, l'anno fatale che segnò l'inizio della Prima Guerra Mondiale. Attraverso un'analisi dettagliata degli eventi, delle alleanze politiche e degli imperi coloniali, la rivista ricostruisce il contesto storico che portò al conflitto.

Scopriremo le previsioni sbagliate, le ambiguità e il gioco mortale delle alleanze che contribuirono a scatenare la guerra. Un focus sulle forze in campo nel 1914 ci mostrerà l'Europa divisa in due blocchi pronti allo scontro, mentre un'analisi delle conseguenze della pace di Versailles ci spiegherà perché non durò a lungo.

Non mancano le storie affascinanti come quella di Agnès Sorel, amante di Carlo VII, e di Moshe Feldenkrais, inventore dell'omonimo metodo terapeutico. Un viaggio nell'arte ci porterà alla scoperta della Street Art e della Pop Art nel nuovo JMuseo di Jesolo, mentre uno sguardo alla scienza ci farà conoscere le scienziate che non hanno avuto i meritati riconoscimenti.

ABBONATI A 29,90€

Focus si immerge nel Mediterraneo con un dossier speciale: un ecosistema minacciato, ma ricco di biodiversità e aree marine protette cruciali. Scopriremo l'importanza della Posidonia oceanica e le minacce alla salute del mare.

La rivista esplora anche scienza e tecnologia, svelando i segreti dei papiri di Ercolano e portandoci dietro le quinte del supercomputer Leonardo. Un viaggio nell'archeoastronomia e un'inchiesta sul ruolo del tatto nella società umana arricchiscono il numero.

Non mancano approfondimenti sulla salute, con un focus sull'Alzheimer e consigli per migliorare il sonno. La tecnologia è protagonista con uno sguardo al futuro dei gasdotti italiani e alle innovazioni nel campo delle infrastrutture. Infine, uno sguardo all'affascinante mondo dell'upupa.

ABBONATI A 31,90€
Follow us