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
Il pensiero di Laplace
Pierre-Simon Laplace (1814). Essai philosophique
sur les probabilités.
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
Genera “ 20 C ”
C C P C P P P C C P C P C C P C P C P P
Genera “ C C P C ...”
Lanciando a caso, le due sequenze hanno la stessa probabilità
1/220 < 1/(1 Milione) di apparire
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
È una teoria molto difficile: cerchiamo di capire
quali ne siano l’essenza e il significato
* Questo lo dico io: forse i matematici non sono
altrettanto interessati.
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.
In conclusione:
K(S) (lunghezza dell’algoritmo più corto) è il
contenuto d’informazione di S.
Una sequenza S è casuale se e solo se K (S ) = |S |
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)
TTC "
TTA Leu (L)
TTG "
TCT Ser (S)
TCC "
TCA "
TCG "
TAT Tyr (Y)
TAC "
TAA Ter
TAG Ter
TGT Cys (C)
TGC "
TGA Ter
TGG Trp (W)
C
CTT Leu (L)
CTC "
CTA "
CTG "
CCT Pro (P)
CCC "
CCA "
CCG "
CAT His (H)
CAC "
CAA Gln (Q)
CAG "
CGT Arg (R)
CGC "
CGA "
CGG "
A
ATT Ile (I)
ATC "
ATA "
ATG Met (M)
ACT Thr (T)
ACC "
ACA "
ACG "
AAT Asn (N)
AAC "
AAA Lys (K)
AAG "
AGT Ser (S)
AGC "
AGA Arg (R)
AGG "
G
GTT Val (V)
GTC "
GTA "
GTG "
GCT Ala (A)
GCC "
GCA "
GCG "
GAT Asp (D)
GAC "
GAA Glu (E)
GAG "
GGT Gly (G)
GGC "
GGA "
GGG "
Un alfabeto quaternario A,C,T,G per codificare
solo 21 aminoacidi !
Perché questa ridondanza ?
Nel DNA le sezioni non-codificanti possono essere
compresse con programmi standard, mentre in
genere le sezioni che rappresentano i geni (codici
di proteine) non possono essere compresse,
ovvero appaiono come casuali.
Come si può interpretare questo fatto ? Forse i geni
sono rappresentati in forma ottimizzata nel senso
che la natura ha escluso dal loro codice tutto ciò
che non contiene informazione utile.
E ora una questione finale:
in termini matematici le sequenze casuali
contengono la massima quntità d’informazione
come umani, siamo pronti ad accettare
questo fatto ?