{"id":2364,"date":"2010-12-15T02:30:47","date_gmt":"2010-12-15T01:30:47","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2364"},"modified":"2022-10-10T22:25:20","modified_gmt":"2022-10-10T20:25:20","slug":"il-teorema-dei-quattro-colori","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/12\/15\/il-teorema-dei-quattro-colori\/","title":{"rendered":"Il teorema dei quattro colori"},"content":{"rendered":"

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\u00e9 non verificabile da nessuno e a cui bisogna credere per fede. Ma dietro tutto questo c’\u00e8 una storia molto interessante.<\/p>\n

La versione in lingua italiana di Wikipedia ha un racconto ben dettagliato<\/a> 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\u00f2 era sempre vero. Arthur Cayley fu il primo a scrivere una pubblicazione sull’argomento; la dimostrazione rest\u00f2 elusiva per un quarto di secolo, fino a che nel 1879 Alfred Kempe lo “dimostr\u00f2”, seguito l’anno successivo da Peter Tait che propose un altro approccio. Tutto rest\u00f2 tranquillo per oltre un decennio; nel 1890 per\u00f2 Percy Heawood scopr\u00ec un errore fatale nella dimostrazione di Kempe, e l’anno successivo anche la dimostrazione di Tait fu trovata errata. L’unico risultato che si \u00e8 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.<\/p>\n

Prima di proseguire, per\u00f2, \u00e8 meglio fare alcune specificaziori sull’enunciato del problema.
\n

\"un<\/a>
un controesempio al teorema dei quattro colori<\/figcaption><\/figure><\/p>\n
    \n
  1. Quando si parla di regioni confinanti<\/i>, il confine deve essere un tratto di territorio, e non uno o pi\u00f9 punti separati. In caso contrario, basterebbe prendere un cerchio e dividerlo in spicchi; tutti gli spicchi “confinerebbero” tra di loro.<\/li>\n
  2. Quando si parla di regioni<\/i>, queste devono essere “di un pezzo solo”. Attenzione: non basta che siano connesse nel senso matematico del termine, perch\u00e9 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.<\/li>\n
  3. Il teorema non \u00e8 la stessa cosa che dire “non \u00e8 possibile disegnare nel piano cinque regioni in modo che ciascuna tocchi le altre quattro”. Quest’ultimo teorema \u00e8 effettivamente vero, ma per quanto ne sappiamo pu\u00f2 darsi che iniziando a colorare una mappa molto complessa ci sia una serie di vincoli che porti alla necessit\u00e0 di usare un quinto colore in qualunque modo si proceda.<\/li>\n<\/ol>\n

    Nei decenni successivi si fecero alcuni passi avanti nella soluzione del problema. Si dimostr\u00f2 che alcune configurazioni delle mappe potevano essere sostituite da configurazioni “pi\u00f9 semplici”, nel senso che se si riusciva a dimostrare la colorabilit\u00e0 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\u00f2, due matematici dell’Universit\u00e0 dell’Illinois – Kenneth Appel e Wolfgang Haken – scrissero un algoritmo informatico che dimostrava (costruttivamente) l’equivalenza di intere classi di configurazioni, riducendo cos\u00ec 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.<\/p>\n

    Da questa rapida carrellata vediamo una cosa: il teorema non \u00e8 stato affatto dimostrato dal calcolatore<\/i>, n\u00e9 pi\u00f9 n\u00e9 meno che quando usiamo una calcolatrice per fare delle operazioni aritmetiche queste non sono fatte dalla calcolatrice ma da noi. Il computer \u00e8 semplicemente stato uno strumento per fare tutta una serie di conti e operazioni che sarebbero stati impossibili perch\u00e9 troppo lunghi per un essere umano. Da questo punto di vista possiamo ancora stare tranquilli: non solo i computer non hanno la creativit\u00e0 per capire se un risultato \u00e8 interessante o no, ma neppure quella per trovare una linea di dimostrazione. \u00c8 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\u00f2 infici la validit\u00e0 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\u00e9 una dimostrazione non viene osservata pu\u00f2 essere contemporaneamente vera e falsa. Altra cosa naturalmente \u00e8 l’affermare che quella attualmente esistente sia una bella<\/b> soluzione; il senso estetico di un qualunque matematico lo fa rabbrividire, ma il suo senso pratico – s\u00ec, anche un matematico pu\u00f2 avere del senso pratico – lo riporta subito con i piedi per terra e gli fa pensare “per il momento, teniamoci stretta questa soluzione.”<\/p>\n

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

    Un’ultima curiosit\u00e0: 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\u00f6bius ne richiede sei. La cosa strana \u00e8 che la dimostrazione in entrambi i casi \u00e8 molto pi\u00f9 semplice: chiss\u00e0 come mai il piano \u00e8 cos\u00ec complicato!<\/p>\n","protected":false},"excerpt":{"rendered":"

    Per colorare una mappa senze che due regioni adiacenti abbiano lo stesso colore, ne bastano quattro. C’\u00e8 voluto pi\u00f9 di un secolo per dimostrarlo, e alla fine \u00e8 stato necessario usare il computer. Ma allora \u00e8 una dimostrazione vera oppure no?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2364","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-C8","jetpack-related-posts":[{"id":2604,"url":"https:\/\/xmau.com\/ilpost\/2013\/05\/06\/e-morto-kenneth-appel-pillole\/","url_meta":{"origin":2364,"position":0},"title":"\u00c8 morto Kenneth Appel [Pillole]","author":".mau.","date":"06\/05\/2013","format":false,"excerpt":"Il nome forse non vi dice molto, e non penso sia un caso che sia morto il 19 aprile ma non ne avevo sentito parlare fino a stamattina: ma Appel (qui il suo ricordo sull'Economist), insieme a Wolfgang Haken, nel 1976 fecero una rivoluzione nella filosofia matematica, dimostrando il teorema\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":398,"url":"https:\/\/xmau.com\/ilpost\/2010\/07\/27\/il-teorema-di-pitagora\/","url_meta":{"origin":2364,"position":1},"title":"Il teorema di Pitagora","author":".mau.","date":"27\/07\/2010","format":false,"excerpt":"Il teorema pi\u00f9 famoso della geometria merita indubbiamente una trattazione a s\u00e9.","rel":"","context":"In \"geometria\"","block_context":{"text":"geometria","link":"https:\/\/xmau.com\/ilpost\/tag\/geometria\/"},"img":{"alt_text":"[la costruzione euclidea del teorema di Pitagora]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2014\/09\/pitagora-euclide.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":2364,"position":2},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2614,"url":"https:\/\/xmau.com\/ilpost\/2013\/06\/03\/matematica-per-analogie\/","url_meta":{"origin":2364,"position":3},"title":"Matematica per analogie","author":".mau.","date":"03\/06\/2013","format":false,"excerpt":"Non \u00e8 che i matematici predichino bene e razzolino male: il punto \u00e8 che loro sono inconsciamente abituati a distinguere la scoperta di una propriet\u00e0 dalla sua dimostrazione, ma si dimenticano di mostrare il momento della scoperta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1441,"url":"https:\/\/xmau.com\/ilpost\/2019\/03\/07\/la-dimostrazione-matematica-piu-lunga\/","url_meta":{"origin":2364,"position":4},"title":"La dimostrazione matematica pi\u00f9 lunga","author":".mau.","date":"07\/03\/2019","format":false,"excerpt":"\u00c8 impossibile che qualche essere umano la possa leggere.","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"un esagono colorato di rosso e blu","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/03\/esagono-300x248.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2580,"url":"https:\/\/xmau.com\/ilpost\/2013\/03\/27\/ricondursi-al-caso-precedente\/","url_meta":{"origin":2364,"position":5},"title":"Ricondursi al caso precedente","author":".mau.","date":"27\/03\/2013","format":false,"excerpt":"Quella del titolo \u00e8 una frase tipica da matematico e fa spesso divertire chi matematico non \u00e8, per\u00f2 \u00e8 uno strumento molto potente quando lo si sa usare.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2364","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2364"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2364\/revisions"}],"predecessor-version":[{"id":2365,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2364\/revisions\/2365"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}