Dimostrazioni matematiche al calcolatore

Qualche giorno fa Maxxfi mi ha chiesto cosa ne pensassi delle dimostrazioni matematiche fatte per mezzo del calcolatore. La mia laconica risposta è stata “brutte, ma valide”; provo ad aggiungere qualche considerazione in più.
Innanzitutto, bisogna mettersi d’accordo sui termini: cos’è una dimostrazione matematica al calcolatore? Lascio immediatamente da parte i programmi di intelligenza artificiale che dimostrano semplici teoremi, magari dandone nuove dimostrazioni, oppure se ne escono con nuovi teoremini non pubblicati in precedenza: quelle sono dimostrazioni del computer, e hanno la stessa validità degli esercizi che ci facevano fare nel biennio di matematica (forse un po’ meglio, se il programma è fatto bene e gli sono stati implementati correttamente gli algoritmi.
Esistono poi “dimostrazioni” che non lo sono affatto: prendiamo ad esempio il test di primalità di Miller-Rabin, che permette di verificare molto velocemente se un numero è presumibilmente primo. Un non matematico può pensare che se la probabilità che il numero testato non sia primo sia di 1 su 1010 ci si potrebbe anche accontentare, e in effetti molti programmi di crittografia usano questi probabili primi accettando il rischio che primi non siano e quindi si possa fare un attacco al testo crittografato; ma un matematico non potrà mai dire “quel numero è primo”.
Resta infine il gruppo di dimostrazioni al computer vere e proprie: quella archetipale è per il teorema dei quattro colori, che afferma che bastano quattro colori per colorare una qualunque mappa in modo che nessuna coppia di regioni confinanti (per un tratto, i singoli punti non contano) abbia lo stesso colore; ma ad esempio c’è stata anche quella della congettura di Keplero, che afferma che il miglior impacchettamento di sfere nello spazio tridimensionale è quello che faremmo tutti, facendo tanti strati a esagono uno sopra l’altro. Queste dimostrazioni, che gli anglofoni definiscono “computer assisted”, hanno una struttura comune. Il teorema è stato inizialmente analizzato e azzannato, e si è arrivati a dire che il caso generale si può ricondurre a un numero finito di sottocasi particolari; nel caso del teorema dei quattro colori si parla di 1476 mappe (grossine) distinte, mentre per la congettura di Keplero sono state ritenute necessarie più di 5000 configurazioni di sfere. In questi casi, il calcolatore serve a verificare che nessuna di queste mappe/configurazioni invalidi il teorema: un lavoro che in linea puramente teorica si potrebbe fare a mano, ma richiederebbe non so quante centinaia d’anni, e si rischierebbe di fare degli errori (tenetevi a mente questa frasetta).
L’atteggiamento dei matematici rispetto a queste dimostrazioni al calcolatore è prettamente filosofico. Alcuni non le considerano valide perché affermano che la dimostrazione deve essere comprensibile a un essere umano, e se non ci si può mettere a verificare tutti i casi allora la dimostrazione in verità non esiste. Altri hanno una preclusione più di principio: come ci si può assicurare che l’algoritmo usato sia corretto, e il programma per computer lo implementi correttamente? Altri ancora, credo la maggioranza, non si fanno di questi problemi e prendono il teorema per dimostrato.
La mia visione personale? Come credo abbiate capito, non ho nessun problema ideologico su una dimostrazione assistita dal computer. Per quanto riguarda la correttezza degli algoritmi, si può ovviare alla cosa implementando indipendentemente più programmi su più architetture diverse – in effetti per il teorema dei quattro colori hanno fatto così – e verificando che l’output sia lo stesso. D’altronde, non è che le dimostrazioni umane siano scevre da errori: proprio il teorema dei quattro colori era stato “dimostrato” nel 1879 salvo poi accorgersi nel 1890 che la dimostrazione era errata. Insomma, la correttezza degli algoritmi e la correttezza delle dimostrazioni sono in fin dei conti la stessa cosa. Nel caso poi degli algoritmi probabilistici di cui sopra, c’è persino chi afferma che se la probabilità che l’algoritmo non ci prenda sia inferiore a quella di un errore hardware della macchina allora si ha la certezza, ma è una linea di pensiero che non mi ispira molto, a meno di pensare anche che tutti gli esseri umani possano venire ipnotizzati contemporaneamente ;-)
Detto tutto questo, resta il mio giudizio lapidario iniziale: il teorema è sì dimostrato, ma la dimostrazione è così brutta che un Vero Matematico se ne fa ben poco, come diceva anche Erdős. Non è detto che esista una dimostrazione “bella” di questi teoremi; visto però che questi teoremi non sono fondamentali nel senso di essere alla base di tanta matematica si può anche decidere di non contarla come dimostrazione dal punto di vista estetico. A voi la scelta!

che smemorati!

Capisco che bisogna riempire un po’ di pagine dei quotidiani con notizie sul ventesimo anniversario della caduta del Muro di Berlino. Capisco che non si può fare più di tanto. Ma magari mettere in funzione il cervello potrebbe evitare di scrivere che «nemmeno Jannick e Oly, due Ossis (tedeschi dell’Est) di 22 e 20 anni, ricordano il crollo del muro e l’apertura della Repubblica Democratica Tedesca»… a meno naturalmente che quei geni malefici della ex DDR, oltre a imbottire di steroidi le atlete, avessero anche avviato un piano per l’impianto di ricordi indotti nella mente di neonati e infanti, e la burocrazia l’avesse stolidamente portato avanti ancora per qualche giorno dopo la caduta del Muro.

Carlo Giovanardi

Mi sono imbarcato in un’impresa impossibile: dare un senso alle parole del sottosegretario Carlo Giovanardi (con delega alla droga, il che non significa necessariamente avere un’esperienza sul campo). L’ineffabile afferma: «Poveretto, è morto, e la verità verrà fuori, soprattutto perchè pesava 42 chili». Il meglio che sono riuscito a tirare fuori è qualcosa del genere: “Se fosse stato una persona dal peso normale, il pestaggio che gli hanno fatto non sarebbe stato letale. Purtroppo non abbiamo fondi per fare un corso alle forze dell’ordine in modo che sappiano valutare quando fermarsi nel caso di condizioni fisiche evidentemente non perfette”.
Io non ho nessun problema a dire “Cucchi era un drogato”, e posso anche immaginare che sia stato uno spacciatore. Questo però significa semplicemente che doveva essere arrestato, giudicato, condannato… almeno in uno Stato di diritto, un posto cioè dove si continua a credere che le persone abbiano dei doveri ma anche dei diritti. Evidentemente il sottosegretario Giovanardi è molto più avanti di me e sa dove ci troviamo davvero.
Ma la cosa più triste non è tanto che Giovanardi si professi cattolico – ognuno può essere convinto di una cosa per quanto falsa essa sia – ma che non ho letto di nessun alto prelato che abbia ricordato queste cose, e il dovuto rispetto per la persona che dovrebbe sempre esserci indipendentemente dal giudizio sulle sue azioni.

fertilizzante

Nell’ultimo post di Leonardo (che raccontava da par suo l’affaire Santanchè-Maometto) c’era una frase che mi ha spiazzato del tutto. Eccovela: «La storia della sposa bambina di Maometto su internet è moneta corrente. Ma piazzata su Domenica Cinque la domenica alle tre è puro tritolo – no, fertilizzante.»
Il concetto dietro questa frase è persin banale, ed è stato declinato in mille modi diversi: quello che si vede in rete non è affatto uno specchio della società italiana. Ma scritto così almeno a me è apparso improvvisamente nuovo. Il guaio di avere un linguaggio completamente diverso implica appunto che la stessa affermazione viene assorbita in maniera completamente diversa; e visto che chi non si fa capire ha sempre torto, forse è meglio che io stia un po’ più attento. Non per quello che scrivo qua, ma per quello che dico in giro…
Aggiornamento: (16:45) Vediamo se riesco a spiegarmi.
– Se io scrivo una cosa qua sul mio blog, immagino che chi mi legge sia abbastanza intelligente da capire cosa intendo (salvo casi eclatanti come quello che ho scritto qui sopra, e lasciando perdere chi arriva qua dopo qualche anno con un motore di ricerca).
– Se io dico la stessa cosa per strada, probabilmente la gente capirà tutt’altro.
– Ergo, devo imparare a ricordarmi che il mondo non si esaurisce con i socialcosi, ma è MOLTO più grande.

gioco della domenica: Flood Fill

Conoscete il teorema dei quattro colori? Afferma che una mappa può sempre essere colorata usando quattro soli colori distinti, senza che due regioni dello stesso colore abbiano un tratto di confine in comune (un punto è permesso). Il teorema è stato enunciato nella seconda metà del secolo XIX, ma si dovette aspettare il 1977 per averne una dimostrazione… che richiede una quantità assurda di conti al computer.
Nel caso di Flood Fill non vi si chiede di dimostrare il teorema, ma semplicemente di colorare alcune mappe usando il minor numero di colori possibile. Purtroppo, anche se vengono assegnate delle stelle se si risparmiano colori, non ho visto da nessuna parte un modo per contare le stelle vinte e/o sapere se si poteva fare di meglio. Ad ogni buon conto, buona colorazione!
P.S.: il sito apre una finestra su http://www.paradoxide.com/ – ho dato un’occhiata al sorgente e mi pare setti solo Google Analytics, ma i paranoici potrebbero bloccare il sito e/o evitare di giocare.
(via Passion for Puzzles)

Pandemia mentale

Stamattina sono andato a comprare il giornale: nell’edicola, in mezzo ai settimanali, c’era uno scatolone di confezioni di gel igienizzante, 2 euro e novanta cadauna. Il che è bellissimo, intendiamoci: ma mi chiedo quanto la gente sia convinta che sia meglio avere la possibilità di disinfettarsi in certi momenti, e quanta non sia la psicosi dell’influenza suina (ora ridenominata “A” perché i produttori di salumi e insaccati sono una lobby più forte dei produttori di polli che non sono riusciti a far togliere il loro nome dall’aviaria).
In Italia, ma mi sa anche altrove, siamo arrivati alla schizofrenia pura: ogni giorno viene fatto il bollettino delle morti, affrettandosi però a spiegare come tutti questi poveretti avevano delle altre malattie croniche e il virus A/H1N1 ha solo dato il colpo mortale. Poi spuntano i numeri delle morti per influenza “normale”, e si capisce ancora di meno: alcuni dicono 8000 persone l’anno solo in Italia, altri parlano di 240000 ma nel mondo, sempre comunque molti più di quanti assurgono attualmente agli onori della cronaca.
Però credo che noi italiani deteniamo un record: il modo di sprecare soldi. Non si sa bene perché, ma il governo ha stanziato una barcata di soldi per fare un regalo all’industria farmaceutica e procacciarsi decine di milioni di dosi del vaccino. Che è successo? che quando i media hanno pompato queste prime morti, ci si è improvvisamente accorti che i vaccini non c’erano. Così il viceministro Fazio ha dovuto inventarsi un piano B, e proclamare che è tutto previsto: si lascia scemare il picco, ma non appena ci sarà la seconda ondata, quella più bastarda – avete presente come funziona un rasoio bilama, no? – allora sì che ci saranno vaccini per tutti. Non credo ci sia da aggiungere altro.

Numerologia (libro)

[copertina] Se qualcuno si chiedesse come mai io mi sia messo a leggere un libro sulla numerologia… beh, perché no? Lo trovo sicuramente più interessante di tanti altri libri nella lista dei bestseller. Poi tanto me lo sono trovato in biblioteca, quindi non ho speso una lira. Confesso però che non ho affatto capito se l’autore del libro (Leonard R. N. Ashley, Numerologia [The Complete Book of Numerology], Mondadori – “Oscar Saggi” 2008 [2005], pag. 295, € 11.40, ISBN 978-88-04-58171-0, trad. Valeria Pazzi) creda o no a tutto quello che ha scritto; a me personalmente ha dato una sensazione ambivalente, dal “in fin dei conti è divertente” al “i numeri danno più indizi che l’astrologia, e soprattutto sono più semplici da usare per divinare”. La lettura è un po’ ripetitiva, visto che Ashley parte dal principio che un lettore possa essere interessato a una sezione specifica; a un certo punto scrive persino “se vi state scocciando delle ripetizioni, ritenetevi fortunati di essere più ricettivi dalla media della gente”. Una vera captatio benevolentiae! Però nonostante tutto la lettura l’ho trovata piacevole, soprattutto nelle digressioni che portano Ashley ad esempio a raccontare della cabala ebraica oppure della storia di Cagliostro. Insomma, forse non riuscirete a scoprire come il vostro nome influenzi il vostro destino ma almeno vi sarete acculturati un po’. La traduzione è scorrevole, tranne qualche caduta nel capitolo 16.

Han fatto fuori Pileri

Disposizione generale Telecom Italia n. 366 del 6 novembre 2009:
Con decorrenza immediata:
* la responsabilità della Direzione Technology & Operations viene affidata ad Oscar Cicchetti;
* la responsabilità della Direzione Domestic Market Operations viene affidata a Marco Patuano;
* la responsabilità della funzione Administration, Finance and Control viene affidata ad Andrea Mangoni che mantiene, ad interim, la responsabilità di International Business.
Stefano Pileri è stato insomma fatto fuori senza nemmeno l’onore di un comunicato ad hoc (qualcuno forse si ricorda di quando Sentinelli venne defenestrato da TIM, pur rimanendo “in piena sintonia con il Gruppo”). La cosa è molto preoccupante, vista l’indubbia competenza di Pileri. Stanno arrivando tempi davvero cupi.