Quanto sono vicini i computer all’automazione del ragionamento matematico?
Negli anni '70, il compianto matematico Paul Cohen, l'unica persona ad aver mai vinto una medaglia Fields per il lavoro in logica matematica, avrebbe fatto una previsione radicale che continua a eccitare e irritare i matematici: che "in un momento futuro non specificato, i matematici sarebbero stati sostituiti dai computer. " Cohen, leggendario per i suoi metodi audaci nella teoria degli insiemi, predisse che tutta la matematica poteva essere automatizzata, inclusa la scrittura di dimostrazioni.
Una dimostrazione è un argomento logico passo passo che verifica la verità di una congettura o di una proposizione matematica. (Una volta dimostrata, una congettura diventa un teorema.) Stabilisce la validità di un'affermazione e spiega perché è vera. Una prova è strana, però. È astratto e non legato all'esperienza materiale. "Sono questo pazzo contatto tra un mondo immaginario, non fisico e creature biologicamente evolute", ha detto lo scienziato cognitivo Simon DeDeo della Carnegie Mellon University, che studia la certezza matematica analizzando la struttura delle prove. "Non ci siamo evoluti per farlo".
I computer sono utili per grandi calcoli, ma le prove richiedono qualcosa di diverso. Le congetture nascono dal ragionamento induttivo – una sorta di intuizione su un problema interessante – e le prove generalmente seguono la logica deduttiva, passo dopo passo. Spesso richiedono un pensiero creativo complicato e il lavoro più laborioso di colmare le lacune e le macchine non possono ottenere questa combinazione.
I dimostratori di teoremi computerizzati possono essere suddivisi in due categorie. I dimostratori di teoremi automatizzati, o ATP, utilizzano tipicamente metodi di forza bruta per analizzare grandi calcoli. I dimostratori di teoremi interattivi, o ITP, agiscono come assistenti di prova che possono verificare l'accuratezza di un argomento e controllare le prove esistenti per gli errori. Ma queste due strategie, anche se combinate (come nel caso dei dimostratori di teoremi più recenti), non si sommano al ragionamento automatico.
Inoltre, gli strumenti non sono stati accolti a braccia aperte e la maggior parte dei matematici non li usa né li accoglie con favore. "Sono molto controversi per i matematici", ha detto DeDeo. "Alla maggior parte di loro non piace l'idea."
Una formidabile sfida aperta sul campo chiede quante prove possono essere effettivamente automatizzate: un sistema può generare una congettura interessante e dimostrarla in un modo che le persone capiscono? Una serie di recenti progressi dai laboratori di tutto il mondo suggerisce modi in cui gli strumenti di intelligenza artificiale possono rispondere a questa domanda. Josef Urban dell'Istituto ceco di informatica, robotica e cibernetica di Praga sta esplorando una varietà di approcci che utilizzano l'apprendimento automatico per aumentare l'efficienza e le prestazioni dei prover esistenti. A luglio, il suo gruppo ha riportato una serie di congetture e prove originali generate e verificate dalle macchine. E a giugno, un gruppo di Google Research guidato da Christian Szegedy ha pubblicato i risultati recenti degli sforzi per sfruttare i punti di forza dell'elaborazione del linguaggio naturale per rendere le prove informatiche più apparentemente umane nella struttura e nella spiegazione.
Alcuni matematici vedono i dimostratori di teoremi come uno strumento potenzialmente rivoluzionario per la formazione degli studenti universitari nella scrittura di prove. Altri dicono che convincere i computer a scrivere le prove non è necessario per il progresso della matematica e probabilmente impossibile. Ma un sistema in grado di prevedere un'utile congettura e dimostrare un nuovo teorema realizzerà qualcosa di nuovo – una versione della macchina della comprensione, ha detto Szegedy. E questo suggerisce la possibilità di automatizzare la ragione stessa.
Macchine utili
Matematici, logici e filosofi hanno a lungo discusso su quale parte della creazione di prove sia fondamentalmente umana, e i dibattiti sulla matematica meccanizzata continuano ancora oggi, specialmente nelle profonde valli che collegano l'informatica e la matematica pura.
Per gli informatici, i dimostratori di teoremi non sono controversi. Offrono un modo rigoroso per verificare che un programma funzioni e gli argomenti sull'intuizione e la creatività sono meno importanti che trovare un modo efficiente per risolvere un problema. Al Massachusetts Institute of Technology, ad esempio, lo scienziato informatico Adam Chlipala ha progettato strumenti per la dimostrazione di teoremi che generano algoritmi crittografici – tradizionalmente scritti da esseri umani – per salvaguardare le transazioni su Internet. Già, il codice del suo gruppo viene utilizzato per la maggior parte delle comunicazioni sul browser Chrome di Google.
"Puoi prendere qualsiasi tipo di argomento matematico e codificarlo con un unico strumento e collegare i tuoi argomenti insieme per creare prove di sicurezza", ha detto Chlipala.
In matematica, i dimostratori di teoremi hanno contribuito a produrre dimostrazioni complicate e pesanti che altrimenti avrebbero occupato centinaia di anni di vita dei matematici. La congettura di Keplero , che descrive il modo migliore per impilare le sfere (o, storicamente, arance o palle di cannone), offre un esempio significativo. Nel 1998, Thomas Hales , insieme al suo allievo Sam Ferguson, ha completato una dimostrazione utilizzando una varietà di tecniche matematiche computerizzate. Il risultato è stato così macchinoso – i risultati hanno richiesto 3 gigabyte – che 12 matematici lo hanno analizzato per anni prima di annunciare di essere sicuri al 99% che fosse corretto.
La congettura di Keplero non è l'unica famosa questione risolta dalle macchine. Il teorema dei quattro colori , che dice che sono necessarie solo quattro tonalità per colorare qualsiasi mappa bidimensionale in modo che nessuna delle due regioni adiacenti condividano un colore, è stato risolto nel 1977 dai matematici utilizzando un programma per computer che ha sfornato mappe a cinque colori per mostrarle potrebbero essere ridotti tutti a quattro. E nel 2016, un trio di matematici ha utilizzato un programma per computer per dimostrare una sfida aperta di lunga data chiamata problema booleano delle triple pitagoriche, ma la versione iniziale della dimostrazione era di 200 terabyte. Con una connessione Internet ad alta velocità, una persona potrebbe scaricarlo in poco più di tre settimane.
Sentimenti complicati
Questi esempi sono spesso strombazzati come successi, ma hanno anche contribuito al dibattito. Il codice del computer che dimostrava il teorema dei quattro colori, stabilito più di 40 anni fa, era impossibile per gli esseri umani verificarlo da soli. "I matematici hanno discusso da allora se si tratta o meno di una prova", ha detto il matematico Michael Harris della Columbia University.
Un altro problema è che se vogliono usare dimostratori di teoremi, i matematici devono prima imparare a programmare e poi capire come esprimere il loro problema in un linguaggio adatto al computer – attività che sminuiscono l'atto di fare matematica. "Quando avrò riformulato la mia domanda in una forma che potesse adattarsi a questa tecnologia, avrei risolto il problema da solo", ha detto Harris.
Molti semplicemente non vedono la necessità di risolutori di teoremi nel loro lavoro. "Hanno un sistema, carta e matita, e funziona", ha detto Kevin Buzzard , un matematico dell'Imperial College di Londra che tre anni fa ha spostato il suo lavoro dalla matematica pura per concentrarsi su dimostratori di teoremi e dimostrazioni formali. "I computer hanno fatto calcoli sorprendenti per noi, ma non hanno mai risolto un problema difficile da soli", ha detto. "Fino a quando non lo faranno, i matematici non compreranno questa roba."
Ma Buzzard e altri pensano che forse dovrebbero. Per prima cosa, "le prove del computer potrebbero non essere così aliene come pensiamo", ha detto DeDeo. Recentemente, insieme a Scott Viteri, uno scienziato informatico ora alla Stanford University, ha decodificato una manciata di famose dimostrazioni canoniche (inclusa una dagli Elementi di Euclide ) e dozzine di dimostrazioni generate dalla macchina, scritte usando un prover di teoremi chiamato Coq, per guardare per punti in comune. Hanno scoperto che la struttura in rete delle prove automatiche era notevolmente simile alla struttura delle prove fatte dalle persone. Questo tratto comune, ha detto, può aiutare i ricercatori a trovare un modo per ottenere assistenti di prova per, in un certo senso, spiegare se stessi.
"Le prove automatiche potrebbero non essere misteriose come sembrano", ha detto DeDeo.
Altri dicono che i dimostratori di teoremi possono essere utili strumenti didattici, sia in informatica che in matematica. Alla Johns Hopkins University, la matematica Emily Riehl ha sviluppato corsi in cui gli studenti scrivono dimostrazioni usando un dimostratore di teoremi. "Ti costringe ad essere molto organizzato e pensare chiaramente", ha detto. "Gli studenti che scrivono le prove per la prima volta possono avere difficoltà a sapere di cosa hanno bisogno e a comprendere la struttura logica".
Riehl dice anche che sta usando sempre più dimostratori di teoremi nel suo lavoro. "Non è necessariamente qualcosa che devi usare tutto il tempo e non sostituirà mai lo scarabocchio su un pezzo di carta", ha detto, "ma l'uso di un assistente per le prove ha cambiato il modo in cui penso di scrivere le prove".
I dimostratori di teoremi offrono anche un modo per mantenere il campo onesto. Nel 1999, il matematico russo americano Vladimir Voevodsky ha scoperto un errore in una delle sue dimostrazioni. Da allora fino alla sua morte nel 2017, è stato un sostenitore vocale dell'uso dei computer per controllare le prove. Hales ha detto che lui e Ferguson hanno trovato centinaia di errori nella loro prova originale quando l'hanno controllata con i computer. Anche la primissima proposizione negli Elementi di Euclide non è perfetta . Se una macchina può aiutare i matematici a evitare tali errori, perché non approfittarne? (L'obiezione pratica, giustificata o meno, è quella suggerita da Harris: se i matematici devono passare il loro tempo a formalizzare la matematica per essere compresi da un computer, è tempo che non passano a fare nuova matematica.)
Ma Timothy Gowers , matematico e medaglia Fields presso l'Università di Cambridge, vuole andare anche oltre: immagina un futuro in cui i dimostratori di teoremi sostituiranno gli arbitri umani nelle principali riviste. "Vedo che sta diventando una pratica standard che se vuoi che il tuo documento venga accettato, devi farlo superare un controllo automatico", ha detto.
Parlare con i computer
Ma prima che i computer possano controllare universalmente o persino escogitare prove, i ricercatori devono prima eliminare un ostacolo significativo: la barriera di comunicazione tra il linguaggio degli esseri umani e il linguaggio dei computer.
I dimostratori di teoremi di oggi non sono stati progettati per essere compatibili con i matematici. Gli ATP, il primo tipo, vengono generalmente utilizzati per verificare se un'affermazione è corretta, spesso testando possibili casi. Chiedi a un ATP di verificare che una persona possa guidare da Miami a Seattle, ad esempio, e potrebbe cercare in tutte le città collegate da strade che partono da Miami e alla fine trovare una città con una strada che porta a Seattle.
Con un ATP, un programmatore può codificare tutte le regole, o assiomi, e poi chiedere se una particolare congettura segue quelle regole. Il computer quindi fa tutto il lavoro. "Devi solo digitare la congettura che vuoi dimostrare e speri di ottenere una risposta", ha detto Daniel Huang, uno scienziato informatico che ha recentemente lasciato l'Università della California, Berkeley, per lavorare in una startup.
Ma ecco il problema: ciò che un ATP non fa è spiegare il suo lavoro. Tutto quel calcolo avviene all'interno della macchina e agli occhi umani sembrerebbe una lunga serie di 0 e 1. Huang ha detto che è impossibile scansionare la prova e seguire il ragionamento, perché sembra un mucchio di dati casuali. "Nessun umano guarderà mai quella prova e sarà in grado di dire, 'Ho capito'", ha detto.
Gli ITP, la seconda categoria, hanno vasti set di dati contenenti fino a decine di migliaia di teoremi e prove, che possono scansionare per verificare che una dimostrazione sia accurata. A differenza degli ATP, che operano in una sorta di scatola nera e sputano solo una risposta, gli ITP richiedono l'interazione umana e persino una guida lungo il percorso, quindi non sono così inaccessibili. "Un umano potrebbe sedersi e capire quali sono le tecniche a livello di prova", ha detto Huang. (Questi sono i tipi di prove macchina studiate da DeDeo e Viteri.)
Gli ITP sono diventati sempre più popolari negli ultimi anni. Nel 2017, il trio dietro il problema delle triple booleane pitagoriche ha utilizzato Coq, un ITP, per creare e verificare una versione formale della loro prova; nel 2005 Georges Gonthier della Microsoft Research Cambridge ha usato Coq per formalizzare il teorema dei quattro colori. Hales ha anche utilizzato ITP chiamati HOL Light e Isabelle sulla prova formale della congettura di Keplero. ("HOL" sta per "logica di ordine superiore".)
Gli sforzi in prima linea nel campo oggi mirano a fondere l'apprendimento con il ragionamento. Spesso combinano ATP con ITP e integrano anche strumenti di apprendimento automatico per migliorare l'efficienza di entrambi. Immaginano programmi ATP / ITP che possono utilizzare il ragionamento deduttivo – e persino comunicare idee matematiche – allo stesso modo delle persone, o almeno in modi simili.
I limiti della ragione
Josef Urban pensa che l'unione di ragionamento deduttivo e induttivo richiesto per le prove possa essere raggiunto attraverso questo tipo di approccio combinato. Il suo gruppo ha costruito dimostratori di teoremi guidati da strumenti di apprendimento automatico , che consentono ai computer di apprendere da soli attraverso l'esperienza. Negli ultimi anni, hanno esplorato l'uso delle reti neurali, strati di calcoli che aiutano le macchine a elaborare le informazioni attraverso un'approssimazione approssimativa dell'attività neuronale del nostro cervello. A luglio, il suo gruppo ha riferito di nuove congetture generate da una rete neurale addestrata sui dati di dimostrazione di teoremi.
Urban è stato parzialmente ispirato da Andrej Karpathy, che alcuni anni fa ha addestrato una rete neurale per generare assurdità dall'aspetto matematico che sembravano legittime ai non esperti. Urban non voleva sciocchezze, però: lui e il suo gruppo hanno invece progettato il proprio strumento per trovare nuove prove dopo essersi allenati su milioni di teoremi. Quindi hanno utilizzato la rete per generare nuove congetture e verificato la validità di tali congetture utilizzando un ATP chiamato E.
La rete ha proposto più di 50.000 nuove formule, sebbene decine di migliaia fossero duplicati. "Sembra che non siamo ancora in grado di dimostrare le congetture più interessanti", ha detto Urban.
Szegedy di Google Research vede la sfida dell'automazione del ragionamento nelle prove informatiche come un sottoinsieme di un campo molto più ampio: l'elaborazione del linguaggio naturale, che implica il riconoscimento di schemi nell'uso di parole e frasi. (Il riconoscimento di modelli è anche l'idea alla base della visione artificiale, l'oggetto del precedente progetto di Szegedy a Google.) Come altri gruppi, il suo team vuole dimostratori di teoremi in grado di trovare e spiegare prove utili.
Ispirato dal rapido sviluppo di strumenti di intelligenza artificiale come AlphaZero – il programma DeepMind che può sconfiggere gli esseri umani a scacchi, Go e shogi – il gruppo di Szegedy vuole capitalizzare i recenti progressi nel riconoscimento della lingua per scrivere prove. I modelli linguistici, ha detto, possono dimostrare un ragionamento matematico sorprendentemente solido.
Il suo gruppo presso la ricerca Google ha recentemente descritto un modo per utilizzare i modelli linguistici, che spesso utilizzano reti neurali, per generare nuove prove. Dopo aver addestrato il modello a riconoscere una sorta di struttura ad albero in teoremi noti per essere veri, hanno eseguito una sorta di esperimento in forma libera, chiedendo semplicemente alla rete di generare e dimostrare un teorema senza ulteriori indicazioni. Delle migliaia di congetture generate, circa il 13% era sia dimostrabile che nuovo (il che significa che non duplicava altri teoremi nel database). L'esperimento, ha detto, suggerisce che la rete neurale potrebbe insegnare a se stessa una sorta di comprensione di come appare una prova.
"Le reti neurali sono in grado di sviluppare uno stile artificiale di intuizione", ha detto Szegedy.
Naturalmente, non è ancora chiaro se questi sforzi adempiranno la profezia di Cohen di oltre 40 anni fa. Gowers ha detto che pensa che i computer saranno in grado di superare i matematici entro il 2099. In un primo momento, predice, i matematici godranno di una sorta di età dell'oro, "quando i matematici fanno tutte le parti divertenti ei computer fanno tutte le parti noiose. Ma penso che durerà molto poco. "
Dopotutto, se le macchine continuano a migliorare e hanno accesso a grandi quantità di dati, dovrebbero diventare molto brave anche a fare le parti divertenti. "Impareranno come eseguire i propri suggerimenti", ha detto Gowers.
Harris non è d'accordo. Non pensa che i provatori di computer siano necessari, o che inevitabilmente "renderanno obsoleti i matematici umani". Se gli informatici saranno mai in grado di programmare una sorta di intuizione sintetica, dice, non potrà comunque competere con quella degli umani. "Anche se i computer capiscono, non capiscono in modo umano."
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/how-close-are-computers-to-automating-mathematical-reasoning-20200827/ in data Thu, 27 Aug 2020 16:15:19 +0000.