venerdì 20 gennaio 2017

I sistemi di Lindenmayer (parte prima: la successione di Thue-Morse)

Aristid Lindenmayer
Per definire una sequenza numerica molto spesso si specificano i primi elementi della sequenza e si fornisce una regola per generare gli infiniti elementi successivi. Per esempio, la celeberrima successione di Fibonacci si costruisce partendo dagli elementi 0 e 1, e rispettando la regola secondo la quale ogni termine successivo è la somma dei due che lo precedono.
Ora, proviamo a costruire una sequenza diversa, formata esclusivamente da zeri e uni. Il suo primo elemento è uno zero. La regola da rispettare è la seguente: ogni elemento genera il suo successore attraverso le sostituzioni 0 01 e 1 10. Il secondo termine della sequenza è quindi 01. Il terzo è 0110. Il quarto 01101001. E così via.

Il sistema di costruzione della sequenza rientra nella famiglia dei cosiddetti "L-systems", o sistemi di Lindenmayer. Questa famiglia di sistemi, a sua volta, fa parte del più ampio mondo dei "sistemi di riscrittura", nei quali, genericamente, vengono fissate alcune regole di sostituzione che possono essere applicate agli oggetti di un insieme.
Un sistema di riscrittura è un sistema di Lindenmayer se esistono:
1. una famiglia di simboli ammessi;
2. un elemento iniziale formato da una concatenazione di simboli ammess;
3. un insieme di regole di sostituzione per la generazione degli elementi successivi.

Disegni di piante generati mediante sistemi di Lindenmayer
Non deve stupire che questi sistemi prendano il loro nome non da un matematico o da un informatico, ma da un biologo. L'ungherese Aristid Lindenmayer, infatti, vissuto tra il 1925 e il 1989, ideò questo giochino di riscrittura per descrivere formalmente il comportamento delle cellule vegetali e la crescita di alcuni semplici organismi multicellulari, ad esempio particolari tipi di alghe. Successivamente i sistemi di Lindenmayer vennero applicati con successo anche a specie vegetali più complesse. Sono stati impiegati anche per generare frattali, mediante un processo di autosimilarità (un frattale costituito da più copie di se stesso, come il celebre triangolo di Sierpinski).


Torniamo all'esempio iniziale. In questo caso, i simboli ammessi sono 0 e 1, l'elemento iniziale è 0, e le regole di sostituzione sono quelle citate sopra: 0 01 e 1 10.
Diamo ancora un'occhiata ai primi termini della sequenza: 0, 01, 0110, 01101001, ... Balza all'occhio una prima proprietà: ogni elemento della successione è formato da un numero di cifre doppio rispetto al suo predecessore.
Un'altra caratteristica è la seguente: ogni elemento è costituito dal suo predecessore concatenato con il suo complemento. Detto altrimenti, ogni termine include il precedente come sua prima metà. Per esempio, abbiamo visto che il terzo termine è 0110. Per costruire il suo complemento basta invertire ogni cifra binaria, cioè trasformare gli zeri in uni e viceversa. Otteniamo quindi 1001. Il nostro quarto elemento è 0110 concatenato a 1001, cioè 01101001.

Ecco, abbiamo trovato un modo alternativo per definire in modo costruttivo la nostra sequenza, che viene illustrato nella figura a fianco.

In virtù della seconda proprietà del sistema, potremmo considerare un'altra sequenza: anziché la successione delle stringhe binarie che raddoppiano di lunghezza ad ogni passo, potremmo considerare un'unica stringa, quella di lunghezza infinita alla quale converge la sequenza che abbiamo preso in esame in precedenza: anche questa stringa può essere studiata come una successione, perché è formata da cifre binarie che ne costituiscono gli elementi.
I primi 16 termini della successione sono quindi: 0110100110010110.

Una volta formalizzata la successione in questo modo, saltano fuori alcune proprietà davvero sorprendenti. Ma andiamo in ordine.
Per cominciare, la successione viene chiamata di Thue-Morse, dai nomi dei due matematici che l'hanno studiata: il danese Axel Thue e l'americano Marston Morse.

Vediamo una prima proprietà: l'n-esimo termine della successione è uguale a:
  • 0, se il numero n-1 espresso in forma binaria contiene un numero pari di uni;
  • 1, se il numero n-1 espresso in forma binaria contiene un numero dispari di uni.

Attenzione: l'elemento che compare per primo nella sequenza è in realtà associato all'indice 0, non all'1. In binario, 0 si scrive ancora 0, che non contiene uni al suo interno. Zero può essere considerato un numero pari, quindi il primo elemento è 0. Vediamo ora, ad esempio, l'elemento associato a n=5: in binario 5 si scrive 101, che contiene due uni. Due è pari, quindi il sesto elemento è 0. Il nono elemento: 8 in binario è 1000, in cui compare un solo uno. Essendo uno dispari, il nono elemento è un 1. E così via.
 Quel genio matematico che risponde al nome di John Conway e di cui ho parlato più volte (ad esempio qui), ha avuto un'ideona: ha chiamato "odiosi" i numeri interi n tali per cui l'n-esimo termine della sequenza di Thue-Morse è 1, e "malvagi" quelli per cui l'n-esimo termine è 0. Perché tutto questo odio e questa malvagità"? Soltanto un gioco di parole: in inglese "pari" si dice "even", che suona simile a "evil" ("malvagio"), e "dispari" si dice "odd", che assomiglia a "odious" ("odioso").

Un'altra curiosa proprietà è la seguente: fissato a 0 il termine associato a n=0, il termine associato a 2n (con n naturale qualsiasi) è uguale a quello associato a n, e il termine associato a 2n+1 è uguale al "complemento" del termine associato a n ("complemento" nel senso che 1 è il complemento di 0 e viceversa). Provare per credere.

Non è nemmeno difficile convincersi del fatto che, preso un qualsiasi n naturale, la porzione di successione formata dai primi 2n termini è palindroma, cioè si legge allo stesso modo da sinistra a destra e da destra a sinistra.

Ma il bello deve ancora venire. Intanto beccatevi le proprietà qui a fianco. Che la successione di Thue-Morse sia legata a quantità come la radice quadrata di 2 può sembra abbastanza normale, ma che anche qui venga fuori pi greco, beh, è già molto più stupefacente.
Ricordate il linguaggio Logo, quello che poteva essere usato, tra le altre cose, per guidare una tartaruga su un piano cartesiano?
Ebbene, immaginiamo che i termini successivi della sequenza di Thue-Morse rappresentino ordini impartiti alla tartaruga. Più precisamente, un 1 deve essere interpretato come "vai avanti di una posizione", e uno 0 come "girati in senso antiorario di 60°".
Secondo voi che disegno traccerà la tartaruga seguendo le cifre binarie della nostra sequenza? Proviamo a vedere.

 Non si capisce molto, vero? Già, perché servono molti termini della sequenza, cioè molte istruzioni per  il simpatico rettile, perché il risultato cominci a prendere forma. Vediamo cosa succede dopo 28 = 256, 210 = 1024, 212 = 4096 e 214 = 16384 istruzioni.



Vi ricorda qualcosa? Se scegliamo, per la cifra 1, una rotazione antioraria di 120° anziché 60°, si ottiene un disegno ancora più pulito:


Ebbene sì: è il fiocco di neve di Koch, uno dei frattali più famosi. Modificando ancora le regole della tartaruga, ma utilizzando sempre la successione di Thue-Morse, si ottengono risultati interessanti, come questi:


Per questi e altri divertimenti vi rimando al blog Three-Cornered Things di Zachary Abel.

Max Euwe
Una proprietà interessante della successione di Thue-Morse è l'assenza in essa di stringhe della forma XXX, dove X è una qualsiasi sequenza di cifre binarie. Un grande campione di scacchi come Machgielis "Max" Euwe (1901 – 1981), che oltre ad essere stato il quinto campione del mondo di scacchi tra il 1935 e il 1937, fu anche una brillante mente matematica, contestò una delle regole "tedesche" che vigevano nel gioco degli scacchi intorno al 1929: una partita poteva essere dichiarata patta se la stessa sequenza di mosse viene ripetuta per tre volte di seguito.
Sfruttando la successione di Thue-Morse, Euwe dimostrò che la regola non escludeva di per sè partite di lunghezza infinita.
Grazie a questa scoperta, venne accettata universalmente la regola in base alla quale una partita può essere dichiarata patta se una posizione si presenta per tre volte, indipendentemente da quali mosse l'abbiano determinata.

E qui mi fermo. La sequenza di Thue-Morse ha anche affascinanti connessioni con il gioco del Nim, con la risoluzione di problemi di distribuzione di risorse tra due contendenti, con la teoria dei numeri, con la combinatoria delle parole, e con un sacco di altre cose. Buon divertimento.

sabato 31 dicembre 2016

Buon 2017!

Con il post precedente questo blog ha festeggiato i suoi primi 250 post pubblicati.
Era il primo gennaio del 2011 quando iniziai, praticamente per gioco, a scrivere cose su queste pagine. Sono passati sei anni, e di acqua sotto i ponti ne è passata molta. 2011, cioè il primo anno di Mr. Palomar, era un numero primo, cioè divisibile soltanto per se stesso e per 1.
Dopo sei anni si ripropone questo fatto, perché anche 2017 è un numero primo.
Per la precisione, si tratta di un numero primo di Friedlander-Iwaniec, cioè della forma
Non ci credete? Prendete a = 44 e b = 3. Il precedente numero primo con questa proprietà è 1777 (a = 39, b = 4), che è l'anno della nascita di Gauss.
2017 fa anche parte di una terna pitagorica, essendo l'ipotenusa di un triangolo rettangolo i cui cateti sono 792 e 1855.
Sicuramente ci saranno altre proprietà del 2017, ma mi fermo qui, non prima di aver augurato un felice nuovo anno a tutti gli amici di Mr. Palomar.
Buon 2017 a tutti!





venerdì 30 dicembre 2016

Gli enigmi di Coelum: La Coppa dei Mondi


La nuova puntata degli enigmi di Coelum verte su un tema che ho già trattato non soltanto nel mio libro "La matematica nel pallone", ma anche in un trittico di post pubblicato agli albori di questo blog. Ecco i link a quei tre antichi articoli:
Parte 1
Parte 2
Parte 3

Ogni anno, intorno al mese di luglio, viene stabilito il calendario del campionato di calcio di Serie A.
Forse molti di voi si saranno a volte chiesti come si svolge tale procedura. Si tratta di una normale estrazione, come quando vengono sorteggiati i numeri del lotto, o di un complicato calcolo effettuato da un supercomputer? Sicuramente definirlo sorteggio sarebbe riduttivo e semplicistico. Come spiegato nell’articolo di giugno, stabilire il calendario di un girone all’italiana, cioè di un torneo in cui ogni squadra disputa un incontro con ciascuna delle altre partecipanti, non è un’operazione banale, a meno che il numero delle formazioni non sia molto esiguo.
Johann Berger, maestro di scacchi austriaco vissuto tra il 1845 e il 1933, inventò l’algoritmo più famoso tra quelli proposti per risolvere il problema. Nel mio articolo pubblicato sulla rivista Coelum, si immaginava di dover stilare il calendario della Coppa dei Mondi 2514, le cui otto partecipanti sono Terra, Luna, Marte, Cerere, Ganimede, Europa, Callisto e Titano. La prima giornata è determinata semplicemente formando i quattro accoppiamenti che derivano dall’ordine in cui abbiamo elencato le squadre:

E la seconda giornata? Immaginiamo di mantenere la Terra fissa al suo posto in alto a sinistra, e facciamo ruotare in senso orario le altre squadre. Marte si ritroverà nella prima riga, a fianco della Terra. La Luna scenderà nella seconda riga, Cerere nella terza, ed Europa nella quarta. Titano passerà nella prima colonna, restando comunque nella quarta riga. Callisto salirà nella terza riga, spingendo Ganimede nella seconda. Il risultato sarà il seguente:



Proseguendo in questo modo si compileranno tutte le altre giornate del torneo, con la certezza che, alla fine, ogni squadra incontrerà ciascuna delle altre esattamente una volta.
Ma quante saranno le giornate? Se ogni squadra deve incontrare sette avversarie, è evidente che la Coppa si articolerà in sette giornate, in ognuna delle quali saranno disputate quattro partite. Il numero totale degli incontri sarà quindi 7 × 4 = 28. In generale, se le squadre che partecipano a un girone all’italiana sono N (con N pari), le giornate saranno N-1, e, dato che ogni giornata comprenderà N/2 partite, saranno giocati in tutto N(N-1)/2 incontri. Tutto questo considerando il solo turno di andata: se è previsto anche il girone di ritorno le giornate saranno 2(N-1) e le partite N(N-1).
Nella Serie A del nostro campionato di calcio, che comprende N=20 squadre, vengono disputate 2(N-1) = 38 giornate, per un totale di N(N-1) = 380 partite.
E se le squadre fossero in numero dispari? In questo caso, a turno ognuna delle formazioni dovrebbe riposare, e il numero delle giornate uguaglierebbe così il numero delle partecipanti. In termini più formali, se le squadre sono N (con N dispari), le giornate saranno N. Visto che a ogni giornata si giocherebbero (N-1)/2 incontri, le partite complessive, prescindendo dal girone di ritorno, saranno N(N-1)/2: esattamente lo stesso risultato che avevamo ottenuto nel caso di N pari. Per esempio, 19 squadre darebbero vita a un torneo di N = 19 giornate, per un totale di N(N-1)/2 = 171 gare. Abbiamo così risposto al primo quesito proposto nel numero di giugno (peraltro abbastanza banale rispetto al secondo).

Il metodo di Berger è l’unico possibile per risolvere il problema del campionato? No di certo. Esistono molti altri algoritmi adatti allo scopo. Sinceramente non so se nel sorteggio dei calendari dei campionati di calcio venga utilizzata una variante dell’algoritmo di Berger o un approccio computazionale completamente diverso. Sicuramente il metodo “puro” di Berger non è utilizzabile in queste occasioni, perché nella determinazione delle giornate devono essere considerati molti vincoli supplementari. Per esempio si fa in modo che le partite tra le squadre più forti non vengano programmate nelle giornate iniziali del campionato, si evita che in una medesima giornata debbano giocare in casa squadre della stessa città, come Verona o Chievo, e così via.
È quindi ipotizzabile che il computer adibito alla determinazione dei calendari sia programmato con un algoritmo simile a quello proposto da Berger, ma modificato e perfezionato in modo da tener conto di una serie di constraint aggiuntivi. Il problema del calendario del campionato mi ha affascinato fin da quando ero ragazzino. Quando avevo una dozzina d’anni, mi cimentavo, con un amichetto compagno di innumerevoli partite a pallone nei cortili di casa, nella compilazione dei calendari dei nostri campionati immaginari. Ma gli algoritmi che adoperavamo erano molto rozzi e poco efficaci. Erano basati su un faticoso approccio per tentativi: si tentava di programmare giornata per giornata, e se a un certo punto incontravamo un ostacolo insormontabile (cioè scoprivamo che le ultime due squadre non ancora abbinate in una giornata si erano già incontrate in una giornata precedente), eravamo costretti a ricominciare tutto da capo.
Diversi anni dopo, non conoscendo ancora il metodo di Berger, escogitai un metodo molto più elegante per risolvere il problema in modo diretto. Supponiamo di avere N squadre. Costruiamo una tabella con N righe e N colonne: ogni riga e ogni colonna corrisponde a una delle squadre. Il nostro obiettivo è riempire ogni casella interna con un numero, che rappresenta la giornata in cui le due squadre in questione si incontreranno tra di loro. Naturalmente, dobbiamo escludere le caselle della diagonale principale, corrispondenti alle improbabili partite in cui una squadra gioca contro se stessa. Per semplicità, possiamo anche trascurare metà tabella, per esempio quella sotto la diagonale principale, perché le caselle di questa zona rappresentano le stesse partite descritte nell’altra metà: potrebbero essere utilizzate per il girone di ritorno, ma una volta che è programmato il turno di andata, basta ripetere la sequenza delle partite, a campi invertiti, e anche il ritorno è determinato.
Considerando le N=8 partecipanti alla Coppa dei Mondi, la tabella di partenza sarebbe la seguente:


In generale, condizione necessaria e sufficiente affinché la compilazione di una simile tabella rappresenti un calendario valido per un campionato è che su ogni riga e su ogni colonna siano presenti tutti i numeri da 1 a N-1, senza ripetizioni. Infatti, la ripetizione di un numero su una medesima riga o colonna starebbe a indicare che una squadra deve giocare due partite nella stessa giornata, e che, corrispondentemente, un’altra squadra non giocherebbe alcuna partita. Situazione questa ovviamente non accettabile.
Forse il vincolo della non ripetizione dei numeri su righe e colonne vi avrà fatto venire in mente il sudoku: in effetti una parentela c’è, ed esistono interessanti connessioni anche con altri concetti matematici come i quadrati latini e i problemi di colorazione dei grafi. Per i lettori interessati ai dettagli, rimando agli articoli del mio blog citati nella bibliografia.
Vediamo come si articola l’algoritmo. Si parte con la matrice compilata con degli zeri.


A questo punto ha inizio il ciclo principale. Si considera, una dopo l’altra, le squadre partecipanti, e per ciascuna vengono individuate la riga e la colonna corrispondenti. Immaginiamo di scendere dall’alto verso il basso lungo la colonna, “rimbalzare” sulla diagonale principale, e percorrere la riga verso destra. Lungo questo cammino, ogni volta che troviamo una casella ancora a zero, la riempiamo con un numero. Quale numero? Per ogni cammino, cercheremo la prima casella che possiamo riempire, e tenteremo di riempirla con il numero successivo a quello presente nella casella immediatamente precedente. Se si tratta della prima casella del cammino, tenteremo di piazzare un 1. Ad ogni nuovo tentativo di riempimento, cresceremo di 1.
Ogni volta che tentiamo di collocare un numero, comunque, controlleremo se il numero candidato non sia stato precedentemente collocato su un’altra casella dello stesso cammino, o della stessa riga, o della stessa colonna: in questo caso ritenteremo il riempimento con il numero aumentato di 1. Se, a un certo punto, a cammino non ancora completato, scopriremo di essere già arrivati a N-1 (nel nostro esempio 7), il successivo incremento ci farà ripartire da 1.
Percorrendo in questo modo il cammino relativo alla Terra, si ottiene:


Dopo aver “sistemato” anche la Luna, ci ritroveremo con questa tabella:


Alla fine dell’intero ciclo di “cammini”, la tabella si riempirà in questo modo:


A questo punto è facile “leggere” il calendario ottenuto. Per esempio, la prima giornata sarà composta dalle partite corrispondenti alle caselle riempite con un 1: Terra-Luna, Marte-Callisto, Europa-Cerere e Titano-Ganimede. Come potete vedere, il risultato è diverso, già nella prima giornata, da quello prodotto dall’algoritmo di Berger. Questo non deve sorprendere, anzi. Con un numero di squadre appena un po’ grande, come 8, sarebbe infatti molto strano che due diversi approcci generassero calendari identici.

Il problema da me proposto sulle pagine di Coelum consisteva nel pianificare il girone all’italiana della Coppa dei Mondi 2514 con le otto squadre già menzionate (Terra, Luna, Marte, Cerere, Ganimede, Europa, Callisto e Titano), facendo però in modo di rispettare lo strano vincolo imposto dagli immaginari organizzatori: a ogni giornata due partite sono in programma al pomeriggio e due alla sera, e prese due squadre qualsiasi tra le partecipanti, esse giocheranno alla stessa ora soltanto tre volte (compresa la giornata in cui si troveranno a gareggiare l’una contro l’altra), mentre nelle altre occasioni scenderanno in campo in fasce orarie diverse.

La figura sotto illustra una soluzione del problema. Se prendiamo, per esempio, Terra e Luna, è facile notare che queste due squadre giocheranno alla stessa ora alla prima giornata (quando giocheranno l’una contro l’altra), alla seconda (quando entrambe scenderanno in campo di pomeriggio), e alla terza (quando giocheranno entrambe in notturna), mentre in tutte le altre giornate si troveranno a disputare i loro incontri in orari differenti.

martedì 20 dicembre 2016

I Premi Turing: Michael Rabin e Dana Scott


Michael Rabin
La serie dedicata agli informatici che hanno vinto il Premio Turing prosegue con una lentezza geologica: perdonatemi. Ma, come sa bene chi li studia, i fenomeni geologici procedono con inesorabile costanza: si va adagio, ma non ci si ferma.
Nel 1959, Michael Rabin e Dana Scott scrissero un articolo intitolato “Finite Automata and Their Decision Problem”, con il quale nasceva un nuovo settore dell’informatica teorica: lo studio degli automi non deterministici.
Un automa non deterministico è una variante, o meglio una generalizzazione, del classico concetto di automa a stati finiti (deterministico). Un automa a stati finiti (deterministico) è un’astrazione con la quale è possibile descrivere il comportamento di molti sistemi reali. Più nello specifico, esso è costituito da:
- un insieme finito I dei possibili input (o ingressi) del sistema;
- un insieme finito O dei possibili output (o uscite) del sistema;
- un insieme finito S dei possibili stati del sistema;
- una "funzione di transizione" f, che stabilisce univocamente quale dei possibili stati del sistema sarà il prossimo, noti lo stato attuale e l'input attuale;
- una "funzione degli output" g, che stabilisce qual è l'output del sistema, noti lo stato attuale e l'input attuale.

Visto che siamo in periodo di feste di fine anno, consideriamo un kit di luci per un albero di Natale: immaginiamo che vi sia un interruttore che, premuto una prima volta, accende le luci in una modalità fissa, e, premuto una seconda volta, attivi la modalità intermittente. Se premiamo l’interruttore una terza volta, le luci si spengono, e il ciclo può essere riavviato.
Il sistema preso ad esempio è molto semplice: ha un solo input possibile (la pressione dell'interruttore), due output (le luci fisse e le luci intermittenti) e tre stati, che possiamo denominare rispettivamente “S” (spento), “F” (fisso), “I” (intermittente). L’automa a stati finiti (deterministico) che descrive il nostro luccicante sistema può essere quindi disegnato come segue:


Nel grafo sono rappresentate, in modo abbastanza autoesplicativo, le funzioni di transizione e delle uscite.

Ora vi chiedo un ulteriore sforzo di immaginazione (coraggio, abbiamo quasi finito, poi resta la parte più semplice e biografica del post): supponiamo che la funzione di transizione, anziché "produrre" come valore uno dei possibili stati del sistema, "produca" una collezione di stati futuri, cioè un sottoinsieme di S. Il risultato sarà un automa a stati finiti non deterministico.
Calma, ragazzi: com'è possibile che la funzione di transizione determini più stati futuri, anziché uno solo? Proprio così: il sistema si può trovare, nello stesso istante, in diversi stati contemporanei, un po' come il gatto di Schrödinger che è vivo e morto nello stesso tempo. Questa è la differenza, o meglio la generalizzazione, rispetto al caso tradizionale deterministico.
Dana Scott
Naturalmente la versione non deterministica è più astratta e meno intuitiva da digerire rispetto alla sua omologa deterministica. Tuttavia, credetemi, questo modello matematico si presta a modellare molte situazioni reali per le quali la versione deterministica sarebbe troppo poco espressiva.

I due ideatori della nozione di automa a stati finiti non deterministico, ovvero Rabin e Scott, provenivano da contesti diversi. Rabin era nato nel 1931 a Breslavia, città allora appartenente alla Germania, oggi alla Polonia, ed era figlio di un rabbino ebreo. All'età di quattro anni si trasferì con la famiglia nel Mandato britannico della Palestina, dove ebbe l'opportunità di coltivare il suo talento per la matematica studiando nella migliore scuola superiore di Haifa e poi, dal 1949, presso l'Università Ebraica di Gerusalemme. Si laureò nel 1953 e conseguì il dottorato nel 1956.
Scott, invece, era nato a Berkeley, in California, nel 1932. Frequentò la prestigiosa Università della sua città studiando logica e filosofia e ottenendo la laurea nel 1954. Trasferitosi a Princeton, ricevette il PhD nel 1958, sotto la supervisione del celebre matematico Alonzo Church. Subito dopo ottenne un incarico di insegnamento presso l'Università di Chicago.

Nel 1959 la IBM organizzò, nei pressi di New York, un workshop estivo al quale invitò un gruppo ristretto di giovani e promettenti ricercatori. Tra i cervelli selezionati c'erano sia Rabin che Scott: fu così che i destini dei due studiosi si incrociarono.
Probabilmente i due non avrebbero mai pensato che, grazie all'articolo scritto in quell'estate newyorkese, avrebbero fondato una nuova branca dell’informatica teorica e avrebbero vinto, diciassette anni dopo, il premio più prestigioso dedicato alla computer science.
L'importanza del loro concetto di automa non deterministico non venne riconosciuta subito. Tuttavia, dopo il fatidico 1959, la carriera dei due scienziati fu piuttosto rapida. Rabin tornò all'Università di Gerusalemme, dove a soli 29 anni divenne professore associato e capo dell'Istituto di Matematica. Quattro anni dopo era professore ordinario. Scott ottenne un posto a Berkeley, si spostò qualche anno dopo a Stanford e poi a Princeton.

Negli anni successivi Rabin e Scott si occuparono non soltanto di automi non deterministici ma anche di altri temi dell'informatica teorica. Scott divenne un guru nel campo della logica matematica, specialmente per quanto riguarda le logiche non classiche e la semantica denotazionale. Rabin, invece, contribuì in modo determinante allo studio degli automi probabilistici, agli algoritmi di confronto tra stringhe (pattern matching), alla crittografia e alla sicurezza informatica. Trasferitosi nel 1975 al MIT come visiting professor, ideò assieme a Gary Miller un fondamentale procedimento, basato sull'ipotesi di Riemann generalizzata, per determinare velocemente se un numero è primo o no.

mercoledì 14 dicembre 2016

Carnevale della Matematica #104

 Canta allegro, canta, canta

Benvenuti all'edizione n. 104 del Carnevale della Matematica, la quinta ospitata da Mr. Palomar.
Anche nel 2015 era capitato a queste pagine ospitare l'illustre rassegna di contributi a sfondo matematico durante il mese di dicembre. Visto  che la curiosa evenienza si è verificata anche quest'anno, ho ritenuto opportuno proporre un tema di atmosfera natalizia: senza molto fantasia, la scelta è caduta su "stelle, nastri, palle, alberi, code e altre suggestioni matematico-natalizie".
Forse giustamente, pochi dei partecipanti si sono lasciati vincolare da questa traccia, ma noi veterani del Carnevale sappiamo bene che non succede mica niente se si va fuori tema: anzi, non ditelo a nessuno, ma quasi quasi è meglio.
Il Carnevale della Matematica, idea sempre luminosa del mai abbastanza lodato .mau., ha ormai ampiamente superato quota cento, ma non dimostra certo la vetustà di un ultracentenario: come un giovane e vispo virgulto, canta allegro ("canta, canta"), e lo fa sulle vivaci note della cellula melodica dell'amico Flavio "Dioniso" Ubaldini:


Prima di iniziare a scorrere i contributi, vediamo, com'è nella tradizione del Carnevale, alcune proprietà matematiche del numero 104.
Naturalmente, si tratta di un numero pari (quindi, a maggior ragione, non primo ma composto, ragion per cui il motto gaussiano di cui sopra è composto da più parole): i suoi divisori sono 1, 2, 4, 8, 13, 26, 52 e lo stesso 104. Poiché i divisori sono 8, e 8 è uno di loro, si dice che 104 è un numero rifattorizzabile o un numero tau. Essendo pari alla somma di alcuni dei suoi divisori (104 = 1 + 4 + 8 + 13 + 26 + 52), è anche un numero semiperfetto. Perfetto non è, perché sommandoli tutti si va oltre 104 (per questo è detto anche numero abbondante).
Assieme al suo consecutivo 105, forma una coppia di Ruth-Aaron, in quanto la somma dei loro fattori primi senza considerare l'esponente è in entrambi i casi 15.
Compare nelle terne pitagoriche (40, 96, 104), (78, 104, 130), (104, 153, 185), (104, 195, 221), (104, 330, 346), (104, 672, 680), (104, 1350, 1354) e (104, 2703, 2705).
Può essere scritto come somma di quadrati, dato che 104 = 102 + 22.
Infine, è il più piccolo numero di segmenti lineari unitari che possono esistere in un piano, dove quattro di loro si toccano ad ogni vertice.

Uscendo per un attimo dal seminato matematico, dal 2008 è attivo a Parigi un importante centro culturale ed espositivo di 39000 m². Esso è situato in un edificio industriale ottocentesco, un tempo servizio comunale di pompe funebri: trovandosi al numero 104 di Rue d’Aubervilliers, ha preso il nome di "Cent Quatre".

104 è anche il numero di sinfonie di Joseph Haydn (o per lo meno il numero ufficialmente riconosciuto, dato che sicuramente il grande compositore ne scrisse di più).
La più famosa di queste sinfonie è la Sinfonia n. 45 in Fa diesis minore, scritta nel 1772 per il principe Nikolaus Esterházy. Quando la composizione venne eseguita la prima volta, a Eszterhaza, la residenza estiva del principe, nell'adagio finale i musicisti a turno smisero di suonare, spensero la candela del loro leggio e lasciarono la sala: il pezzo fu terminato soltanto da due violini con sordina, uno dei quali era suonato dallo stesso Haydn. Pare che con questo gesto il compositore volesse far capire al principe che il soggiorno a Eszterhazasi era prolungato a dismisura, e tutti i musicisti desideravano tornarsene al più presto presso le loro famiglie. Per questo motivo la sinfonia è universalmente nota come "Sinfonia degli addii".


E veniamo finalmente ai contributi.
Annalisa Santi, dal suo blog Matetango, mi segnala una Intervista Impossibile a Babbo Natale. Come mi scrive la stessa autrice, l'intervista nasce dalla constatazione che ogni bambino prova una grande delusione nel momento in cui scopre che Babbo Natale non è reale: ebbene, l'antidoto a tale dispiacere potrebbe essere un ragionamento fisico-matematico. Come suggerisce la stessa Annalisa, l'intervista potrebbe stimolare anche i più grandicelli a curiosare sui temi della fisica quantistica.

Flavio Ubaldini, noto anche come Dioniso Dionisi, recentemente divenuto anche apprezzato autore teatrale, nonché autore del blog Pitagora e dintorni, non si limita a fornire generosamente la sopra menzionata cellula melodica, ma contribuisce con alcuni suoi lavori.
In particolare, mi segnala Gli n-ternologi su Mathematics in Europe, in cui sottolinea che mentre qualcuno ne esce, il suo blog entra in Europa. Il sito Mathematics in Europe, infatti, ha pubblicato The concept of n-triplewatch, versione inglese del suo post Orologi con terne di singole cifre (n-ternologi) (che era stato seguito da N-ternologi: il 2-ternologio completato).
Flavio propone anche N-ternologi: il 2-ternologio semplificato
in cui racconta come, in seguito alla pubblicazione dell'articolo su Mathematics in Europe, Lorenzo Folcarelli, un giovane studente del Politecnico, abbia proposto una nuova 2-ternoformula per il numero 7.

Roberto Zanasi, dal glorioso blog Gli studenti di oggi
(quello che, per inciso, sarà eternamente ricordato per avere ospitato la prima edizione del Carnevale della Matematica, ormai più di 8 anni fa) offre La Formula del piccolo Gauss senza parole, con un bell'albero di Natale illuminato.

E veniamo ad Alice Riddle (al secolo Francesca Ortenzio), Rudy d'Alembert (all'anagrafe Rodolfo Clerico) e Piotr Rezierovic Silverbrahms (pseudonimo di Piero Fabbri), ovvero gli inimitabili Rudi Matematici. Mi scrivono chiedendo perdono per la fretta con cui mi inviano i loro contributi, ma al tempo stesso mi (ci, vi) regalano una serie di post che come al solito brillano per fantasia e intelligenza.
Il tradizionale Compleanno è dedicato a Norbert Wiener, ed è un pezzo che spazia in modo geniale e gustosissimo tra barzellette sui fisici e sugli ingegneri, circuiti elettrici, sciacquoni e cibernetica. Come sottolineano i tre Rudi, è anche ricchissimo di esempi di retroazione o feedback.
Per la serie dei Giochi del Capo, ecco una nuova puntata, Rien ne va plus 4 - Ogni tanto, va bene a tutti e due, in cui si parla di giochi finiti dove tuttavia si possono incontrare situazioni di loop potenzialmente infinito.
Si prosegue con MacBeth, un articolo che descrive un gioco molto simile all’Othello, al punto che il suo autore ha deciso di battezzarlo con un altro titolo di tragedia shakespeariana.
Infine, Il problema di novembre (579) - Vampiri lineari e quadratici, ovvero il classico post con la soluzione dell'ultimo problema proposto su Le Scienze.
I Rudi fanno poi sapere che il prossimo numero di RM, la rivista fondata nell'altro millennio, è in ritardo ma arriverà presto!

Tocca ora a Math is in the Air, blog divulgativo sulla matematica applicata, sempre molto ricco di spunti interessanti.
Davide Passaro mi comunica che lui e gli altri autori hanno deciso di contribuire con post "belli corposi, in modo che tutti abbiano qualcosa da leggere sotto l'albero mentre mangiano fritti, panettoni e dolci vari!"
Il primo articolo di Davide Passaro ha come titolo I colloqui con i genitori di un insegnante di matematica: la stupidità non è ereditaria. In questo articolo si parla del ruolo della matematica nella società e dell'unica esperienza più temibile di una riunione di condominio o di una fila alla posta: i colloqui fra genitori e professori.

Simulazione con Python: un esempio del profilo di temperatura nel tempo (Parte 2), di Rosario Portoghese, prosegue una serie dedicata alle equazioni differenziali e alla loro discretizzazione usando il linguaggio Python. Il tema è la simulazione dell'equazione di diffusione del calore.
La storia di Pi Greco: intervista recensione a Pietro Greco [Parte 1] è un'intervista al giornalista e divulgatore scientifico Pietro Greco, che parla del suo libro "Storia di Pi Greco" e riflette sulla sua esperienza di giornalista, sull'editoria e sul percorso di divulgatore scientifico.
Teoria dei giochi: il problema delle coppie è un articolo di Giulia Bernardi che prosegue la serie sulla teoria dei giochi. In questo caso si parla del problema delle coppie e di come la matematica può aiutare a trovare il giusto partner.

Completa l'elenco delle segnalazioni di "Math is in the air" il post Kaggle: The Home of Data Science, nel quale Andrea Capozio spiega cosa è Kaggle, una piattaforma online dedicata alle competizioni tra modelli predittivi e analitici.

Non sarebbe un normale Carnevale della Matematica se MaddMaths! non contribuisse con la sua consueta lunghissima serie di articoli di elevata qualità.
Si parte con Sono usciti i risultati dell'indagine OCSE-PISA 2015: nei giorni scorsi, sul sito https://www.oecd.org/pisa, sono stati resi noti i risultati dell’indagine OCSE-PISA 2015. PISA è l’acronimo di Programme for International Student Assessment, ed è un’indagine internazionale triennale volta a valutare le competenze dei quindicenni in scienze, matematica e lettura. L’indagine ha assunto una rilevanza planetaria sia dal punto di vista quantitativo che qualitativo: molto spesso infatti i risultati e le comparazioni tra Paesi sono motivo di dibattito sulla qualità dell’educazione, e talvolta influenzano le scelte di politica educativa.
In La marcia dei piccoli pinguini di Phillip Island si racconta di come alcuni ricercatori italiani di matematica abbiano osservato i piccoli pinguini di Phillip Island in Australia e abbiano trovato un modello matematico per descrivere il modo con cui tornano a casa (spoiler: ogni tanto qualche pinguino entra in crisi).
L'articolo La CIIM dice la sua sulla seconda prova dell'Esame di Stato relaziona sui lavori della Commissione Italiana per l’Insegnamento della Matematica dell'Unione Matematica Italiana (CIIM), che ha proposto un documento sulla questione dell'esame di Stato. Molti ritengono che quest'anno l'esame potrebbe vertere (per la prima volta nella storia del Liceo scientifico di ordinamento) sulla fisica invece che sulla matematica. Questo ha scatenato svariate reazioni nelle comunità vicine al mondo della scuola. MaddMaths! ha inteso dare spazio alla vicenda, alle varie opinioni in merito e agli sviluppi, partendo dal documento della CIIM.
Per quanto riguarda l'Angolo Arguto, MaddMaths! mi segnala Alla mostra di Escher al Palazzo Reale di Milano: Giuseppe Rosolini è andato a Milano a vedere la mostra del celebre artista olandese, e gli è piaciuta (ci ha incontrato anche Fabio Fazio, mi riferisce Roberto Natalini, ma questo Rosolini non lo scrive).


In Ripetizioni - Puntata 8: "Pane" di Davide Palmigiani, si parla di pane, frazioni, antico Egitto e ... Festival della scienza di Genova.
L'articolo Scuola Astre #3 - La teoria dei giochi e l’attività della Pubblica Amministrazione presenta il terzo elaborato della Scuola Astre, proposto da Andrea Renzi, del corso di laurea in Giurisprudenza.
Ricordo di Jean-Christophe Yoccoz, scritto da Stefano Marmi, giunge in seguito alla prematura scomparsa, avvenuta il 3 settembre scorso, di un grande scienziato e di un grande uomo.
In Il Club Segreto dei Triangoli Diversi e il problema dell’area, Fabrizio Calimera, Alessia Cristofanilli e Giulio Codogni descrivono una loro esperienza di teatro e matematica, e in dettaglio raccontano di come, in questo contesto, abbiano provato ad affrontare il problema dell'area.
Infine, se siete dei "buoni boccali" inglesi e volete assaggiare tutte, ma proprio tutte, le birre offerte dai pub del Regno Unito, ora la matematica vi viene in soccorso. Scopritelo in Ecco il "birra tour" perfetto tra i pub inglesi.

Se un Carnevale non può privarsi di MaddMaths!, ancora più imprescindibile è l'apporto del Fondatore, ovvero Maurizio .mau. Codogno, autore non di un solo blog ma almeno di due: quello sul Post, che porta semplicemente il nome del suo autore, e le Notiziole di .mau.
La produzione codogniana dell'ultimo mese è, come sempre, abbondante (anche se Maurizio mi scrive "poca roba stavolta").
Sul Post abbiamo la pillola Pubblicare da morti, con l'ultimo articolo scritto da Ron Graham e Steve Butler insieme a... Paul Erdős, morto vent'anni fa; e il post Più errori nel previsto (negli USA) dove .mau. racconta degli errori nei sondaggi americani.
Sulle Notiziole, al solito ci sono tanti quizzini della domenica: Lancette quasi sovrapposte, Bilancia taroccata, Frase autodefinita e Lavaggio auto. Codogno mi invia anche due recensioni: La magia della matematica (un approccio un po' diverso alle nozioni di matematica nelle scuole superiori) e Reflections: The Magic, Music and Mathematics of Raymond Smullyan (teoricamente un'autobiografia di Smullyan, praticamente, a parere di .mau., una delusione). Per finire, ecco anche Chi ha votato per Trump?, dove vengono spiegati alcuni possibili errori statistici che in genere passano inosservati.

Il blog Al Tamburo Riparato
mi propone Rivoltare una sfera: un contributo sul problema topologico dell'eversione di una sfera. Nell'articolo si parla anche di Stephen Smale: il matematico che, nel 1958, dimostrò che è possibile rivoltare una sfera senza praticare buchi o tagli. Il post si conclude con un valzer di Josef Strauss denominato, non a caso, "musica delle sfere".

Gianluigi Filippelli, autore di DropSea, tiene a precisare che nell'ultimo mese non ha scritto molto: l'unico suo dono al Carnevale di dicembre è Mondo matematico: la crittografia, una recensione/approfondimento particolarmente interessante sul libro "Matematici, spie e pirati informatici" della collana "Mondo Matematico".

Chiudo ricordando (autoreferenzialmente) i due post usciti negli ultimi giorni su queste pagine.
Gli enigmi di Coelum: Natale su Ganimede è l'ennesima puntata della serie sui miei problemi astro-matematici pubblicati negli anni scorsi sulla rivista Coelum. Questa volta è di scena un problema di ambientazione natalizia, con un Babbo Natale intento a svolazzare per il sistema solare a portare regali ai bambini buoni. Moebius di Natale, invece, riesuma un mio vecchio post sui nastri di Moebius, parlando anche dei miei laboratori matematici per bambini.

Ringrazio di cuore tutti gli amici che hanno contribuito al Carnevale con l'abituale bravura e generosità. Appuntamento all'anno nuovo per la prossima edizione. Evviva il Carnevale!