Compressione e complessità algoritmica

L’informazione di una sorgente probabilistica è l’entropia. Ma quanta informazione c’è in un singolo oggetto, una stringa concreta presa da sola? La risposta — la lunghezza del programma più corto che la genera — è una nozione bellissima e profondamente teorica: definisce il limite ultimo della compressione, formalizza il rasoio di Occam, e non si può calcolare.

Perché questo capitolo

Due stringhe di mille bit. La prima è “01” ripetuto cinquecento volte. La seconda è il risultato di mille lanci di una moneta equa, scritti uno dopo l’altro. Hanno la stessa lunghezza. Se le immagini estratte da una sorgente che emette ogni sequenza di mille bit con uguale probabilità, hanno anche la stessa probabilità, identica: $2^{-1000}$ . Per la teoria di Shannon, da quel punto di vista, sono equivalenti.

Eppure qualcosa stride. La prima la puoi dettare al telefono in tre secondi: “zero-uno, cinquecento volte”, e l’altra persona la ricostruisce senza errori. La seconda devi leggerla bit per bit, per intero, perché non c’è scorciatoia: ogni cifra è una sorpresa indipendente, e saltarne una significa perderla.

La prima contiene meno informazione, in un senso che l’entropia di Shannon — fatta su misura per le sorgenti probabilistiche, non per i singoli oggetti — non riesce a esprimere. Serve un’altra misura, e questo capitolo è dedicato a quella.

Questo capitolo riguarda la nozione che cattura quella differenza: la complessità di Kolmogorov, l’informazione di un singolo oggetto misurata come la lunghezza del programma più corto che lo produce. È un’idea che sposta la teoria dell’informazione dalla statistica all’informatica, fissa il limite teorico assoluto di ogni possibile compressore, e dà la definizione più pulita che esista del rasoio di Occam.

È anche, per un avvertimento da mettere subito in chiaro, una nozione che non si può calcolare, e che al deep learning di oggi serve come bussola concettuale, non come motore. Nessuna loss la minimizza, nessun optimizer la insegue direttamente.

Il valore del capitolo sta proprio nel tenere distinte queste due cose: cosa è profondo e dimostrato — e qui c’è una catena di teoremi notevoli — e cosa è suggestivo ma ancora una scommessa, come l’idea che comprimere bene equivalga a essere intelligenti. Confondere le due classi è l’errore che rende l’argomento un magnete per l’hype; separarle è quello che lo rende utile.

Contesto

Questo capitolo siede nella Parte XIII, subito dopo Minimum Description Length, e ne è il completamento teorico. MDL mostrava come scegliere un modello minimizzando una lunghezza di descrizione in due parti, all’interno di una classe di modelli fissata e calcolabile.

La complessità di Kolmogorov toglie quel recinto e pone la domanda nella sua forma più estrema: cosa succede se la classe di modelli sono tutti i programmi possibili? La risposta è la nozione più generale immaginabile di “descrizione più corta” — e il prezzo della generalità totale è l’incomputabilità. È il rovescio della medaglia: MDL rinuncia alla generalità per essere calcolabile, Kolmogorov rinuncia alla calcolabilità per essere generale.

Il punto di partenza resta l’entropia di Shannon, l’informazione misurata come sorpresa media di una sorgente probabilistica. Shannon chiede: data una sorgente che emette simboli secondo una distribuzione, quanti bit in media servono per simbolo?

Kolmogorov pone una domanda diversa, quasi ortogonale: quanta informazione c’è in un singolo oggetto, preso da solo, senza alcuna sorgente che lo abbia prodotto? È un cambio di registro che vale la pena tenere a mente per tutto il capitolo, perché la confusione tra le due nozioni — informazione della sorgente contro informazione dell’oggetto — è il fraintendimento più comune dell’intera area.

L’idea fu trovata tre volte, indipendentemente, a metà degli anni Sessanta, da tre persone che arrivavano da tre domande diverse. È uno di quei casi in cui un’idea matura “nell’aria” e viene colta in parallelo da menti che non si parlano.

Ray Solomonoff (1926-2009, matematico americano, pioniere dell’AI presente già al workshop di Dartmouth del 1956 che fondò il campo) ci arriva tra il 1960 e il 1964 partendo dall’induzione: come dovrebbe un agente ideale prevedere il futuro a partire dai dati visti? La sua risposta, nel paper A Formal Theory of Inductive Inference (Information and Control, 1964), introduce la probabilità algoritmica come sottoprodotto di una teoria della previsione.

Andrey Kolmogorov (1903-1987, il più influente matematico sovietico del Novecento, l’uomo che nel 1933 aveva dato alla teoria della probabilità la sua assiomatizzazione moderna) ci arriva nel 1965 da una domanda sulla casualità: cosa rende casuale una singola stringa, se la probabilità non basta a dirlo?

C’è un’ironia in questo. Lo stesso uomo che aveva fondato la teoria assiomatica della probabilità si rese conto che quella teoria non poteva dire se una singola sequenza fosse casuale — la probabilità parla di distribuzioni e di eventi, non di esiti individuali presi uno per uno.

Il suo Three Approaches to the Quantitative Definition of Information (Problems of Information Transmission, 1965) dà alla nozione il nome con cui la conosciamo, attaccando il problema dal lato del calcolo invece che da quello della probabilità. La casualità del singolo oggetto, irraggiungibile per la probabilità, diventa accessibile attraverso i programmi.

Gregory Chaitin (n. 1947, matematico americano-argentino) ci arriva da adolescente, indipendentemente dagli altri due, e ne sviluppa le conseguenze logiche più vertiginose: una nuova forma del teorema di incompletezza e il numero $\Omega$ .

Leonid Levin (allievo di Kolmogorov a Mosca, poi emigrato negli Stati Uniti) aggiunge la versione tecnica con i codici prefisso, che rende la teoria pulita e permette di collegarla alla probabilità. Quattro nomi, tre domande diverse, una sola idea convergente: misurare l’informazione di un oggetto come la lunghezza del programma più corto che lo genera.

L’intuizione

Prima di qualsiasi formula, due modi di guardare la stessa idea. Il primo parte dalla descrizione: quanto in breve posso dire come fabbricare un oggetto. Il secondo parte dalla casualità: cosa significa, davvero, che una stringa è casuale.

Portano allo stesso posto da direzioni opposte, e capire perché coincidono è già metà del capitolo.

Angolo 1: la lunghezza della ricetta

Immagina di dover dettare una stringa a qualcuno al telefono, ma con una regola: non sei obbligato a leggere i bit uno per uno, puoi anche dare istruzioni su come ricostruirli. L’altra persona ha un computer e farà esattamente quello che le dici.

Per la stringa “01 ripetuto cinquecento volte” detti una ricetta cortissima: “scrivi 01, cinquecento volte”. Otto parole, indipendentemente da quanto è lunga la stringa: se fossero diecimila ripetizioni invece di cinquecento, cambierebbe solo il numero.

Per i primi mille bit dell’espansione binaria di $\pi$ detti una ricetta un po’ più lunga ma ancora corta: “calcola $\pi$ con questa formula e stampane i primi mille bit”. La formula è fissa, il “mille” è l’unica parte che cresce.

Per mille bit casuali di moneta non hai scampo. Nessuna ricetta è più corta del leggere tutti i bit a uno a uno, perché non c’è nessuna struttura da sfruttare. Devi dire “scrivi: zero, uno, uno, zero, …”, per mille volte: la ricetta è lunga quanto la stringa.

La complessità di Kolmogorov di una stringa è la lunghezza della ricetta più corta. Una stringa è semplice se ha una ricetta corta; complessa (o casuale) se la sua ricetta più corta è essenzialmente “scrivi questi bit esatti”, cioè lunga quanto la stringa stessa. La complessità non misura la lunghezza dell’oggetto, ma quanta struttura comprimibile contiene.

C’è un dettaglio che salva l’intuizione dall’ambiguità. “Ricetta più corta” rispetto a quale linguaggio? Una ricetta in italiano, in Python, in C, in assembly? Il sospetto legittimo è che la risposta dipenda dal linguaggio scelto, e che quindi la nozione sia arbitraria, soggettiva.

Vedremo tra poco — è il teorema di invarianza — che la dipendenza dal linguaggio si riduce a una costante fissa, irrilevante per oggetti grandi. La ricetta più corta in Python e quella in C differiscono al massimo per la lunghezza di un traduttore tra i due, scritto una volta sola. Cambiare linguaggio è come cambiare unità di misura: sposta il valore di una costante, non ne stravolge la sostanza.

Angolo 2: cosa vuol dire che una stringa è casuale

Capovolgiamo. Cosa rende casuale una stringa? La prima risposta che viene in mente è statistica: una stringa è casuale se passa i test, se ha tanti zeri quanti uni, se le coppie e le terne sono bilanciate, se non emergono pattern di frequenza.

Non basta. L’espansione binaria di $\pi$ passa tutti questi test: le sue cifre sembrano perfettamente casuali a qualunque analisi di frequenza, e infatti $\pi$ è uno dei candidati storici a “numero normale”. Eppure $\pi$ è prodotto da una formula corta. C’è qualcosa di profondamente non casuale in $\pi$ che i test statistici, per quanto raffinati, non vedono.

Kolmogorov dà la risposta esatta: una stringa è casuale se è incomprimibile, cioè se non esiste nessuna ricetta più corta della stringa stessa. La casualità non è una proprietà statistica, è una proprietà descrittiva.

Una stringa è casuale quando non c’è modo di dirla più in breve di quanto sia. $\pi$ non è casuale in questo senso, perché la formula è una ricetta corta. Una sequenza di lanci di moneta lo è, perché non ha ricetta corta: l’unico modo di dirla è elencarla.

Questo è un capovolgimento profondo. La casualità, che sembrava appartenere al regno della probabilità e del caso, diventa una questione di lunghezza di programmi — un fatto sul calcolo, deterministico.

Si misura una proprietà del singolo oggetto, non della sorgente che lo ha prodotto. Una stringa è casuale o no per quello che è, non per come è stata generata: due stringhe identiche hanno la stessa complessità, anche se una viene da una moneta e l’altra da un calcolo.

E qui arriva la sorpresa contro-intuitiva che regge metà del capitolo: rispetto a questa definizione, quasi tutte le stringhe sono casuali. Le stringhe con una ricetta corta sono un’eccezione rarissima.

Le sequenze ordinate, comprimibili, strutturate — quelle che ci capita di incontrare nel mondo, perché testi e immagini e codice sono pieni di struttura — sono una minuscola minoranza in mezzo a un oceano di stringhe incomprimibili. Il mondo che vediamo è anomalo: è fatto quasi solo di oggetti comprimibili, mentre la stragrande maggioranza degli oggetti possibili non lo è. Lo dimostreremo, con un conteggio, nella sezione sulla meccanica.

La meccanica

Adesso il formalismo, costruito per pezzi. Si parte dalla definizione, poi il teorema che la rende ben posta nonostante la dipendenza dal linguaggio, poi la prova che non si può calcolare.

Da lì le conseguenze più profonde si srotolano una dopo l’altra: la casualità della maggioranza delle stringhe, l’incompletezza di Chaitin, il numero $\Omega$ , e infine il prior universale di Solomonoff che chiude il cerchio tornando all’induzione da cui tutto era partito.

La definizione

Fissiamo una macchina di Turing universale $U$ — un modello matematico di computer general-purpose, capace di eseguire qualunque programma, esattamente come un linguaggio di programmazione completo (Python, C, qualunque cosa Turing-completa). È il nostro interprete di riferimento.

La complessità di Kolmogorov $K(x)$ di una stringa $x$ è la lunghezza, in bit, del programma più corto che fa stampare $x$ a $U$ e poi termina:

$K_U(x) = \min \{\, |p| : U(p) = x \,\}$

In parole povere: tra tutti i programmi $p$ che, dati in pasto alla macchina $U$ , producono in output esattamente $x$ e si fermano, prendi il più corto; la sua lunghezza è $K(x)$ . Il simbolo $|p|$ è la lunghezza del programma in bit.

Un primo fatto immediato fissa un tetto: per ogni stringa $x$ vale $K(x) \le |x| + c$ . C’è sempre la ricetta banale “stampa esattamente questi bit”, lunga quanto $x$ più una costante $c$ per il comando di stampa. Nessuna stringa è mai più complessa di sé stessa, più un pizzico di overhead.

Le stringhe interessanti sono quelle per cui $K(x)$ è molto minore di $|x|$ : hanno una ricetta che le batte, una struttura che permette di dirle in meno spazio di quanto occupino. La differenza $|x| - K(x)$ misura quanta ridondanza la stringa nasconde.

Una raffinatezza tecnica, che vale la pena citare e poi mettere da parte. La versione moderna (dovuta a Levin e Chaitin) richiede che i programmi validi formino un codice prefisso, cioè che nessun programma valido sia l’inizio di un altro — la stessa proprietà dei codici prefisso vista in Minimum Description Length.

Questo rende la teoria più pulita e permette di definire bene la probabilità universale di cui si parlerà alla fine del capitolo. La distinzione tra complessità “plain” e “prefix-free” cambia $K$ solo di un termine logaritmico, e non è essenziale per l’intuizione; nel resto del capitolo si scrive $K(x)$ senza preoccuparsene.

Il teorema di invarianza

L’obiezione naturale: $K$ dipende dalla macchina $U$ , quindi dal linguaggio. Cambio linguaggio, cambia il programma più corto, cambia $K$ . La nozione sembra arbitraria.

Il teorema di invarianza (provato indipendentemente da Solomonoff nel 1964, Kolmogorov nel 1965 e Chaitin nel 1969) la salva. L’enunciato: se $K_1$ e $K_2$ sono le complessità rispetto a due linguaggi Turing-completi $L_1$ e $L_2$ , esiste una costante $c$ — che dipende solo dalla coppia di linguaggi, non dalla stringa — tale che per ogni $s$ :

$-c \le K_1(s) - K_2(s) \le c$

In parole povere: le due misure di complessità coincidono a meno di una costante fissa, la stessa per tutte le stringhe.

La prova è un ragionamento da programmatore. Posso scrivere, una volta per tutte, un interprete di $L_2$ scritto in $L_1$ : un programma che prende un programma $L_2$ e lo esegue. Quell’interprete ha una lunghezza fissa, chiamiamola $c$ .

Allora, dato qualunque programma in $L_2$ che produce $s$ , posso ottenere un programma in $L_1$ che produce lo stesso $s$ : basta prefissargli l’interprete. Costo: la lunghezza del programma $L_2$ più $c$ . Quindi $K_1(s) \le K_2(s) + c$ .

Per simmetria, scrivendo un interprete di $L_1$ in $L_2$ , vale anche la disuguaglianza opposta, e insieme danno l’enunciato. La costante $c$ è, letteralmente, la dimensione di un compilatore — un oggetto finito, scritto una volta sola, che non cresce con le stringhe da descrivere.

Questa è una relazione formalmente provabile, dunque un teorema nel senso pieno della parola, non un’analogia o una regolarità empirica. La conseguenza pratica: per stringhe lunghe la scelta del linguaggio diventa trascurabile, e ha senso parlare di " $K(x)$ " senza specificare la macchina. La costante c’è, ma non scala con l’oggetto.

Perché non si può calcolare

Ed ecco il fatto più sorprendente e più importante di tutto il capitolo. $K$ non è una funzione calcolabile: non esiste, e non può esistere, un programma che, data una stringa $x$ qualunque, restituisca $K(x)$ .

Non è una limitazione tecnica da superare con più potenza di calcolo o un algoritmo più astuto. È un’impossibilità di principio, dimostrabile, dello stesso tipo dell’impossibilità di decidere se un programma arbitrario si ferma.

La prova passa per un paradosso vecchio di un secolo. Il paradosso di Berry (attribuito a G. G. Berry, bibliotecario di Oxford, e riportato da Bertrand Russell nel 1908) considera l’espressione: “il più piccolo intero positivo non definibile in meno di dodici parole”. Quell’espressione ha undici parole, e definisce un intero — proprio quello che dovrebbe essere indefinibile in meno di dodici. Contraddizione.

Per un secolo questo è rimasto un divertissement logico, una curiosità da manuale di paradossi. Chaitin lo trasforma in un teorema usando $K$ , dandogli per la prima volta conseguenze matematiche serie.

Supponiamo per assurdo che esista una funzione calcolabile K(s) che, data una stringa, ne restituisce la complessità di Kolmogorov. Allora possiamo scrivere questo programma:

GeneraStringaComplessa(N):
    per ogni stringa s, in ordine di lunghezza crescente:
        se K(s) >= N:
            return s

Questo programma cerca la prima stringa la cui complessità è almeno $N$ , un numero enorme che fissiamo noi (diciamo otto miliardi). Ora contiamo la lunghezza di GeneraStringaComplessa stesso: è il codice della funzione K (lunghezza fissa, chiamiamola $L_K$ ), più un piccolo wrapper che contiene il numero $N$ (circa $\log_2 N$ bit) e il loop. Chiamiamo $L$ questa lunghezza totale.

Se scegliamo $N > L$ , scatta la contraddizione. Il programma produce una stringa $s$ con $K(s) \ge N$ . Ma quel programma è una descrizione di $s$ , lunga solo $L$ bit. Quindi $K(s) \le L < N$ . Abbiamo $K(s) \ge N$ e $K(s) < N$ contemporaneamente: assurdo. La funzione calcolabile K non può esistere.

L’intuizione, spogliata della matematica: “la prima stringa che non si può descrivere in meno di $N$ bit” è essa stessa una descrizione corta di quella stringa — se potessimo calcolare $K$ .

La capacità di calcolare $K$ produrrebbe descrizioni corte degli oggetti incomprimibili, contraddicendo la loro stessa incomprimibilità. È il paradosso di Berry reso esecutivo: l’autoreferenza che nel paradosso è un gioco di parole qui diventa un programma che si morde la coda.

Il legame con il problema dell’arresto

C’è un secondo modo di vedere l’incomputabilità, che la collega al risultato più famoso della teoria della calcolabilità. Il problema dell’arresto (Alan Turing, 1936): non esiste algoritmo che, dato un programma arbitrario, decida se quel programma terminerà o girerà per sempre.

Calcolare $K(x)$ è altrettanto impossibile, e per la stessa ragione. Per trovare il programma più corto che produce $x$ , dovremmo provare tutti i programmi più corti di $|x|$ , eseguirli, e vedere quale stampa $x$ .

Ma “eseguirli e vedere se si fermano” è proprio ciò che il problema dell’arresto rende impossibile. Un programma corto candidato potrebbe non essersi ancora fermato, e non possiamo sapere se si fermerà più tardi con l’output giusto, o se girerà per sempre. Aspettare non è una strategia: non c’è un momento in cui possiamo concludere “non si fermerà mai”.

Questo lascia a $K$ uno status preciso: è semicalcolabile dall’alto (in inglese, upper-semicomputable). Possiamo trovare descrizioni sempre più corte facendo girare i programmi in parallelo — la tecnica del dovetailing: un passo del primo, poi un passo dei primi due, poi dei primi tre, intrecciando le esecuzioni — e aggiornando la migliore descrizione trovata finora.

Ma non sapremo mai di aver trovato la più corta, perché un programma ancora più corto potrebbe fermarsi con l’output giusto in un momento futuro che non possiamo prevedere. La nostra stima può solo scendere, mai dichiararsi definitiva. Sappiamo stimare $K$ per eccesso, mai stabilirla con certezza — ed è esattamente questa asimmetria che la rende incalcolabile.

Quasi tutto è incomprimibile

Torniamo alla sorpresa annunciata nell’intuizione — quasi tutte le stringhe sono incomprimibili — e dimostriamola. La prova è un argomento di conteggio elementare, accessibile a chiunque sappia contare le potenze di due, ma decisivo: stabilisce un fatto strutturale sull’intero universo delle stringhe.

Quante sono le stringhe di lunghezza esatta $n$ ? Sono $2^n$ . Quante sono le possibili descrizioni più corte di $n - c$ bit? Le stringhe di lunghezza $0, 1, 2, \dots, n-c-1$ sono in totale $2^{n-c} - 1$ , cioè meno di $2^{n-c}$ .

Una funzione non può associare $2^n$ oggetti a meno di $2^{n-c}$ descrizioni distinte senza che due oggetti finiscano sulla stessa descrizione: è il principio dei cassetti (pigeonhole), lo stesso che dice che se hai più piccioni che caselle, almeno due piccioni condividono una casella.

Ma in compressione due oggetti diversi non possono avere la stessa descrizione, altrimenti la decompressione sarebbe ambigua: scompattando, non sapresti quale dei due ricostruire. Quindi le descrizioni corte non bastano per tutte le stringhe.

Conseguenza: la frazione di stringhe di lunghezza $n$ che si possono comprimere di almeno $c$ bit è minore di $2^{-c}$ . Detto in positivo, la probabilità che una stringa casuale sia incomprimibile di almeno $c$ bit è almeno $1 - 2^{-c+1} + 2^{-n}$ .

Per $c = 10$ , oltre il 99,9% delle stringhe di lunghezza $n$ non si comprime di più di dieci bit. Per $c = 20$ , la frazione comprimibile scende sotto un milionesimo.

La maggioranza schiacciante delle stringhe è incomprimibile, e lo è in modo sempre più netto man mano che si alza l’asticella. Comprimere è possibile solo per gli oggetti eccezionalmente strutturati — che per nostra fortuna sono proprio quelli che produciamo e che vogliamo memorizzare.

Questo è esattamente lo stesso fatto, visto da un’angolazione più profonda, del “non esiste un compressore che comprime tutto” discusso in Minimum Description Length. Lì lo si dimostrava dal lato dei compressori (uno che accorcia alcuni file deve allungarne altri); qui dal lato degli oggetti (la maggior parte non ha descrizione corta). Sono due facce dello stesso conteggio.

La compressione funziona nel mondo reale non perché esista un algoritmo magico, ma perché gli oggetti reali — testi, codice, immagini, audio — abitano la minuscola isola comprimibile, non l’oceano incomprimibile. La struttura del mondo è ciò che rende possibile la compressione; su dati davvero casuali nessun algoritmo guadagnerebbe nulla.

Chaitin: incompletezza e il numero Omega

Chaitin spinge $K$ fino in fondo, dentro la logica matematica, e ne ricava un risultato che tocca i fondamenti stessi della matematica.

Il suo teorema di incompletezza (pubblicato nel 1974 in Information-Theoretic Limitations of Formal Systems, Journal of the ACM) dice: per ogni sistema formale coerente $S$ con un numero finito di assiomi, esiste una costante $L$ — dipendente da $S$ — tale che $S$ non può dimostrare l’enunciato " $K(s) \ge L$ " per nessuna stringa $s$ specifica.

In parole: oltre una certa soglia di complessità, il sistema formale non riesce a dimostrare che una particolare stringa è complessa, anche se sappiamo, dal conteggio appena fatto, che quasi tutte lo sono. C’è un mare di stringhe complesse, e il sistema non riesce a puntare il dito su quasi nessuna di esse e dire “questa è complessa, ecco la prova”.

La prova è ancora Berry. Se $S$ potesse dimostrare $K(s) \ge L$ per un $L$ abbastanza grande, allora enumerando meccanicamente tutte le dimostrazioni di $S$ troveremmo, prima o poi, una stringa complessa esibita da un programma corto — quel programma che enumera le dimostrazioni — e ricadremmo nella contraddizione di prima.

È una forma del teorema di incompletezza di Kurt Gödel (logico austriaco, 1906-1978, che nel 1931 dimostrò che ogni sistema formale abbastanza ricco da esprimere l’aritmetica è incompleto o incoerente), ottenuta però via il paradosso di Berry invece che via l’auto-riferimento diagonale dell’originale.

Lo slogan di Chaitin condensa tutto: un sistema con $L$ bit di assiomi non può spremere conclusioni che richiedono più di $L$ bit di informazione. Non puoi tirare fuori da un teorema più informazione di quanta ne abbiano messa gli assiomi. L’incompletezza, vista da qui, è una legge di conservazione dell’informazione.

Da qui Chaitin (1975) costruisce il numero $\Omega$ , forse l’oggetto matematico più strano di questa storia, e certamente il più carico di paradosso.

$\Omega$ è la probabilità che una macchina di Turing universale prefix-free si fermi, se le diamo in input una sequenza di bit ottenuti lanciando una moneta. È un singolo numero reale che riassume il comportamento di arresto di tutti i programmi possibili:

$\Omega = \sum_{p \,:\, U(p) \text{ si ferma}} 2^{-|p|}$

la somma, su tutti i programmi $p$ che terminano, di $2^{-|p|}$ (la probabilità di pescare proprio quel programma con lanci di moneta equa). La proprietà di codice prefisso garantisce, via la disuguaglianza di Kraft vista in Minimum Description Length, che la somma converga a un numero tra $0$ e $1$ .

$\Omega$ è un numero reale perfettamente definito, eppure ha tre proprietà spiazzanti che lo rendono quasi un paradosso fatto numero.

È algoritmicamente casuale nel senso più forte (Martin-Löf random): le sue cifre binarie sono incomprimibili, i primi $n$ bit hanno complessità $\ge n - O(1)$ . Conoscere le prime mille cifre non aiuta minimamente a indovinare la millesima e prima.

È enumerabile ma non calcolabile: ci si può avvicinare al suo valore dal basso, con stime crescenti, ma non si possono mai stabilire con certezza le sue cifre, perché farlo richiederebbe di sapere quali programmi si fermano.

E concentra tutta l’indecidibilità dell’arresto in un solo numero: conoscere i primi $n$ bit di $\Omega$ permetterebbe di risolvere il problema dell’arresto per tutti i programmi di lunghezza fino a $n$ .

È, in un senso preciso, il numero più informativo che possa esistere — ogni suo bit è un frammento di verità matematica indecidibile, compresso al massimo. Se potessi scriverne le cifre, avresti in mano la soluzione di innumerevoli problemi aperti della matematica; ed è proprio perché potresti farlo che non puoi calcolarle.

Il prior universale di Solomonoff

Torniamo a Solomonoff e alla domanda da cui era partito: l’induzione. Come prevedere il prossimo simbolo di una sequenza, viste le osservazioni passate, scegliendo tra tutte le ipotesi possibili? Solomonoff identifica le ipotesi con i programmi e definisce la probabilità algoritmica, o prior universale:

$M(x) = \sum_{p \,:\, U(p) = x*} 2^{-|p|}$

la somma, su tutti i programmi che producono un output che inizia con $x$ , di $2^{-|p|}$ , dove $2^{-|p|}$ è la probabilità di generare proprio quel programma pescando bit a caso. Programmi corti contribuiscono molto, programmi lunghi quasi niente.

Vale l’approssimazione $M(x) \approx 2^{-K(x)}$ : la probabilità universale di un oggetto è dominata dal suo programma più corto. Un oggetto con una ricetta breve è, a priori, più probabile di uno senza. La semplicità diventa probabilità a priori, automaticamente, senza che nessuno debba deciderlo a mano.

Solomonoff dichiarò quattro ispirazioni esplicite per questa costruzione. Il rasoio di Occam: preferisci le ipotesi più semplici, cioè i programmi più corti, che pesano di più nella somma. Il principio di Epicuro: non scartare nessuna ipotesi consistente con i dati, tienile tutte, ognuna col suo peso.

E poi la macchina di Turing universale, che dà lo spazio delle ipotesi — l’insieme di tutti i programmi — senza doverlo scegliere a mano; e la regola di Bayes, che aggiorna le probabilità man mano che arrivano i dati.

Il risultato è un prior bayesiano che non richiede di scegliere arbitrariamente una distribuzione a priori. È il punto delicato di ogni inferenza bayesiana: da dove viene il prior? Solomonoff risponde pesando ogni ipotesi secondo la sua semplicità algoritmica, e dando automaticamente più credito alle teorie che comprimono meglio i dati osservati. Comprimere bene il passato e prevedere bene il futuro diventano, di nuovo, la stessa operazione.

Il teorema chiave: la predizione di Solomonoff converge alla vera distribuzione che genera i dati — purché questa sia computabile — e lo fa più rapidamente di qualunque altro metodo di predizione, con un errore totale limitato da $K$ della vera distribuzione. È induzione ottimale in un senso preciso e dimostrato.

Il prezzo, ereditato da $K$ e dal problema dell’arresto, è che $M$ è incomputabile. È una teoria fondazionale: definisce cosa sarebbe l’induzione perfetta, non come eseguirla. Lo status delle affermazioni qui è misto, e va tenuto netto: l’ottimalità è un teorema, l’incomputabilità è un teorema, ma l’uso di tutto questo come ricetta pratica è impossibile per costruzione, non per mancanza di ingegno.

Esempi

Quattro esempi eterogenei, dal più elementare al più applicato: due stringhe a confronto, $\pi$ come trabocchetto, la distanza di compressione come strumento reale, e il programma di Berry come oggetto eseguibile del paradosso.

Esempio 1 — due stringhe di mille bit (numerico)

Riprendiamo le due stringhe dell’apertura, e stimiamo $K$ a mano.

La prima è “01” ripetuto cinquecento volte. Una ricetta: ripeti 500 volte: stampa "01". La parte variabile è il numero 500, che in binario sta in circa $\log_2 500 \approx 9$ bit; il resto è il codice fisso del loop e della stampa, una costante che non dipende da quante ripetizioni.

Quindi $K \approx 9 + \text{costante}$ : qualche decina di bit, contro i mille della stringa. Comprimibilità altissima. E nota che se le ripetizioni fossero un milione invece di cinquecento, $K$ crescerebbe solo di una manciata di bit (per scrivere il numero più grande), mentre la stringa crescerebbe di milioni: la complessità resta quasi piatta.

La seconda è mille bit di moneta equa. Con probabilità schiacciante — per l’argomento di conteggio della sezione precedente, che dice che quasi tutte le stringhe sono incomprimibili — non esiste ricetta più corta del leggere tutti i bit a uno a uno. Quindi $K \approx 1000$ , quanto la stringa stessa. Incomprimibile.

Stessa lunghezza, mille bit in entrambi i casi, ma $K$ radicalmente diverso: qualche decina di bit contro mille. È la dimostrazione concreta, fatta a mano, che la complessità di Kolmogorov misura la struttura interna di un oggetto, non la sua taglia esterna.

E nota il contrasto con Shannon. Se entrambe le stringhe vengono da una sorgente uniforme su mille bit, hanno la stessa probabilità $2^{-1000}$ , e quindi la stessa “informazione di Shannon” rispetto a quella sorgente. $K$ le distingue nettamente, $H$ no — non perché una delle due sbagli, ma perché parlano di cose diverse: un singolo oggetto contro una sorgente. È il fraintendimento centrale del capitolo, mostrato su un caso minimo.

Esempio 2 — π sembra casuale ma non lo è (concettuale)

Prendi i primi dieci milioni di cifre binarie di $\pi$ . Sottoponile a qualunque test statistico di casualità: frequenza di zeri e uni, distribuzione delle coppie, delle terne, autocorrelazioni. Le passano tutte. Da un punto di vista statistico, le cifre di $\pi$ sono indistinguibili dal rumore.

Eppure $K$ di quei dieci milioni di cifre è minuscola: poche centinaia di byte. Esistono formule corte — per esempio la formula di Bailey-Borwein-Plouffe, scoperta nel 1995, che calcola le cifre binarie di $\pi$ a partire da una posizione qualsiasi — che le generano tutte con un programma breve.

La ricetta è corta, quindi la stringa è semplice, anche se sembra casuale a ogni test di frequenza. Tutta l’apparente casualità delle cifre di $\pi$ è il prodotto di un processo deterministico e compatto.

Questo separa due nozioni che il senso comune tiene confuse: la casualità statistica (passare i test di frequenza) e la casualità algoritmica (non avere ricetta corta). $\pi$ è statisticamente casuale ma algoritmicamente semplice.

La casualità di Kolmogorov è la nozione più forte. Una vera sequenza casuale deve fallire perfino il test di “esiste un programma corto che mi genera”. $\pi$ lo fallisce clamorosamente, perché quel programma esiste e lo conosciamo — ed è questa la differenza che i test di frequenza, per costruzione, non possono cogliere.

Esempio 3 — clustering per compressione (scenario reale)

Poiché $K$ non si calcola, l’uso pratico passa sempre per un’approssimazione: usare un compressore reale al posto di $K$ . Lo strumento canonico è la Normalized Compression Distance (NCD), introdotta da Rudi Cilibrasi e Paul Vitányi (informatici olandesi, dal Centrum Wiskunde & Informatica di Amsterdam) nel 2005, nel paper Clustering by Compression (IEEE Transactions on Information Theory).

L’idea è elegante: due oggetti sono “vicini” se, una volta concatenati, si comprimono molto bene insieme — cioè se conoscere uno aiuta a comprimere l’altro. Se due testi condividono frasi, vocabolario, struttura, comprimere la loro concatenazione costa poco più che comprimere il maggiore dei due.

Detto $C(\cdot)$ la dimensione compressa da un compressore reale (gzip, bzip2), la distanza si scrive

$NCD(x, y) = \frac{C(xy) - \min(C(x), C(y))}{\max(C(x), C(y))}$

dove $xy$ è la concatenazione dei due oggetti. Se $x$ e $y$ condividono struttura, comprimere $xy$ costa poco più che comprimere il maggiore dei due, e $NCD$ è vicina a zero.

Se invece sono del tutto indipendenti, comprimerli insieme non aiuta, e $NCD$ è vicina a uno. La formula normalizza in modo che il valore stia tra zero e uno indipendentemente dalle dimensioni assolute degli oggetti, così da poter confrontare coppie eterogenee.

Il punto interessante è che questa misura non richiede di estrarre feature: si applica a sequenze grezze, senza dire al sistema cosa guardare. È stata usata per costruire alberi filogenetici di lingue dal solo testo, classificare brani musicali da file MIDI, raggruppare genomi e perfino riconoscere famiglie di malware dai binari.

È un esempio concreto di $K$ usata come bussola: non si calcola $K$ , la si approssima con un compressore reale, e si ottiene uno strumento funzionante in nicchie ben precise.

La classe di affermazione va però tenuta onesta. $C$ è un upper bound grezzo di $K$ , non un’approssimazione con errore controllato: funziona dove funziona, per via empirica, non con garanzie teoriche. Se il compressore è cieco a una certa struttura, la NCD la ignora.

Esempio 4 — il programma di Berry, eseguibile (logico)

Il programma GeneraStringaComplessa della sezione sull’incomputabilità non è solo una prova: è un oggetto a cui pensare concretamente. Immagina di averlo scritto davvero, supponendo per un attimo di avere la funzione K. Lo lanci con $N$ uguale a otto miliardi. Il programma comincia a scorrere le stringhe e a chiedere “questa ha $K \ge$ otto miliardi?”.

Prima o poi (in teoria) restituisce una stringa $s$ con complessità almeno otto miliardi di bit. Ma l’intero programma che l’ha trovata è lungo, diciamo, sette miliardi di bit: il codice di K più il piccolo wrapper. Allora quella stringa “incomprimibile in meno di otto miliardi di bit” l’abbiamo appena descritta in sette miliardi — è la sua versione compressa, e contraddice la sua stessa definizione.

L’assurdo è palpabile, e l’unica via d’uscita è che K non possa esistere. Il paradosso non è un trucco linguistico: è una macchina che, se la funzione esistesse, girerebbe e produrrebbe la contraddizione.

Lo stesso programma, eseguito con la K finta che ogni compressore reale fornisce — un upper bound, non il vero valore — gira senza paradosso, ma non trova mai la vera stringa di alta complessità. Trova solo stringhe che quel compressore specifico non sa accorciare, il che è tutta un’altra cosa: la sua cecità non è incomprimibilità.

Applicazioni pratiche

La complessità di Kolmogorov vive in pratica per influenza, non per calcolo diretto: nessuno la computa, ma molte tecniche la inseguono con approssimazioni calcolabili. Compare in quattro punti del lavoro di chi costruisce sistemi AI, sempre come idea-guida dietro strumenti che ne usano un surrogato.

Vale la pena leggere questa sezione tenendo a mente la distinzione che la sezione “Dove si rompe” renderà esplicita: qui si parla di influenza concettuale e di proxy, non di applicazioni dirette di una grandezza che, ricordiamolo, non si può calcolare.

Il rasoio di Occam, finalmente definito. Ogni volta che si preferisce un modello più semplice a uno più complesso a parità di fit — la regolarizzazione, l’early stopping, la scelta del grado di un polinomio — si applica una versione del rasoio di Occam. Ma “semplice” è notoriamente vago.

La complessità di Kolmogorov gli dà la definizione più pulita che esista: semplice = ricetta corta = $K$ basso. Il rasoio smette di essere un principio estetico e diventa la preferenza per oggetti a bassa complessità algoritmica, una grandezza precisa anche se incalcolabile.

La regolarizzazione pratica (weight decay, penalità L1 e L2) non calcola $K$ — non potrebbe — ma è ispirata allo stesso principio: pesi piccoli e regolari hanno una descrizione più corta. Va detta per quello che è: un’influenza concettuale, non un’identità formale.

MDL come ombra calcolabile di K. Tutto il principio Minimum Description Length è, esplicitamente, la mossa per rendere calcolabile l’idea di Kolmogorov.

Dove $K$ cerca il programma più corto tra tutti i programmi possibili (e quindi sbatte contro l’incomputabilità e l’halting problem), MDL fissa una classe di modelli e cerca il two-part code più corto dentro quella classe. È la complessità di Kolmogorov ristretta a un recinto calcolabile: si paga la perdita di generalità con il guadagno di poterla effettivamente computare.

Quando usi MDL, o il suo cugino approssimato BIC, per scegliere quanti cluster, quale grado di polinomio, quale profondità d’albero, stai approssimando $K$ in modo pratico — scegliendo l’oggetto con la descrizione più corta nella classe che ti sei concesso.

Compressione come proxy di modellazione. Lo Hutter Prize (finanziato dal 2006 da Marcus Hutter, ricercatore in AI di formazione tedesca, autore di lavori fondazionali sull’intelligenza artificiale generale) premia chi comprime di più un estratto di Wikipedia — oggi enwik9, un gigabyte, con un montepremi che ha raggiunto i 500.000 euro.

Il regolamento conta nel file finale anche il decompressore, imponendo la contabilità completa: un compressore che bara memorizzando i dati nel proprio codice non guadagna nulla, perché paga in dimensione del codice ciò che risparmia sui dati. È la contabilità del two-part code imposta come regola di gara.

La tesi del concorso è che comprimere bene un testo richieda di modellarne la struttura — grammatica, fatti, regolarità del mondo descritte nel testo — e che quindi il tasso di compressione sia un proxy misurabile di capacità di modellazione. È una scommessa, come si vedrà nella sezione successiva, ma resa numerica e falsificabile: collega direttamente $K$ alla pratica della valutazione dei modelli.

La distanza di compressione come strumento senza feature. La NCD dell’esempio 3 è una tecnica reale in nicchie dove non si vogliono o non si possono progettare feature: clustering di sequenze grezze, rilevamento di anomalie, confronto di file di formato ignoto.

È $K$ approssimata da un compressore reale, e funziona proprio perché un buon compressore cattura la struttura condivisa tra oggetti — la stessa struttura che $K$ misurerebbe in modo ideale. Dove altri approcci richiedono di decidere a mano cosa contare, la compressione lascia che sia il compressore a trovare le regolarità. È il caso più tangibile di $K$ che, surrogata, lavora.

Dove si rompe

La complessità di Kolmogorov è teoricamente solidissima: le sue proprietà sono teoremi, non congetture. Ciò che si rompe non è la teoria, ma l’intuizione di chi confonde le classi di affermazione, o tira l’idea oltre dove può arrivare.

Questa sezione raccoglie i fraintendimenti, e sono numerosi proprio perché qui convivono teoremi profondi (invarianza, incomputabilità, incompletezza), una tesi filosofica (compressione = intelligenza) e un modello teorico non implementabile (AIXI) — tre classi di affermazione facilissime da scambiare l’una per l’altra, e quasi sempre scambiate.

Confondere K con l’entropia di Shannon. È il fraintendimento centrale, e merita di essere ripetuto fino alla noia. L’entropia $H$ misura la sorpresa media di una sorgente probabilistica: esiste solo se c’è una distribuzione $p$ , ed è una proprietà della distribuzione, non di un singolo esito.

La complessità $K(x)$ misura il contenuto descrittivo di un singolo oggetto: non richiede alcuna distribuzione, ed è una proprietà intrinseca della stringa rispetto al calcolo. Le due rispondono a domande diverse.

Sono legate — per una sorgente computabile, il valore atteso di $K$ normalizzato per la lunghezza converge a $H$ , un risultato che si trova in Cover e Thomas — ma restano concettualmente distinte. La differenza decisiva è operativa: $H$ si calcola se conosci $p$ ; $K$ non si calcola mai. Chiamarle entrambe “informazione” e trattarle come intercambiabili è l’errore più diffuso dell’intera area.

Credere che K sia calcolabile, magari “approssimandola con gzip”. $K$ è incalcolabile, punto: lo dice il teorema, sia via Berry sia via halting problem. Non è una questione di non aver ancora trovato l’algoritmo giusto: l’algoritmo non può esistere.

Un compressore reale fornisce un upper bound — trova una descrizione corta, non necessariamente la più corta — ma non c’è alcuna garanzia su quanto quell’upper bound sia lontano dal vero $K$ . Potrebbe essere vicinissimo o lontanissimo, e non c’è modo di saperlo, perché conoscere la distanza significherebbe conoscere $K$ .

La NCD e tecniche simili funzionano in pratica, ma chi le presenta come “calcolo approssimato di $K$ con errore controllato” sovravaluta la solidità: sono proxy euristici, non approssimazioni con un bound dimostrato. Utili, ma onestamente euristici.

Pensare che “sembra casuale” significhi “alta K”. L’esempio di $\pi$ esiste apposta per rompere questa intuizione. Una stringa può passare ogni test statistico di casualità e avere $K$ minuscola, perché un programma corto la genera.

La casualità algoritmica è strettamente più forte della casualità statistica: richiede che nessun programma corto produca la stringa, non solo che le frequenze siano bilanciate. È una barra molto più alta, e quasi tutte le stringhe la superano — ma quelle che incontriamo nel mondo, generate da processi con struttura, spessissimo no.

Trattare il teorema di invarianza come “K è un numero ben definito”. $K(x)$ è definita solo a meno di una costante additiva che dipende dalla macchina scelta. Per stringhe lunghe la costante è trascurabile e ha senso parlare di " $K(x)$ " come se fosse un numero.

Ma per stringhe corte la costante può dominare completamente il valore, e “il” $K$ di una stringa breve specifica non è ben definito senza fissare la macchina $U$ . Su una stringa di dieci bit, una costante di interprete di cento bit rende la nozione priva di senso operativo. È una nozione asintotica e teorica; non aspettarti un numero esatto da incollare in una tabella per un oggetto piccolo.

Presentare “compressione = intelligenza” come un teorema. Qui serve la distinzione più fine del capitolo, perché si toccano due affermazioni che sembrano simili e non lo sono affatto.

Da un lato c’è l’identità formale, discussa in Minimum Description Length, tra log-loss e lunghezza di codice: un modello con cross-entropy bassa produce, via codifica aritmetica, un file corto, esattamente proporzionale alla loss. Quella è un teorema, conseguenza diretta di Shannon, e non ammette repliche.

Dall’altro c’è la tesi che comprimere bene equivalga a comprendere, a essere intelligenti. È un’ipotesi di lavoro, sostenuta dalla scuola dell’algorithmic information theory (Hutter, Matt Mahoney, Shane Legg) e incarnata nello Hutter Prize, ma non dimostrata e non oggetto di consenso.

Comprimere bene un testo richiede di modellarne le regolarità statistiche; che questo coincida con “capirlo” nel senso pieno della parola è una scommessa filosofica, non un risultato matematico. Presentare la tesi come se fosse il teorema è esattamente l’errore che la disciplina delle classi di affermazioni esiste per impedire.

Credere che AIXI sia un’architettura implementabile. AIXI (proposto da Hutter nel 2000, formalizzato nel libro Universal Artificial Intelligence, Springer 2005) è l’agente teorico ottimale universale. Combina l’inferenza di Solomonoff, per modellare l’ambiente, con la teoria delle decisioni sequenziali, per scegliere l’azione che massimizza il reward atteso futuro.

È dimostrato ottimale in ogni ambiente computabile — un risultato forte — ed è anche incomputabile, perché eredita l’incomputabilità di Solomonoff. Hutter ne ha proposto varianti limitate in tempo e spazio (AIXItl) che sono calcolabili ma di costo astronomico, inutilizzabili in pratica su qualunque hardware reale.

AIXI è una bussola concettuale: definisce cosa sarebbe un agente perfetto, non come costruirne uno. Chiamarlo “il modello dell’AGI” senza marcare il suo status di oggetto teorico non implementabile è fuorviante quanto chiamare la velocità della luce “un mezzo di trasporto”.

Sovrastimare il transfer pratico al deep learning. Questa è la rottura più importante da interiorizzare con onestà. $K$ non si calcola. Nessun optimizer minimizza $K$ ; nessuna loss è $K$ .

Le applicazioni dirette al deep learning moderno sono per lo più concettuali e ispirazionali: il rasoio di Occam dietro la regolarizzazione, l’idea di compressione dietro le metriche di valutazione, la NCD in nicchie senza feature. Sono usi reali ma laterali, non il motore della tecnologia.

La complessità di Kolmogorov è una delle idee più profonde della teoria dell’informazione, e proprio per questo è facile prestarle un potere pratico che non ha. È una bussola che indica la direzione — semplicità, compressione, descrizione minima — non un motore che muove i modelli. Tenere ferma questa distinzione è il modo migliore di rendere onore a un’idea che vale per quello che è: fondazionale, non operativa.

Confondere l’incomputabilità con l’inutilità. Per chiudere, il rovescio dell’avvertimento precedente: incomputabile non vuol dire inutile, e sarebbe un errore opposto altrettanto grave.

$K$ fissa il limite teorico assoluto di ogni compressore possibile, dà la definizione esatta di casualità, fonda l’induzione di Solomonoff, produce l’incompletezza di Chaitin, e illumina il rasoio di Occam. Sono contributi enormi, tutti dovuti a una grandezza che non si può calcolare.

È utile come concetto di confine: il punto ideale verso cui le tecniche calcolabili tendono senza mai raggiungerlo, e rispetto al quale si misura quanto sono lontane. Una bussola non deve essere raggiungibile per indicare il nord; deve solo indicarlo in modo affidabile.

Collegamenti

Minimum Description Length: il capitolo precedente e il suo complemento diretto. MDL è la versione calcolabile di $K$ , ristretta a una classe di modelli; lì vivono il two-part code e l’identità formale log-loss = lunghezza di codice, che qui si tengono distinti dalla tesi compressione = intelligenza.
Informazione come riduzione di incertezza: l’entropia di Shannon, la nozione di informazione su una sorgente, da contrapporre con cura a $K$ come informazione su un singolo oggetto.
Entropia, cross-entropy, KL divergence: la macchina dell’entropia e della cross-entropy, su cui poggia il legame tra $K$ medio e $H$ per sorgenti computabili.
Il trade-off bias-varianza: la preferenza per modelli semplici e la regolarizzazione, di cui $K$ è la formalizzazione-limite. Il rasoio di Occam letto come bassa complessità algoritmica.
La macchina di Turing e “Computing Machinery and Intelligence”: la macchina di Turing universale e il problema dell’arresto, su cui poggiano la definizione e l’incomputabilità di $K$ .
ridondanza ed error correction, in Ridondanza, error correction, robustezza: la disuguaglianza di Kraft usata qui per la convergenza di $\Omega$ , e la ridondanza come ciò che la compressione toglie.
rate-distortion (in preparazione): la compressione lossy, che chiede quanta perdita accettare; complementare al limite lossless ideale dato da $K$ .
ponte-informazione-llm (in preparazione): il ponte tra token prediction, compressione e rappresentazioni, di cui $K$ è la cornice teorica più ampia.
inferenza bayesiana e prior, in percezione come inferenza bayesiana (in preparazione): l’inferenza di Solomonoff come prior universale, il caso limite della scelta del prior.

Per andare oltre

Solomonoff, R. J. (1964). A Formal Theory of Inductive Inference, Part I e II, Information and Control, 7(1), 1-22 e 7(2), 224-254. La nascita della probabilità algoritmica e dell’induzione universale, da una domanda sulla previsione.
Kolmogorov, A. N. (1965). Three Approaches to the Quantitative Definition of Information, Problems of Information Transmission, 1(1), 1-7. Il paper che dà alla nozione il suo nome e prova l’invarianza.
Chaitin, G. J. (1974). Information-Theoretic Limitations of Formal Systems, Journal of the ACM, 21(3), 403-424. Il teorema di incompletezza via complessità: un sistema con $L$ bit di assiomi non dimostra che una stringa ha complessità molto superiore a $L$ .
Li, M. & Vitányi, P. (2019, 4a ed.). An Introduction to Kolmogorov Complexity and Its Applications, Springer. Il testo monografico di riferimento: definizioni, incomputabilità, randomness, Solomonoff, applicazioni. La fonte da cui partire per approfondire seriamente.
Cilibrasi, R. & Vitányi, P. (2005). Clustering by Compression, IEEE Transactions on Information Theory, 51(4), 1523-1545. Introduce la Normalized Compression Distance e mostra $K$ approssimata da compressori reali al lavoro su lingue, musica e genomi.
Cover, T. M. & Thomas, J. A. (2006, 2a ed.). Elements of Information Theory, cap. 14, Wiley. La trattazione più accessibile del legame tra complessità di Kolmogorov ed entropia di Shannon, con l’argomento di conteggio.
Hutter, M. (2005). Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, Springer. La formalizzazione di AIXI come agente ottimale universale; da leggere tenendo a mente che è un modello teorico incomputabile, non un progetto implementabile.