La complessità di Kolmogorov

Quando lo usiamo, il nostro smartphone scambia una quantità enorme di dati sia al suo interno, per esempio fra processore, schermo o memoria, sia con l’esterno (per esempio con le cuffie bluetooth, con la connessione wireless ecc). Questa mole di informazioni è codificata in segnali digitali, vale a dire lunghissime successioni di bit, cioè di 0 e 1: sappiamo infatti che i dispositivi elettronici riescono a rappresentare e memorizzare egregiamente una cifra binaria (bit è la crasi di binary digit) tramite due distinti potenziali elettrici nei loro circuiti. La trasmissione di questi segnali è continua e incessante, anche se non ce ne accorgiamo, e avviene miliardi di volte al secondo all’interno del dispositivo e milioni di volte al secondo nel caso di comunicazioni esterne. In particolare, le trasmissioni a distanza richiedono più tempo e sono maggiormente soggette a errori. Per renderle affidabili, il segnale viene “ridondato”, cioè ripetuto un certo numero di volte, seguendo i dettami della teoria dell’informazione che Claude Shannon e Norbert Wiener crearono negli anni ’40 del XX secolo, qualche anno prima che i computer fossero inventati e qualche decennio prima che i computer potessero comunicare a distanza. Questa ridondanza rende la trasmissione di informazioni onerosa, in particolare se dobbiamo trasmettere enormi moli di informazioni come ormai siamo abituati a fare: per esempio, scaricare un video comporta la trasmissione di decine o centinaia di miliardi di bit. Fin dagli esordi della comunicazione a distanza ci si è quindi posti il problema di comprimere i segnali in modo da preservare l’informazione in essi contenuta o perderne una quota che si decide sia trascurabile, trasformandoli in una sequenza più corta dell’originale. Una tecnica che, per fare un esempio, usiamo tutti è quella di “zippare” un file. Il file “zippato” non è più leggibile a schermo perché contiene una codifica diversa della stessa informazione del file originale. Comprimere i file in questo modo ne preserva completamente l’informazione ma ne ha più che dimezzato la dimensione e quindi anche il tempo di trasmissione, se volessimo inviarlo su Internet o via bluetooth. Di più, ci ha fatto risparmiare spazio sul disco. Al di là del fatto che gli algoritmi di compressione sono un argomento matematicamente molto interessante, quel che ci preme qui sottolineare è un’altra cosa e cioè che i dati e le informazioni nella loro “forma originaria” non si presentano mai in una codifica “ottimizzata” ma possiedono delle ridondanze che è possibile eliminare per comprimere il dato ai soli bit che sono necessari a ricostruirlo. La teoria matematica che sta alla base di tutto questo è non solo utile ma anche molto elegante e correlata ai fondamenti dell’informatica e della matematica computazionale. Si tratta della teoria algoritmica dell’informazione fondata dal grande matematico sovietico Andrej Nikolaevic Kolmogorov (1903-1987). Per capire la sua idea, pensiamo a un esempio banale. Supponiamo di dover trasmettere, per qualche motivo, un messaggio costituito da un milione di 0 e 1 alternati: 01010101… Un modo semplice per comprimere questo messaggio ultra-ridondante è di convenire, con chi lo riceve, di scambiarsi il numero di ripetizioni e la sequenza da ripetere, nel nostro caso il numero 500.000 e la sequenza 01. A quel punto chi riceve questa codifica è in grado di ricostruire il messaggio originale. Quindi, inviare un messaggio cifrato equivale a disporre di uno strumento per cifrarlo e di uno strumento per decifrarlo: se ai tempi della seconda guerra mondiale si usavano macchine fisiche, come la celebre Enigma usata dai nazisti, oggi si usa il software, cioè programmi per computer. Il ragionamento di Kolmogorov, detto in termini moderni e un po’ semplificati, muove dall’osservare che in qualsiasi linguaggio di programmazione è possibile scrivere, con poche istruzioni, un programma che generi un milione di 0 e 1 alternati. Quindi, invece di inviare la sequenza, potremmo inviare il programma che la genera e chi lo riceve lo eseguirà ottenendo la sequenza desiderata. Inoltre, il programma è comunque codificato in un file, quindi in una sequenza di bit: per esempio, un programma per generare la sequenza in questione nel linguaggio Python, molto usato per l’intelligenza artificiale, è: print(“01”*500000). Non è importante per chi legge capire il programma. Basta sapere che il programma consta di una sequenza di simboli (che gli informatici chiamano caratteri), in questo caso 18: quando viene memorizzato nel computer occupa quindi 18 byte che corrispondono a 94 bit. Si tratta di quattro ordini di grandezza in meno della sequenza di bit che il programma genera! Poiché un programma è una sequenza finita di caratteri, dato un output (cioè un risultato) generabile da un programma, esiste sempre un programma di lunghezza minima che genera lo stesso identico output: probabilmente nel nostro caso il programma riportato è quello di lunghezza minima ma l’importante è convincerci che ne esista uno (non necessariamente unico: programmi diversi possono produrre il medesimo output e avere la stessa lunghezza!). Abbiamo ora gli elementi per definire la complessità di Kolmogorov o complessità algoritmica di una sequenza di bit: è la lunghezza del più piccolo programma che la generi, espressa ancora in bit. Dunque, nel nostro caso, la complessità della sequenza di un milione di zeri e uno è 94: ovviamente questo valore dipende dal linguaggio usato ma nella teoria supponiamo di averne fissato uno, una volta per tutte. Kolmogorov ha definito questa grandezza la complessità di una sequenza, per dare una definizione astratta di “casualità”. In effetti, la sequenza di un milione di zeri e uno sembra tutto meno che casuale. Consideriamo invece la sequenza di cifre (decimali e non binarie ma il principio è lo stesso):141592653589793238462643383279. È difficile scoprire al suo interno una regolarità che consenta di generarla con un programma semplice come quello che abbiamo visto prima. Ma esiste sempre un programma per generare una sequenza di numeri: basta mettere una dopo l’altra singole istruzioni che stampino la sequenza. Per esempio, in Python potremmo scrivere print(“1 4 15926535897932384626433832 7 9”) che funziona anche se è un programma la cui lunghezza è dello stesso ordine di grandezza del dato che vuole produrre. Per Kolmogorov una sequenza numerica è casuale quando la sua complessità (cioè la lunghezza in bit del minimo programma necessario a generarla) è dello stesso ordine di grandezza della lunghezza in bit della sequenza che vuole generare. In altri termini: una sequenza è casuale se è incomprimibile! Comprimerla equivale a scrivere un programma che la codifichi e trasmettere il programma invece della sequenza: se questo programma non è molto più breve della sequenza stessa, tanto vale trasmettere quest’ultima. Chi ha accesso a un computer potrebbe fare questo esperimento: prendere un file che contiene un milione di caratteri tutti uguali, diciamo una “A”, e un file che contiene un milione di caratteri generati a caso. Entrambi i file non “zippati” pesano 997Kb: dopo aver zippato il primo, quello con la sequenza non casuale, il file codificato contiene 1Kb mentre il secondo file, quello con le lettere casuali, se compresso, contiene 712Kb: meno ma nello stesso ordine di grandezza del file non compresso. Quindi, meno una sequenza è casuale e più è facile comprimerla. Questo intuitivamente dovrebbe essere ovvio in quanto se una sequenza presenta simmetrie, regolarità, pattern come dicono quelli bravi, allora queste possono essere codificate in un programma che le genera. Invece, un programma per generare una sequenza veramente casuale non può far altro che stampare tutti i valori della sequenza e quindi non sarà mai più breve della sequenza stessa, perché in qualche modo la deve contenere esplicitamente. Un’altra interessante conseguenza di questa elegante teoria che collega informazione, algoritmi (programmi Python nel nostro caso) e compressione dei dati è che comprimere una sequenza di dati vuol dire eliminarne in qualche modo le ridondanze, le informazioni superflue: l’unica informazione che c’è da sapere nella sequenza di un milione di lettere “A” è stata appena espressa nella frase che definisce la sequenza, mentre l’informazione di una sequenza casuale è data per forza dalla sequenza di tutti gli elementi, nell’ordine, della sequenza. In altri termini, una sequenza casuale non è descrivibile se non tramite l’enumerazione di tutti i suoi elementi, laddove una sequenza che non lo sia è riassumibile con una sua descrizione più sintetica. Esistono molti campi di applicazione nei quali si ha a che fare con sequenze che possono essere compresse “strizzando” in un certo senso l’informazione inutile come si strizza l’acqua da un panno che vogliamo mettere ad asciugare dopo la lavatrice. Un primo notevole esempio è il nostro Dna, che è una molecola molto complessa ma che è possibile rappresentare come una sequenza di lettere A, C, G, T che corrispondono ai possibili nucleotidi, cioè i mattoni molecolari con i quali il Dna è costruito. Una sequenza di Dna è quindi una sequenza di 4 possibili simboli. La sequenza completa del genoma umano consta di circa 3,2 miliardi di nucleotidi e ciascuno si può rappresentare con due cifre binarie (diciamo 00 = A, 01 = C, 10 = G e 11 = T) per un totale di 3.200.000.000 × 2 = 6.400.000.000 bit, meno di 1Gb di memoria di un nostro smartphone! Molte sequenze del nostro Dna non sembrano assolvere allo scopo cui la molecola è deputata, cioè codificare le caratteristiche e i processi biologici dell’individuo che la possiede; questo Dna “spazzatura” ha altri scopi, come consentire alla molecola di raggomitolarsi all’interno del nucleo cellulare. Quindi, la nostra sequenza di 6,4 miliardi di bit contiene molta informazione ridondante e potrebbe essere compressa senza perdita di informazioni essenziali. È quel che fanno alcuni studiosi di genoma e la cosa sorprendente è che, comprimendo le sequenze del Dna, è possibile anche confrontarle meglio e persino usarle per dire se corrispondano o meno a un dato genoma. Per esempio, confrontando sequenze compresse di Dna, è stato possibile capire come certi geni attivino alcune proteine. Inoltre, data la natura particolare dell’alfabeto del Dna, è stato possibile creare degli algoritmi di compressione ad hoc che consentono, una volta compresse le sequenze geniche, di raggrupparle in cluster, una tecnica che tradizionalmente richiederebbe algoritmi di machine learning. In effetti, comprimendo i dati e confrontando le sequenze compresse con semplici criteri numerici, è possibile classificare non solo il Dna ma anche testi, immagini e video ottenendo risultati simili a quelli ottenuti impiegando sofisticati algoritmi di intelligenza artificiale: come se comprimere un dato consenta anche di comprenderlo meglio. Ma d’altra parte non è questo il motivo per cui a scuola ci facevano fare “il riassunto” di un testo? La capacità di cogliere gli aspetti essenziali di un testo è a pieno titolo identificabile con la capacità di comprendere il testo stesso e non a caso uno dei banchi di prova dell’intelligenza artificiale è proprio la capacità di fornire sintesi di testi scritti. “Comprimere” e “comprendere” sono parole non solo vicine ortograficamente, perché differiscono per poche lettere, ma anche per il significato profondo che le attività che denotano possono assumere.