Complessità di Kolmogorov

Nella teoria algoritmica dell'informazione, la complessità di Kolmogorov (dal nome del matematico russo A. N. Kolmogorov) di un oggetto (assumendo che possa essere rappresentato come una sequenza di bit, per esempio un pezzo di testo), è la lunghezza del più breve programma informatico (in un dato linguaggio di programmazione) che produca l'oggetto come output. Una definizione alternativa è: la quantità di informazione contenuta in una data sequenza x espressa come la lunghezza del più breve programma che stampa x e si arresta.^[1]

Concetto generale

Supponiamo sia data una stringa come 111111 ... che vada avanti cento volte nello stesso modo, la lunghezza della stringa sarebbe di 100 caratteri ma si può scrivere un breve programma che lo genera molto facilmente:

repeat 100   print "1"  end repeat

Si consideri ora la stringa "231048322087232 .." e così via per cento cifre. La si supponga essere una stringa casuale, allora sarebbe difficile creare un programma più corto della stringa stessa in grado di stamparla. In altre parole, non c'è modo di specificare questa stringa dall'aspetto casuale se non citandola cifra per cifra. Questa osservazione della differenza tra queste due stringhe è ciò che conduce all'idea della complessità di Kolmogorov. La prima stringa può essere generata da un programma con circa 30 caratteri, e quindi si può dire che ha 30 byte di informazione, ma la seconda stringa richiede un programma di almeno cento caratteri per citare tutte le cifre come un letterali e così ha informazione da 100 byte.^[2] Chiaramente il numero di byte necessari per un programma che ne stampa cento non è un numero ben definito, dipende dal linguaggio di programmazione che si usa. Tuttavia, in qualsiasi linguaggio di programmazione possiamo definire la complessità di Kolomogorov come la lunghezza del programma più piccolo che genera la stringa in questione. Quindi la complessità è definita rispetto a un determinato linguaggio di descrizione. Per le stringhe infinite le cose sono un po' più interessanti perché, se non si dispone di un programma che genererà la stringa, in pratica non si ha la stringa in alcun senso pratico. Cioè, senza un programma che genera le cifre di una sequenza infinita non si può effettivamente definire la stringa.

Note

^ Nicolò Cesa-Bianchi, Teoria dell’Informazione e della Trasmissione - Complessità di Kolmogorov (PDF), su cesa-bianchi.di.unimi.it, 1º maggio 2016 (archiviato dall'url originale il 24 marzo 2018).
^ (EN) Mike James, Kolmogorov Complexity, su i-programmer.info, 2 settembre 2013 (archiviato dall'url originale il 21 giugno 2018).