Quando si parla di teoria dell’informazione non si può non fare a meno di parlare del suo padre fondatore Claude Shannon, un ingegnere elettrico e matematico statunitense, il quale, nel 1948, pubblicò un articolo sul Systems Technical Journal, intitolato A Mathematical Theory of Communication.98 Sarebbe molto bello poter entrare più nel dettaglio del percorso accademico di Shannon e della sua prima applicazione della Markov chain alla lingua Inglese, tuttavia non è possibile farlo in questa sede. Prenderemo qui in
97Per un approfondimento su queste tematiche vedi, [Gol10]. 98[Sha48].
considerazione il concetto chiave sviluppato da Shannon e che ha dato vita a quella che oggi si chiama teoria dell’informazione, ovvero il fatto che si possa parlare di entropia anche per quanto riguarda l’informazione che si vuole comunicare.
Prima di poter addentrarci nel concetto di entropia bisogna introdurre ciò che Shannon definì per la prima volta e che ha segnato per sempre l’era digitale: il concetto di bit. Prima di tutto ‘bit’ sta per binary digit, ovvero i numeri del sistema binario 0 e 1, ma questo ci dice davvero molto poco; per comprendere la portata concettuale di questo strumento di misura dob- biamo considerare come Shannon non era interessato alle componenti prag- matiche e semantiche dell’informazione, in effetti non definisce mai cosa sia l’informazione ma piuttosto cerca di capire come poter comunicare attraverso un canale messaggi sintatticamente corretti. Questa non è assolutamente una semplificazione da poco, eppure, questo rimane un campo di indagine molto complesso: prima di tutto cosa comunichiamo? Ci comunichiamo dei mes- saggi ed essi non sono altro che un tipo particolare di informazione; quindi che cos’è l’informazione? Essa è quel quid che ci permette di eliminare o ridurre l’incertezza, quel quid che ci provoca la sorpresa quando riceviamo un messaggio piuttosto che un altro. Quindi anche se Shannon non fornisce mai delle definizioni esplicite di cosa intendesse per informazione, senza dub- bio certe definizioni rimangono comunque implicite nel suo lavoro. Tuttavia il passo tra comunicazione ed informazione era diventato talmente ovvio che in breve tempo la sua teoria verrà appunto chiamata teoria dell’informazione. L’idea che sta alla base del bit è proprio quella di saper cogliere la dif- ferenza tra due stati, ed sta proprio in questa capacità che risiede la nostra
abilità di comunicare informazione. Supponiamo di essere dotati di un qual- siasi apparecchio di comunicazione, dal telegrafo visivo, a quello elettrico fino ai social media moderni; adesso immaginiamo che un interlocutore ci voglia comunicare qualcosa, ma, l’unica cosa che noi possiamo fare è ricevere risposte, come un ‘si’ o un ‘no’ a delle domande prefissate. Il nostro inter- locutore risponderà quindi inviando una serie di ‘1’ e ‘0’, usando un qualche metodo di variazione, in quanto tutti i metodi di trasmissione di informazione richiedono lo scambio di differenze tra due stati: ecco che un 1 potrebbe es- sere una fiamma accesa o un impulso elettrico e lo 0 l’assenza di essi. Non importa sotto quale forma andiamo a considerarli, questi due stati possono comunque essere descritti come binary digit, il bit, che considereremo come la risposta ‘si’ nel caso di un 1 ad e come ad un ‘no’ per lo 0. Ora tutto quello che si richiede è di avere la giusta serie di risposte ad una serie pre- fissata di domande, tali che ci permettano di identificare in maniera certa l’informazione contenuta nel messaggio.
Uno dei casi più semplici a cui si può pensare come esempio è lo scam- bio di informazione riguardante il lancio di una moneta: chi deve inviare l’informazione ha bisogno di selezionare uno dei due possibili simboli della moneta, testa o croce. Risulta subito immediato come in una sola domanda sia possibile comunicare con certezza il risultato di un lancio di una moneta, basterà la domanda: è testa? Se la risposta è un 1 significa che abbiamo già la nostra risposta, se invece è uno 0 abbiamo comunque la nostra risposta per esclusione. Il numero minimo di domande che sarà necessario fare per sapere il risultato di dieci lanci di moneta saranno quindi 10, ed equivalgono a 10bit di informazione. In un senso intuitivo quindi il bit, la nostra unità
di misura per l’informazione non rappresenta altro che il numero minimo di domande che si devono fare per sapere cosa ci viene comunicato.
Adesso però cerchiamo di complicare un po’ il quadro supponendo di volerci scambiare una lettera dell’alfabeto, si potrebbe ingenuamente pen- sare di partire dalla prima dell’alfabeto e chiedere lettera per lettera finché non si sia trovata quella giusta. Questo metodo ci porta alla risposta ma non è molto efficiente in quanto richiede di media molte domande e quindi molta informazione per lettera. Pensiamo invece a come formulare le do- mande in modo più efficiente: la migliore alternativa che abbiamo è fare domande che eliminano la metà delle possibilità, come ad esempio: si trova nella prima metà dell’alfabeto? Facciamo un esempio con l’alfabeto italiano: {a,b,c,d,e,f,g,h,i,l,m,n,o,p,q,r,s,t,u,v,z}. Possiamo dividere questo insieme di lettere in due {a,. . . ,l} e {m,. . . ,z} e chiedere se la lettera si trova nel primo; riceviamo uno 1, perciò dividiamo il primo insieme ancora una volta e ot- teniamo {a,. . . ,e} e {f,. . . ,l}. Adesso richiediamo se è nel primo insieme e riceviamo ancora un 1, quindi applichiamo nuovamente il solito procedimento e rimaniamo con {a,b,c} e {d,e}, ripetiamo la domanda, otteniamo ancora un 1. A questo punto siamo rimasti con tre possibili alternative, a, b e c, quindi chiediamo: è ‘a’? e riceviamo uno 0; allora chiediamo: è ‘b’? ma riceviamo un ultimo 0; adesso per esclusione sappiamo che la lettera in questione è la ‘c’, codificata nella sequenza di bit ‘11100’.
Quindi per una qualsiasi lettera dobbiamo aspettarci di chiedere minimo 4 domande e massimo 5, ogni lettera quindi contiene dai 4 ai 5 bit di infor- mazione. Più in generale otteniamo quindi che il numero di messaggi possibili sarà uguale a 2#domande che nel nostro caso dovrebbe risultare uguale a ven-
tuno, otteniamo quindi la seguente equazione 2#domande = 21 e per risolvere
questo tipo di equazioni dobbiamo ricorrere all’uso della funzione logaritmica, in quanto il logaritmo in base due di ventuno è esattamente l’esponente a cui due deve essere elevato per ottenere ventuno, ovvero 4,4. Possiamo quindi aspettarci di dover fare, di media, 4,4 domande per ogni lettera e questa for- mula ci da la possibilità di trovare facilmente il numero di bit necessari per scambiarsi un qualsiasi tipo di informazione. Questa piccola panoramica non ci deve far dimenticare come gli algoritmi di compressione dati ci permettano ad oggi di scambiarsi video e foto ad alta risoluzione, e con i nostri computer moderni sono in grado di gestire TeraByte di memoria, equivalenti a 812 bit.
Adesso però si pone un’altra questione, ovvero, fin’ora abbiamo consid- erato la scelta dei simboli come se fosse casuale e di conseguenza abbiamo calcolato l’informazione media contenuta in una lettera dell’alfabeto. Questa è stata una semplificazione fondamentale per capire il concetto che sta di- etro al bit come unità di misura, bisogna tenere presente però che la mag- gior parte delle comunicazioni, come i nostri comuni discorsi colloquiali, non sono affatto casuali, ma sono piuttosto un sottile mescolamento di sorpresa e prevedibilità. Non giochiamo mai a dadi per scrivere una lettera, quindi è proprio la struttura stessa del linguaggio e la sua prevedibilità che possono portare ad una maggior efficienza nel codificare l’informazione.
Consideriamo il seguente esperimento mentale: ci sono due macchine di Turing M1 e M2, le quali producono stringhe con un alfabeto di carat-
teri, a, b, c, d secondo delle istruzioni precise. La macchina M1 produce delle
stringhe che sono completamente casuali, ogni lettera ha un 25% di proba- bilità di occorrere nelle possibili stringhe generate; mentre la macchina M2
genera le stringhe secondo le seguenti probabilità: a=50%, b=12,5%, c=12,5, d=25%. La domanda fondamentale a questo punto diventa, quali delle due macchine tra M1 e M2 sta producendo più informazione nel suo output?
Alla luce del ragionamento che abbiamo fatto nel paragrafo precedente, possiamo capire meglio come Shannon sia stato capace di riformulare la do- manda in un modo così originale, ovvero: se dovessi predire la prossima lettera di uno dei due output prodotti dalle nostre macchine di Turing, qual è il minimo numero di domande, del tipo si o no, che posso aspettarmi di chiedere? Vediamo intanto la macchina M1, il modo migliore per fare le do-
mande rimane lo stesso che abbiamo visto prima, ovvero ridurre le possibilità in due, dimezzando le alternative; in questo modo, dopo solo due domande, abbiamo sempre la risposta corretta. Possiamo quindi dire che l’incertezza della macchina M1 è di due domande per simbolo.
Veniamo ora alla macchina più interessante, M2; anche in questo caso
potremo fare due domande, ma visto che le probabilità dei vari simboli è diversa, possiamo anche fare le nostre domande in modo diverso. Sappiamo che la probabilità più alta è quella di a con il 50%, mentre tutte le altre in- sieme arrivano al 50%. Quindi la prima domanda da fare sarà: è a? Notare che nella metà dei casi abbiamo già fatto con una sola domanda. Successi- vamente si chiederà se è d e solo in ultima istanza si chiederà se è uno degli ultimi due simboli meno probabili, b e c. A questo punto abbiamo tutti gli elementi per rispondere alla domanda iniziale: quante domande ci dobbiamo aspettare di chiedere, in media, per predire il prossimo simbolo di una delle due macchine? Basta applicare la media ponderata tra le varie probabilità di ogni simbolo Px, e il numero di domande ad esso associato Dx, così che,
(Pa× Da) + (Pb× Db) + (Pc× Dc) + (Pd× Dd). Per la macchina M1 avremo di
conseguenza (0.25×2)+(0.25×2)+(0.25×2)+(0.25×2) =2bit , mentre per la macchina M2 otteniamo (0.50×1)+(0.125×3)+(0.125×3)+(0.25×2) =
1.75bit. Vediamo quindi come sia la macchina M1 a produrre più infor-
mazione, ma questo solo perché consideriamo la macchina M2 come più
prevedibile e meno incerta dell’altra, questa misura di incertezza di un deter- minato output viene chiamata Shannon, entropia dell’informazione e l’unità di misura di questa entropia che viene scelta è quella di un lancio di testa o croce, chiamandolo bit. Riporto di seguito la famosa espressione dell’entropia di Shannon: H = N X i=1 Pi× log2 1 pi
L’entropia è quindi la sommatoria per ogni simbolo, della probabilità di quel simbolo, per il logaritmo a base due di uno sulla probabilità dello stesso simbolo, o equivalentemente, come nella formulazione originale di Shannon,
H = −
N
X
i=1
Pi× log2pi
Ricapitolando l’entropia è quindi massima quando abbiamo eventi con la stessa probabilità, quando la sorpresa del risultato è massima; ogni volta che ci si allontana dall’equiprobabilità e quindi introduciamo qualche tipo di prevedibilità, l’entropia deve per forza scendere. L’idea che sta alla base è quindi che se l’entropia diminuisce, saranno necessarie meno domande per prevedere il risultato di un determinato processo, ed è proprio grazie a Shan- non se ad oggi utilizziamo il bit come unità di misura di questa entropia o anche, più intuitivamente, della nostra sensazione di sorpresa presente in una
informazione.
Poco più di dieci anni dopo la pubblicazione dell’articolo di Shannon, negli anni sessanta, si è assistito ad un rinnovato interesse per il campo dell’informatica e della computazione che hanno portato ben al di là del concetto di entropia dell’informazione. Ray Solomonoff, Andreï Kolmogorov (1965),99 Leonid Levin, Per Martin-Löf (1966), Gregory Chaitin, Charles
Bennett100 sono stati tra i primi studiosi a contribuire in questo ambito di
ricerca,101 che affonda le sue radici nel lavoro di Turing e i successivi sviluppi
di Von Neumann.
La teoria della complessità algoritmica di Kolmogorov cerca di formal- izzare il concetto di semplicità e/o complessità: intuitivamente descrive la quantità di informazione necessaria per descrivere univocamente un oggetto digitale x.102 In questo senso una stringa è semplice se può essere descritta in
modo conciso e sintetico, e complessa se invece non esiste nessuna descrizione più breve o semplice dell’oggetto in questione. Più formalmente, diciamo che un programma p è una descrizione di una stringa x per una macchina di Turing T se T (p) = x. La lunghezza della descrizione più breve diventa quindi:
KT(x) := minp{l(p) : T (p) = x}
dove l(p) è la grandezza del programma misurata in bit.103 Questa definizione
99[Sol64], [Kol65]. 100[Cha66], [Ben88].
101Per una buona panoramica su questi temi vedi [LV09].
102Dove per oggetto digitale si intende uno che possa essere rappresentato da una stringa
binaria finita.
103Ricordiamo, per inciso, che la definizione della funzione K(∗) riportata nel testo, anche
se basata su una particolare descrizione di una macchina di Turing, rimane comunque indipendente da essa, questo risultato è quello che a oggi è conosciuto come the invariance
coglie a pieno quella differenza sostanziale che riscontriamo quando parag- oniamo la complessità di sequenze di numeri. Per esempio, consideriamo le seguenti due stringhe binarie:
i) 1010101010101010101010101010101010101010 ii) 1001011101011010100101011010101011011010
Mentre la stringa i) può essere generata molto semplicemente da un sem- plice programma ciclico, come "Print: ‘10’ , 20 volte." si richiede invece un programma più lungo per compilare la stringa ii), la quale appare effettiva- mente molto più random. In questo secondo caso, in cui non percepiamo quella ridondanza che invece è presente per la stringa i), l’unico modo per descrivere una stringa random sarebbe di enumerare ogni suo bit, e ciò im- plica che una stringa binaria finita di lunghezza s è random se la sua comp- lessità algoritmica è anch’essa pressoché uguale a s; in questo caso parliamo di una stringa che si dice algoritmicamente incomprimibile. Inoltre, vale la pena sottolineare come, in contrasto con la teoria dell’informazione classica, questa definizione ha il vantaggio di essere una misura assoluta per messag- gio, piuttosto che caratterizzare una sorgente random di numeri binari, come nel caso considerato da Shannon. Quello che ci deve colpire è che mentre KT(x) può essere sempre stimata per stringhe finite, in generale è impos-
sibile dire se una stringa di arbitraria lunghezza è random, difficoltà che è stata considerata inizialmente da Chaitin nel suo libro Algorithmic Informa- tion Theory del 1988.104 Ad esemio, mentre le rappresentazioni binarie delle
theorem. [Kol65].
cifre decimali di π (001001000011111101101...), e (1011011111100001010..) o √
2 (0110101000001001111...) potrebbero apparire tutte random, così che la loro entropia è alta, in realtà ognuna di queste stringhe può essere rappre- sentata più compattamente usando un numero qualsiasi di brevi algoritmi, il che equivale a dire che la loro complessità algoritmica è praticamente pari a zero. In conclusione, la complessità algoritmica è sicuramente una misura più accurata della grado di random di un sistema piuttosto che della sua complessità.105
Proprio per questa ragione però l’informazione algoritmica è stata con- siderata come una misura del grado di casualità o randomness, piuttosto che di complessità, ecco che Bennett, seguendo questa linea di ragionamento ha presentato la sua innovativa definizione di complessità, la logical depth o profondità logica.106 Senza dover entrate troppo nei tecnicismi di questa
definizione, quello che ci interessa di questa misura delle complessità è che essa è dinamica, infatti, ciò che essa cerca di cogliere è il numero più plau- sibile di operazioni computazionali nella storia causale di un oggetto. Per chiarezza espositiva riporto di seguito la definizione formale di profondità logica come il tempo di esecuzione richiesto da una macchina di Turing uni- versale U per generare un oggetto O, compilando il programma più efficiente P∗ che lo possa produrre:
DU(O) = TU(P∗)
105Vedi [Ila01], pp. 624 - 626. 106[Ben88].
in cui
U (P∗) = S(O)
dove S(O) è la rappresentazione in bit dell’oggetto O e TU(P∗) è il tempo
richiesto da U per compilare il programma P∗.107 Secondo la definizione
sopra riportata sia stringhe altamente ordinate che quelle completamente random sono superficiali, o non profonde, dato che possono essere entrambe computate con programmi brevi della forma <print x >. Al contrario però, un numero come π, che abbiamo visto avere complessità algoritmica minima, considerato lo sforzo computazionale richiesto per generare n decimali anche da un semplice algoritmo, risulta essere sicuramente più profondo di molti altri numeri di pari cifre decimali. Inoltre, un’altra caratteristica della pro- fondità logica è che esse obbedisce alla slow-growth law, ovvero la legge della cresita lenta, la quale suggerisce come oggetti profondi non possono essere prodotti velocemente a partire da altri più superficiali. Possiamo dire che, tra quelle sopra menzionate, la definizione di Bennett è quella che più si avvicina alla nostra comprensione intuitiva della complessità. Ad esempio, un organ- ismo biologico è complesso proprio in virtù richiede una lunga e complicata computazione per descriverlo. Mentre, all’opposto, un cristallo strutturato regolarmente è superficiale perché può essere descritto da un breve algoritmo; allo stesso modo se si pensa al comportamento di un gas, che continua ad essere in accordo con la nostra intuizione: un gas è certamente un sistema complesso, ma gli manca organizzazione e conseguentemente ha poca comp- lessità innata.
107Allo stesso modo, per la capacità delle macchine universali di simularsi a vicenda,
A conclusione di questa, inevitabilmente limitata, presentazione teorica dei sistemi complessi, andremo a vedere nel dettaglio uno degli esempi dei modelli matematici più semplici i quali riescono a catturare qualcosa di fon- damentale per ciò che intuitivamente consideriamo emergente, complesso ed irriducibile: i Cellualar Automata.108 Nella prossima sezione verrà fornita
una presentazione esaustiva di questi modelli generali, insieme a due es- empi concreti di tipologie di CA differenti. Attraverso l’analisi di questi modelli vedremo come gran parte della discussione sull’emergentismo e sulla computabilità trovi un’importante connessione con la fisica e con la nostra percezione dei processi che compongono la realtà.