domenica 31 maggio 2009

Siamo tutti critici letterari

Bookreview ha raccolto i cento migliori incipit di romanzi: la posizione numero 30 è occupata da

The sky above the port was the color of television, tuned to a dead channel.

Che probabilmente è l'unica frase di quel libro che merita di essere letta.

(via friendfeed)

sabato 30 maggio 2009

Nidan

Per la serie gli esami non finiscono mai, da oggi posso fregiarmi del titolo di nidan.

Anche noi avevamo i debiti: con una materia insufficiente, ma la media almeno pari a sei, vieni promosso. Con due o tre materie insufficienti (ma sempre con la media del sei), sei rimandato.

Oggi ho compreso per bene l'importanza di uno scrutinio: perché non puoi rimandare un ragazzo con due cinque e mezzo, quando con un cinque e mezzo e un sei sarebbe stato promosso. Dagli quattro, se vuoi, ma abbi un minimo di decenza. Così lo prendi in giro: sarebbe come bocciare uno all'esame di stato con cinquantanove.

(No, io niente debiti, eh)

giovedì 28 maggio 2009

L'ultima settimana di scuola

“Prof, ascolti, io ho due, tre e mezzo e quattro allo scritto. All'orale ho preso due e tre. Domani posso farmi interrogare per rimediare?”.


“Ehm. Proprio domani, che è l'ultima ora dell'anno? Perché non vieni oggi che abbiamo due ore?”.

“Eh, no, prof, devo ripassare. Facciamo domani?”.

“Prof, domani vorrei venire anche io a farmi interrogare”.

“Anche io!”.

“Ehi, anche io!”.

“C'eravamo prima noi due!”.

“Io mi sono prenotato la settimana scorsa!”.

“Noi cinque volevamo venire fuori ora, possiamo?”.

martedì 12 maggio 2009

La strana e meravigliosa chimica del decadimento audioattivo - la costante di Conway

Il decadimento audioattivo è analogo alla compressione RLE, usata ad esempio nei fax. L'idea alla base di questo tipo di compressione senza perdita di informazioni è questa: invece di memorizzare n byte tutti uguali, memorizzo n e un solo byte. In pratica un pezzo di immagine tutta bianca, che verrebbe memorizzata come BBBBBBBBBB, una volta compressa diventerebbe 10B.

Non è un sistema molto efficiente, tant'è che nel decadimento audioattivo la stringa che decade pian piano aumenta la sua dimensione. Magari qualche volta la lunghezza potrà anche diminuire, ma in media aumenterà. Ecco un esempio:

11111111
81
1811
111821
31181211
132118111221

Bene, Conway ha studiato la crescita di una generica sequenza, scoprendo che l'n-esima stringa ha una lunghezza proporzionale a λn, dove λ è circa uguale a 1.303577.

Per essere più preciso, ha specificato che λ è l'unica soluzione positiva della seguente equazione:

x71-x69-2x68-x67+2x66+2x65+x64-x63-x62-x61-x60-x59
 +2x58+5x57+3x56-2x55-10x54-3x53-2x52+6x51+6x50+x49+9x48-3x47
 -7x46-8x45-8x44+10x43+6x42+8x41-5x40-12x39+7x38-7x37+7x36+x35
 -3x34+10x33+x32-6x31-2x30-10x29-3x28+2x27+9x26-3x25+14x24-8x23
 -7x21+9x20+3x19-4x18-10x17-7x16+12x15+7x14+2x13-12x12-4x11
 -2x10+5x9+x7-7x6+7x5-4x4+12x3-6x2+3x-6 = 0.

Ecco una rappresentazione sul piano complesso di tutte le 71 soluzioni del precedente polinomio: si vede che tre di esse sono reali, e una sola positiva: quella è λ, detta anche costante di Conway.


Rimane un'ultima questione: se prendo una generica stringa e la faccio decadere, posso aspettarmi di trovare tutti i 92 elementi distribuiti con la stessa frequenza?

Naturalmente la risposta è no: alcuni elementi sono più rari, altri più comuni: basta osservare la tabella del decadimento per notare che alcuni elementi compaiono con maggiore frequenza. Ecco qua la lista di tutti gli elementi con le loro frequenze relative:

1   91790.38321598
 2    3237.29685875
 3    4220.06659818
 4    2263.88603245
 5    2951.15037158
 6    3847.05254190
 7    5014.93024640
 8    6537.34907500
 9    8521.93965391
10   11109.00682092
11   14481.44877330
12   18850.44122748
13   24573.00669542
14   32032.81295997
15   14895.88665819
16   19417.93924972
17   25312.78421743
18   32997.17012181
19   43014.36091325
20   56072.54312854
21    9302.09744434
22   12126.00278278
23   15807.18159188
24   20605.88261067
25   26861.36017966
26   35015.85854555
27   45645.87725570
28   13871.12419974
29   18082.08220273
30   23571.39133629
31    1447.89056423
32    1887.43722758
33      27.24621608
34      35.51754794
35      46.29986815
36      60.35545568
37      78.67800009
38     102.56285249
39     133.69860315
40     174.28645997
41     227.19586752
42     296.16736852
43     386.07704943
44     328.99480576
45     428.87015042
46     559.06537945
47     728.78492056
48     950.02745645
49    1238.43419719
50    1614.39466866
51    2104.48819331
52    2743.36297175
53    3576.18561068
54    4661.83427193
55    6077.06118890
56    7921.91882838
57   10326.83331181
58   13461.82516638
59   17548.52928660
60   22875.86388300
61   29820.45616740
62   15408.11518153
63   20085.66870930
64   21662.97282106
65   28239.35894924
66   36812.18641833
67   47987.52943839
68    1098.59559973
69    1204.90838414
70    1570.69118084
71    2047.51732002
72    2669.09703633
73     242.07736666
74     315.56655252
75     169.28801808
76     220.68001229
77     287.67344775
78     375.00456739
79     488.84742983
80     637.25039755
81     830.70513293
82    1082.88832855
83    1411.62861001
84    1840.16696832
85    2398.79983113
86    3127.02093283
87    4076.31340783
88    5313.78949991
89    6926.93520451
90    7581.90471245
91    9883.59863913
92     102.56285249

E questo, almeno per ora, è tutto.



“Ma tutto questo, a che scopo?”.

“Bé, per amor di precisione”.

“Precisione?”.

“Certo, è brutto dire che conosciamo solo l'approssimazione di una certa costante...”.

“Brutto? Ma ti rendi conto? Un'equazione di settantunesimo grado per definire un numero? Che oltretutto serve per spiegare come funziona un giochino? Spero almeno che abbia qualche applicazione”.

“Naturalmente...”.

“Ah, meno male. E dove viene usata, tutta questa matematica?”.

“No, ehm, stavo dicendo naturalmente no”.

“Eh? Non serve a niente? E sette persone, per non parlare del computer con nome e cognome...”.

“Ha anche un secondo nome”.

“Eh?”.

“Il computer con nome e cognome si chiama Shalos B. Ekhad, ha anche un secondo nome...”.

“Roba da matti. Sette persone e un computer con nome, secondo nome e cognome, impiegano vent'anni per studiare come funziona un giochino, tentando di ridimostrare un teorema perduto e inutile scritto su foglietti volanti, oltretutto non riuscendoci completamente?”.

“Sì, hai riassunto bene la storia. Anche se i Veri Matematici non dicono mai che i loro teoremi non servono a niente. In verità, i teoremi servono per fare altri teoremi”.

“Voi siete matti”.

lunedì 11 maggio 2009

La strana e meravigliosa chimica del decadimento audioattivo - il teorema cosmologico

Abbiamo conosciuto le 92 stringhe atomiche del decadimento audioattivo. Ma che succede se prendiamo una stringa a caso e la facciamo decadere? Decaderà sicuramente, dopo un certo tempo, in sole stringhe atomiche?

Conway pubblicò nel 1986 i suoi studi riguardanti il gioco del decadimento audioattivo su Eureka, la rivista degli Archimedeans, cioè la società matematica dell'università di Cambridge; la maggior parte degli articoli è scritta da studenti (!), ma nell'elenco degli autori troviamo anche gente come Dirac, Erdős, Hofstadter, Stewart, per dire.

In quell'articolo Conway racconta di aver dimostrato, con la collaborazione di Richard Parker, che qualunque stringa arbitrariamente scelta decade in un composto di elementi comuni e transuranici — questa affermazione venne chiamata teorema cosmologico. La dimostrazione era scritta su foglietti e, purtroppo, è andata perduta.

In seguito Mike Guy calcolò il massimo numero di iterazioni necessarie per fare decadere una qualunque stringa, trovando il valore 24. Anche questa dimostrazione, però, è persa.

L'articolo di Conway conteneva una richiesta ai lettori: Can you find a proof in just a few pages? Please!

Nel 1997 uscì un articolo, scritto da Shalosh B. Ekhad e Doron Zeilberger, che conteneva la risposta: sì, la dimostrazione era stata trovata, ma richiedeva l'uso di un computer. Un uso pesante: dal sito degli autori si può scaricare un pacchetto che gira sotto Maple e, dopo un paio di settimane, produce il risultato (un paio di settimane del 1997 — sarei curioso di sapere quanto ci mette oggi, se qualcuno ha Maple può provarlo?).

La dimostrazione non era però perfetta: il programma dimostrava che il teorema cosmologico è vero, ma dava come massimo numero di iterazioni il valore di 29, più alto di quello trovato da Conway. Il fatto meraviglioso di questo lavoro, comunque, riguarda i due autori: Doron Zeilberger è un umano, ma Shalosh B. Ekhad è il suo computer. E risulta accreditato come autore.

Ma andiamo avanti: nel 2003 (con qualche correzione apportata poi nel 2006) R.A. Litherland provò a ridimostrare, utilizzando altre tecniche di programmazione, il teorema. Secondo l'autore il suo programma è simile, in spirito, alla dimostrazione perduta di Conway e Parker. Citando Conway, essa consisteva di “a very subtle and complicated argument, which (almost) reduced the problem to tracking a few hundred cases”, casi che erano “handled on dozens of sheets of paper (now lost)”. Litherland ammette che, forse, la sua tecnica non è abbastanza sottile, perché comunque deve considerare 3360 casi distinti. Comunque è molto veloce, e in poco tempo fornisce la soluzione corretta, compreso il famoso valore di 24 iterazioni.

Ma le dimostrazioni fatte con l'ausilio del computer non sempre sono ben viste dai matematici, soprattutto quando non si è sicuri al di là di ogni ragionevole dubbio (cioè mai) che il software funzioni come si deve. Nel 2006, quindi, entra in scena un altro matematico, Kevin Watkins, che dimostra nuovamente il teorema cosmologico utilizzando il linguaggio Haskell; per me è totalmente incomprensibile, perché non è un linguaggio procedurale, comunque il codice è notevolmente più corto e, quindi, più facilmente controllabile.

E questo pone fine (almeno per ora) alla sequenza di dimostrazioni del teorema cosmologico di Conway: se la sua dimostrazione fatta su foglietti di carta era corretta, non è ancora stata trovata.

Rimane da chiarire un'ultima questione: è davvero 24 il valore minimo di iterazioni necessarie per far decadere qualunque stringa in elementi comuni? Sì, qua la risposta è certa: Conway trovò un controesempio, un composto che decade proprio in 24 iterazioni, da lui chiamato Methuselum (quale altro nome sarebbe stato altrettanto appropriato...?). Eccolo qua:

0: 22333222112
 1: 2233322112
 2: 2233222112
 3: 2223322112
 4: 3223222112
 5: 132213322112
 6: 1113221123222112
 7: 311322211213322112
 8: 1321133221121123222112
 9: La.H.123222112211213322112
10: 11121332212221121123222112
11: Sr.32211322112211213322112
12: 1322211322212221121123222112
13: 11133221133211322112211213322112
14: 3123222.Ca.Li
15: 1311121332
16: 11133112112.Zn
17: Zn.321122112
18: 131221222112
19: 1113112211322112
20: 311321222113222112
21: 1321131211322113322112
22: 111312211311122113222.Na
23: 3113112221133122211332
24: Ho.Pa.H.Ca.Ac.H.Ca.Zn

Guy ne trovò un altro, più efficiente perché più breve, che in seguito fu ulteriormente migliorato da Litherland eliminando le prime due cifre. Dato che era più corto, lo chiamò Thuselum:

0: 333222112
 1: 33322112
 2: 33222112
 3: 23322112
 4: 1223222112
 5: 112213322112
 6: 21221123222112
 7: 121122211213322112
 8: 111.H.13221121123222112
 9: 31.1113222112211213322112
10: 1311.311332212221121123222112
11: 111321.Pm.Ca.32211322112211213322112
12: 31131211.1322211322212221121123222112
13: 132113111221.11133221133211322112211213322112
14: 1113122113312211.3123222.Ca.Li
15: Er.Ca.Sb.1311121332
16: 11133112112.Zn
17: Zn.321122112
18: 131221222112
19: 1113112211322112
20: 311321222113222112
21: 1321131211322113322112
22: 111312211311122113222.Na
23: 3113112221133122211332
24: Ho.Pa.H.Ca.Ac.H.Ca.Zn

Per quanto riguarda il teorema cosmologico, non c'è altro da aggiungere. Ma lo studio non è finito qua: rimangono ancora alcune domande. Quanto sono frequenti gli elementi? Cioè, se una stringa scelta a caso decade, i vari elementi sono ugualmente distribuiti oppure possiamo aspettarci che qualcuno di essi sia più comune e qualcun altro più raro? E poi, come decade una stringa? Di quanto aumenta, se aumenta, la sua dimensione? Ma questa è un'altra storia, e si dovrà raccontare un'altra volta.

domenica 10 maggio 2009

È un duro lavoro

Un mio studente è arrivato primo nella sua categoria ai giochi matematici Kangourou, ed è stato ammesso alla finale. Mi tocca accompagnarlo, starò via da questa sera a martedì.

A Mirabilandia.

giovedì 7 maggio 2009

La strana e meravigliosa chimica del decadimento audioattivo - gli elementi

Dunque una stringa decade, seguendo le regole del decadimento audioattivo, in una stringa più lunga ma spezzabile in tante parti separate, indipendenti. Esistono quindi delle stringhe indivisibili, atomiche?

Sì, effettivamente è così, esistono delle stringhe di base che non sono ulteriormente divisibili. Per esempio la stringa 22 è un atomo, ed è anche stabile, ovvero non decade. Il fatto meraviglioso è che di stringhe atomiche ce ne sono 92, tante quanti sono gli elementi chimici naturali (wikipedia dice che qualche elemento transuranico è stato rinvenuto anche in natura, ma non sottilizziamo). Data la forte analogia con la chimica, Conway ha deciso di chiamare ogni stringa atomica con il nome di un elemento chimico, partendo dall'Uranio e facendolo decadere fino all'Idrogeno.

Ecco la tabella con tutte le stringhe atomiche:

92 U   3
91 Pa  13
90 Th  1113
89 Ac  3113
88 Ra  132113
87 Fr  1113122113
86 Rn  311311222113
85 At  Ho.1322113
84 Po  1113222113
83 Bi  3113322113
82 Pb  Pm.123222113
81 Tl  111213322113
80 Hg  31121123222113
79 Au  132112211213322113
78 Pt  111312212221121123222113
77 Ir  3113112211322112211213322113
76 Os  1321132122211322212221121123222113
75 Re  111312211312113221133211322112211213322113
74 W   Ge.Ca.312211322212221121123222113
73 Ta  13112221133211322112211213322113
72 Hf  11132.Pa.H.Ca.W
71 Lu  311312
70 Yb  1321131112
69 Tm  11131221133112
68 Er  311311222.Ca.Co
67 Ho  1321132.Pm
66 Dy  111312211312
65 Tb  3113112221131112
64 Gd  Ho.13221133112
63 Eu  1113222.Ca.Co
62 Sm  311332
61 Pm  132.Ca.Zn
60 Nd  111312
59 Pr  31131112
58 Ce  1321133112
57 La  11131.H.Ca.Co
56 Ba  311311
55 Cs  13211321
54 Xe  11131221131211
53 I   311311222113111221
52 Te  Ho.1322113312211
51 Sb  Eu.Ca.3112221
50 Sn  Pm.13211
49 In  11131221
48 Cd  3113112211
47 Ag  132113212221
46 Pd  111312211312113211
45 Rh  311311222113111221131221
44 Ru  Ho.132211331222113112211
43 Tc  Eu.Ca.311322113212221
42 Mo  13211322211312113211
41 Nb  1113122113322113111221131221
40 Zr  Er.12322211331222113112211
39 Y   1112133.H.Ca.Tc
38 Sr  3112112.U
37 Rb  1321122112
36 Kr  11131221222112
35 Br  3113112211322112
34 Se  13211321222113222112
33 As  11131221131211322113322112
32 Ge  31131122211311122113222.Na
31 Ga  Ho.13221133122211332
30 Zn  Eu.Ca.Ac.H.Ca.312
29 Cu  131112
28 Ni  11133112
27 Co  Zn.32112
26 Fe  13122112
25 Mn  111311222112
24 Cr  31132.Si
23 V   13211312
22 Ti  11131221131112
21 Sc  3113112221133112
20 Ca  Ho.Pa.H.12.Co
19 K   1112
18 Ar  3112
17 Cl  132112
16 S   1113122112
15 P   311311222112
14 Si  Ho.1322112
13 Al  1113222112
12 Mg  3113322112
11 Na  Pm.123222112
10 Ne  111213322112
 9 F   31121123222112
 8 O   132112211213322112
 7 N   111312212221121123222112
 6 C   3113112211322112211213322112
 5 B   1321132122211322212221121123222112
 4 Be  111312211312113221133211322112211213322112
 3 Li  Ge.Ca.312211322212221121123222112
 2 He  13112221133211322112211213322112
 1 H   Hf.Pa.22.Ca.Li

Dobbiamo leggerla in questo modo: l'Uranio decade nel Protoattinio, perché 3 diventa 13, il quale decade a sua volta nel Torio, perché 13 diventa 1113, e così via. Se in una stringa compaiono simboli di altri elementi, significa che la stringa precedente decade in più di un elemento: per esempio, la stringa del Samario (311332) decade in 13212312, che si spezza (secondo le regole già enunciate) in 132.12.312: 132 corrisponde al Promezio, 12 a Calcio e 312 a Zinco. L'ultimo elemento nella lista è l'Idrogeno (22), che è stabile. Il fatto che le stringhe più lunghe siano composte da 42 cifre non deve farvi prendere dal panico.

Come si vede, non compare mai la cifra 4, a meno che non la inseriamo noi all'inizio (infatti nulla vieta di fare partire il decadimento da una stringa contenente cifre maggiori di 3). Ma anche le stringe artificiali contenenti una cifra maggiore di 3 sono state previste e studiate da Conway: esse decadono in elementi naturali e in elementi chiamati transuranici. Questi ultimi costituiscono due diverse famiglie, quella del Plutonio, che corrisponde a

Pux = 31221132221222112112322211x

dove con x indichiamo una qualunque cifra maggiore di 3, e quella del Nettunio, l'elemento nel quale decade il Plutonio e che corrisponde a

Npx = 1311222113321132211221121332211x

A sua volta il Nettunio decade in elementi stabili e Plutonio — più precisamente, il Nettunio diventa Hf.Pa.H.Ca.Pux.

Ora la prossima domanda: abbiamo visto che se partiamo dall'Uranio (3) otteniamo tutti gli elementi, ma è così per qualunque stringa scritta a caso? È vero che ogni possibile stringa decade solo in questi elementi, prima o poi? (E quanto poi?)

Ma la storia della ricerca della risposta a questa domanda merita un post a parte...

martedì 5 maggio 2009

La strana e meravigliosa chimica del decadimento audioattivo - fissione

1
11
21
1211
111221
...


Cosa viene dopo? Questa semplice domanda ci permette di dividere il mondo in tre categorie: quelli che rispondono “boh?”, quelli che ci pensano un po' e poi trovano la risposta, e i Veri Matematici.

Dunque, cosa viene dopo? Non è facile rispondere, perché... Beh, provateci un po', prima di continuare a leggere.

Trovata la soluzione? Il motivo per cui è difficile rispondere è dovuto al fatto che quelli che leggiamo non sono semplici numeri, ma sono descrizioni di numeri (metanumeri?). Ogni riga, infatti, descrive la precedente: cosa si legge nella prima riga, per esempio? Una cifra uno, cioè “un uno”, in numeri 11.

Cosa si legge nella seconda? Due cifre uno, cioè “due uno”, in numeri 21. Poi leggiamo un due e un uno, cioè 1211, e così via. Chi appartiene alla seconda categoria si ferma qui, ben felice di aver trovato la soluzione. Cosa fa invece un Vero Matematico? Certamente non si ferma alla soluzione del quesito: ora che ha scoperto cosa viene dopo, vuole capire come funziona la regola. E quindi comincia a domandarsi: posso prevedere come sarà la n-esima stringa? Come si evolvono le stringhe? Ma è un caso che compaiano solo le cifre 1, 2 e 3? Compare mai la cifra 4?

In sostanza, un Vero Matematico si domanda: posso ricavare una qualche regola?

Si dà il caso che in questo giochino di regole ce ne siano tante, e per nulla banali.

Per esempio: in che modo una stringa influenza la successiva? Dobbiamo valutare una sequenza di cifre nella sua globalità, per stabilire come sarà la successiva? La risposta è no: se sono valide certe condizioni possiamo spezzare una stringa in sottostringhe separate, e farle evolvere separatamente. Ecco qua le condizioni:


1) ...m][n..., se m è maggiore o uguale di 4 e n è minore o uguale di 3

Con questa simbologia vogliamo indicare che una stringa si spezza in corrispondenza delle due parentesi quadrate se m è maggiore o uguale di 4 e n è minore o uguale di 3: ciò significa che le due cifre m e n non si influenzano nella generazione della stringa successiva. Per esempio, osserviamo l'evoluzione seguente:

124.1
111214.11
31121114.21
1321123114.1211


tutto quello che avviene prima della cifra 4 non può modificare quello che avviene dopo: se noi prendiamo le due stringhe 124 e 1 e le facciamo evolvere separatamente, ottieniamo lo stesso risultato. Vediamo gli altri casi in cui le stringhe si spezzano:

2) ...2][11x1...

Con questa simbologia vogliamo intendere che una stringa si spezza in due se un 2 è seguito da un singolo 1 e un'altra singola cifra diversa da 1

3) ...2][13...

4) ...2][31x≠3...

Qui, con una simbologia che il mio vecchio prof di meccanica razionale avrebbe definito sportiva, intendiamo che il 3 è seguito da un'altra cifra che può anche ripetersi, ma non per tre volte.

5) ...2][n1...

6) ...≠2][2211x1...

Qui si intende che la cifra prima della parentesi quadra deve essere diversa da 2.

7) ...≠2][2213...

8) ...≠2][2231x≠3...

9) ...≠2][22n{0|1}...

Qua si intende che la cifra n o non c'è o è presente una sola volta.

Queste regole ci fanno capire un concetto fondamentale: è vero che la stringa da cui si parte aumenta di dimensione ad ogni passaggio, però essa è spezzabile in varie sottostringhe che possono essere studiate separatamente. Quindi la domanda che dovrebbe nascere spontanea è: esistono delle sottostringhe di base che generano tutto il resto, come se fossero una sorta di atomi, oppure no? Se sì, quante sono? Come sono fatte? Che proprietà hanno?

Vedremo prossimamente quali sono le risposte a queste domande, perché ora ne sorge una ancora più importante: che nome diamo a questo procedimento di costruzione di stringhe numeriche?

Il nome scelto dal Vero Matematico che ha studiato il tutto, Conway (sempre lui, sì), è il seguente: decadimento audioattivo.