backup del Post

Il teorema dei quattro colori

Il teorema dei quattro colori ha avuto una triste nomea; essere stato il primo risultato matematico dimostrato non da un essere umano ma da un computer. Peggio ancora, non esiste a tutt’oggi una dimostrazione verificata da una persona in carne e ossa, tanto che quando negli anni ’70 del secolo scorso il risultato fu reso pubblico ci furono alcuni che commentarono che quella fornita non era affatto una dimostrazione proprio perché non verificabile da nessuno e a cui bisogna credere per fede. Ma dietro tutto questo c’è una storia molto interessante.

La versione in lingua italiana di Wikipedia ha un racconto ben dettagliato della nascita e crescita di quella che ai tempi era solo la congettura dei quattro colori. Essa venne enunciata per la prima volta nel 1852 da uno studente del matematico inglese Augustus De Morgan, tale Francis Guthrie, che si era accorto che bastavano quattro colori per colorare una mappa delle contee britanniche, e chiese al suo professore se ciò era sempre vero. Arthur Cayley fu il primo a scrivere una pubblicazione sull’argomento; la dimostrazione restò elusiva per un quarto di secolo, fino a che nel 1879 Alfred Kempe lo “dimostrò”, seguito l’anno successivo da Peter Tait che propose un altro approccio. Tutto restò tranquillo per oltre un decennio; nel 1890 però Percy Heawood scoprì un errore fatale nella dimostrazione di Kempe, e l’anno successivo anche la dimostrazione di Tait fu trovata errata. L’unico risultato che si è saputo per quasi un secolo, anch’esso a opera di Heawood, era che con cinque colori si era certi di poter colorare una qualsiasi mappa.

Prima di proseguire, però, è meglio fare alcune specificaziori sull’enunciato del problema.

1. Quando si parla di regioni confinanti, il confine deve essere un tratto di territorio, e non uno o più punti separati. In caso contrario, basterebbe prendere un cerchio e dividerlo in spicchi; tutti gli spicchi “confinerebbero” tra di loro.
2. Quando si parla di regioni, queste devono essere “di un pezzo solo”. Attenzione: non basta che siano connesse nel senso matematico del termine, perché in quel caso potrebbero esserci delle zone connesse attraverso un singolo punto e, come si vede nella figura a destra, sarebbe facile trovare un controesempio. Se si considerano le regioni con lo stesso colore come un’unica regione, lo gnomone bianco richiede necessariamente un quinto colore.
3. Il teorema non è la stessa cosa che dire “non è possibile disegnare nel piano cinque regioni in modo che ciascuna tocchi le altre quattro”. Quest’ultimo teorema è effettivamente vero, ma per quanto ne sappiamo può darsi che iniziando a colorare una mappa molto complessa ci sia una serie di vincoli che porti alla necessità di usare un quinto colore in qualunque modo si proceda.

Nei decenni successivi si fecero alcuni passi avanti nella soluzione del problema. Si dimostrò che alcune configurazioni delle mappe potevano essere sostituite da configurazioni “più semplici”, nel senso che se si riusciva a dimostrare la colorabilità della seconda si poteva ricavare una colorazione con quattro soli colori anche della prima; e si riusci a trovare un insieme di configurazioni di base, tali che se ciascuna di esse poteva essere colorata con solo quattro colori allora il teorema sarebbe stato risolto. Il guaio era che tale insieme era infinito, e quindi non si poteva certo provarle tutte. Nel 1977, però, due matematici dell’Università dell’Illinois – Kenneth Appel e Wolfgang Haken – scrissero un algoritmo informatico che dimostrava (costruttivamente) l’equivalenza di intere classi di configurazioni, riducendo così a poco meno di duemila quelle di base, e arrivarono con il loro listato e i pacchi di tabulati a rivendicare la dimostrazione del teorema. Gli editori che ricevettero il manoscritto scrissero un altro algoritmo indipendente per verificare il risultato, osservarono la coincidenza delle risposte, pubblicarono l’articolo e fecero nascere l’era del d.c.: dopo il computer.

Da questa rapida carrellata vediamo una cosa: il teorema non è stato affatto dimostrato dal calcolatore, né più né meno che quando usiamo una calcolatrice per fare delle operazioni aritmetiche queste non sono fatte dalla calcolatrice ma da noi. Il computer è semplicemente stato uno strumento per fare tutta una serie di conti e operazioni che sarebbero stati impossibili perché troppo lunghi per un essere umano. Da questo punto di vista possiamo ancora stare tranquilli: non solo i computer non hanno la creatività per capire se un risultato è interessante o no, ma neppure quella per trovare una linea di dimostrazione. È poi vero che a tutt’oggi non esiste una dimostrazione del teorema che possa essere seguita passo passo da un essere umano; ma non mi pare che ciò infici la validità del teorema stesso, a meno che voi non siate dei filosofi zen e affermiate che un albero che cade in una foresta senza nessuno che lo osservi non fa alcun rumore oppure siate dei fisici quantistici duri e puri e riteniate che finché una dimostrazione non viene osservata può essere contemporaneamente vera e falsa. Altra cosa naturalmente è l’affermare che quella attualmente esistente sia una bella soluzione; il senso estetico di un qualunque matematico lo fa rabbrividire, ma il suo senso pratico – sì, anche un matematico può avere del senso pratico – lo riporta subito con i piedi per terra e gli fa pensare “per il momento, teniamoci stretta questa soluzione.”

Il secondo insegnamento che ci viene da questa storia è che non è nemmeno detto che una dimostrazione “umana” sia priva di errori, come visto più sopra. Fare una dimostrazione formalmente corretta a partire da un sistema di assiomi è possibile, come dimostrarono Russell e Whitehead, ma è una palla tale che nessuno lo fa in pratica, tralasciando passaggi che sembrano a tutti ovvi… almeno fintantoché qualcuno ci pensa su un po’ di più e si accorge che non sono poi così ovvi. Quindi perché lamentarsi di una dimostrazione automatizzata, tanto più che nel 2005 Georges Gonthier ha dimostrato che la dimostrazione è sintatticamente corretta? La possibilità di errori c’è anche in quel caso, ma non è che la situazione sia peggiore. Come ultima cosa, chi effettivamente disegna le mappe non si è mai preoccupato della cosa; non è che usare un quinto colore avrebbe fatto cascare il mondo.

Un’ultima curiosità: i matematici hanno trovato una formula corrispondente per altri tipi di superfici: il toro (la ciambella) richiede almeno sette colori mentre il nastro di Möbius ne richiede sei. La cosa strana è che la dimostrazione in entrambi i casi è molto più semplice: chissà come mai il piano è così complicato!