Fabrizio Luccio
Università di Pisa
Informazione e casualità
Anche se non ci si pensa, c’è un concetto matematico alla base della comunicazione tra gli uomini e forse tra tutte le altre creature
la crescita esponenziale
è un fenomeno sottile e in genere
massacrato nel linguaggio comune
crescita esponenziale e comunicazione
Quante parole di tre lettere si possono costruire con il nostro alfabeto ?
le parole: aaa aab aac . . . . zzz
Infatti con un alfabeto di k > 1 simboli il numero p di parole di lunghezza n cresce esponenzialmente con n :
p = k n
per le parole: aaa aab aac . . . . zzz
abbiamo k = 26 , n = 3, p = 26
3= 17.576
Questa legge matematica vale per la comunicazione orale (fonemi) e scritta (caratteri alfabetici)
I primi caratteri nella storia della scrittura
furono ideografici; poi, con un processo in
parte graduale ma comunque straordinario,
si sono trasformati in fonetici.
EGITTO
IV DINASTIA
2620 – 2500 A.C.
Dalle istruzioni di Dua-Khety a suo figlio Pepy:
(Egitto. XII Dinastia, circa 1800 A.C.)
il vasaio è ricoperto di argilla, anche i suoi abiti divengono rigidi . . . . il messaggero è terrorizzato dai leoni . . . .
il calzolaio vive infelice tra i sui tubi di colla . . . .
il lavandaio lava i panni nel fiume tra i coccodrilli . . . .
dirigiti dunque verso la professione dello scriba !
Nasce il codice binario in Europa
Meditatio Proemialis. Johannes Caramuel’s Matesis Biceps Vetus et Nova, 1670
Tutti i nostri documenti, siano scritti, immagini o suoni, sono rappresentati nei sistemi elettronici come sequenze di caratteri di un alfabeto binario
. . . ma il metodo è molto più antico del
codice di Caramuel
YI JING
Libro dei Mutamenti, Cina ~ 200 A.C.
Divinazione Ifá nella cultura Yorubá in Nigeria ~ 1200 D.C.
Nel 2005 questo sistema è stato inserito dall’UNESCO nella lista dei Masterpieces of the Oral and Intangible Heritage of Humanity
. . . . e infatti vi è qualcosa di magico nel
sistema binario
Braille: un codice binario sorprendente
(a) Le sei posizioni dei punti in Braille
(b) La lettera B: punti sporgenti in nero
(c) Il numero 2, composto dal “segno numeri” per
il cambio di significato, seguito da una B
Il ruolo del caso
Una raccomandazione preliminare:
Bi à bà rùbo ki à mù t’Èsù kuro
Pierre-Simon Laplace (1814). Essai philosophique sur les probabilités .
Il pensiero di Laplace
Laplace sottolineò come sia sbagliato credere che il verificarsi di un “evento regolare” come l’apparizione di venti teste consecutive nel lancio di una moneta sia
meno probabile di qualsiasi altra sequenza “irregolare”
di risultati.
E aggiunse . . . Le combinazioni regolari arrivano più raramente perché sono meno numerose.
L’esperimento di Laplace
Lancio di una moneta per venti volte (Croix o Pile)
C C C C C C C C C C C C C C C C C C C C C C P C P P P C C P C P C C P C P C P P
Lanciando a caso, le due sequenze hanno la stessa probabilità 1/220 < 1/(1 Milione) di apparire
Genera “ 20 C ”
Genera “ C C P C ...”
Intuitivamente una sequenza S è casuale (random) se non esiste un metodo per descriverla (algoritmo per generarla) che può essere a sua volta
rappresentato con una sequenza più corta di S.
Da un punto di vista matematico questa affermazione assume un senso preciso solo se è basata su una
rigorosa definizione di algoritmo come quelle date da
Alan Turing e altri logici nella prima metà del secolo
scorso. Laplace non aveva questa possibilità.
Di qui nasce una delle pagine più interessanti* della matematica recente:
la complessità secondo Kolmogorov
*
Questo lo dico io: forse i matematici non sono altrettanto interessati.È una teoria molto difficile: cerchiamo di capire
quali ne siano l’essenza e il significato
La base teorica
Vi sono innumerevoli modi per definire una famiglia di sistemi si calcolo: per esempio una famiglia di
“macchine di Turing”, o una di PC che usano il
linguaggio Java, ecc.
In ogni famiglia di sistemi di calcolo (per esempio PC differenti che usano il linguaggio Java), la lunghezza
dell’algoritmo più corto per generare una sequenza S è la complessità algoritmica di S e si indica con K(S) .
Un fondamentale teorema d’invarianza mostra che il
valore di K(S) è sostanzialmente indipendente dal
membro della famiglia (cioè dal PC) scelto per il
calcolo.
K (S) (lunghezza dell’algoritmo più corto) è il contenuto d’informazione di S .
Una sequenza S è casuale se e solo se K ( S ) = | S |
In conclusione:
La casualità è ora definita come proprietà
intrinseca di una sequenza, indipendentemente dalla sorgenta che l’ha generata.
Una sequenza che può essere descritta con una breve regola non è casuale anche se è stata
generata perfettamente a caso.
Questa definizione non implica l’esistenza, filosoficamente discutibile, di sorgenti
random.
Due importanti proprietà delle sequenze random, dimostrabili matematicamente
Esistono sequenze random lunghe n, per ogni valore di n.
Non può esistere un algoritmo per
stabilire se una sequenza arbitraria
è random
Ma allora è possibile comprimere i dati ?
In genere sí (per esempio con gzip).
Teoricamente la massima compressione di una sequenza S si ottiene sostituendo a S il
programma più corto che la genera. Quindi le sequenze casuali non possono essere compresse.
In altre parole le sequenze casuali contengono
la massima quantità d’informazione in funzione
della loro lunghezza.
Casualità e informazione:
due ritmi musicali in “Box Notation”
ROCK (origine europea)
RUMBA (origine africana)
E che dire del codice biologico ?
T C A G
T TTT Phe (F) TCT Ser (S) TAT Tyr (Y) TGT Cys (C)
TTC " TCC " TAC " TGC "
TTA Leu (L) TCA " TAA Ter TGA Ter
TTG " TCG " TAG Ter TGG Trp (W)
C CTT Leu (L) CCT Pro (P) CAT His (H) CGT Arg (R)
CTC " CCC " CAC " CGC "
CTA " CCA " CAA Gln (Q) CGA "
CTG " CCG " CAG " CGG "
A ATT Ile (I) ACT Thr (T) AAT Asn (N) AGT Ser (S)
ATC " ACC " AAC " AGC "
ATA " ACA " AAA Lys (K) AGA Arg (R)
ATG Met (M) ACG " AAG " AGG "
G GTT Val (V) GCT Ala (A) GAT Asp (D) GGT Gly (G)
GTC " GCC " GAC " GGC "
GTA " GCA " GAA Glu (E) GGA "
GTG " GCG " GAG " GGG "
