VIERI BENCI è docente di Analisi matematica all’Università di Pisa. Dopo essere stato direttore del Centro Interdipartimentale per loStudio dei Sistemi Complessi dal 1998 al 2004 e del Dipartimento di Matematica applicata dell’Università di Pisa dal 2004 al 2007, ha ricevuto nel 2009 il Premio “Wanda e Luigi Amerio” da parte del’Istituto Lombardo Accademia di Scienze e Lettere. È autore di più di 150 articoli su riviste nazionali e internazionali per lo più nel campo delle equazionialle derivate parziali ed argomenti collegati. Altri interessi di ricerca riguardano l’Analisi non standard e le applicazioni della Teoria dell’informazione allo studio delle dinamiche caotiche.

 



Teoria algoritmica dell’informazione


Alan Turing

3.1. Come si misura la quantità di informazione?


A.-Hai presente che cos’è una macchina di Turing universale?

B.-Certamente no. Sai bene che al Liceo queste cose non ce le spiegano.

A.-È vero. In realtà, molte volte questi concetti non sono insegnati neppure all’Università (e mostra all’amico un disegno di una macchina di Turing e una tabella che ne illustra il funzionamento).

B.-Mamma mia, cos’è? Un ibrido tra un macina-caffè ed il computer di Matusalemme?!?

A.-Ma no! È solo un disegno schematico. Il disegno non ha importanza; nessuno ha mai costruito veramente una macchina di Turing. Se vuoi capire, devi guardare solo questa tabella qui.

B.-Ma sei scemo! Ho ben altro da fare che studiarmi la tua tabella.

A.-Comunque non ha importanza perché, al posto di una macchina di Turing universale, si può sostituire il tuo computer con un semplice linguaggio di programmazione.

B.-Per esempio, il Basic che è l’unico che conosco?

A.-Il Basic o il Pascal fa lo stesso. L’unica astrazione che devi usare consiste nel fatto di supporre che il tuo computer abbia memoria infinita e che tu abbia la pazienza di aspettare che il programma abbia completato il suo ciclo (ammesso che si fermi).

B.-Ehi, un momento: posso immaginarmi un computer con memoria infinita ma non quali grandiosi programmi ci si possa far girare.

A.-Non prendermi troppo alla lettera. Dicendo che un computer ha memoria infinita, voglio semplicemente dire che ha memoria sufficiente per farci girare un qualunque programma. Siccome non si può sapere a priori la memoria necessaria, si deve supporre che gli si possa aggiungere un po’ di memoria tutte le volte ciò si renda necessario.

B.-È come quando, in un compito di esame, si possono sempre richiedere nuovi fogli bianchi.

A.-Hai capito benissimo. Una macchina di Turing si dice universale se può “simulare” ogni altra macchina di Turing. I computer che usiamo sono macchine di Turing universali. Puoi mettergli dentro il linguaggio che ti pare: Pascal, Basic, Lisp. E ciascuno di questi linguaggi può simulare un qualsiasi altro linguaggio.

B.-Fin qui ci arrivo.

A.-Allora, supponiamo che tu ed il tuo amico sulla luna abbiate due computer con lo stesso linguaggio di programmazione. Se vuoi fare in modo che sul display del tuo amico compaia la stringa S1, basta che tu spedisca il se-guente messaggio: “for n= 1 to 10, print “0001, next”. Questo messaggio è più corto del messaggio “print “0001000100010001000100010001000100010001””. A questo punto, si può definire la quantità di informazione contenuta in una qualunque stringa come la lunghezza del più corto programma che produce quella stringa. Una volta fissata una macchina di Turing universale Uo, per dirlo in parole povere, una volta fissato il linguaggio di programmazione, la quantità di informazione contenuta in una stringa S risulta essere un numero intero ben definito. Esso sarà denotato con il simbolo IU(x). In simboli, possiamo scrivere:


dove |p| denota la lunghezza del programma p (cioè il numero di 0 e di 1 che lo compongono) e U(p) denota la stringa prodotta dal tuo computer quando esegui il programma p.

B.-Molto semplice... ed interessante. Ma definita in questa maniera, la quantità di informazione viene a dipendere dal linguaggio di programmazione scelto, cioè da U.

A.-Questo è vero; ma questa dipendenza non è troppo grave. Infatti, se V è un altro linguaggio di programmazione, risulta che:


dove C(U, V) è una costante che dipende da U e V, ma non dalla stringa. Quindi, se cambi programma, la quantità di informazione risulta modificata solo di una quantità finita. Questo fatto ci garantisce che la quantità di informazione è un buon concetto e la sua dimostrazione, dovuta a Kolmogorov, è quasi immediata.

B.-Quindi la quantità di informazione contenuta in una stringa è un concetto ben definito, a meno di una costante. In fondo è abbastanza naturale pensare che la quantità di informazione contenuta in una stringa non sia proporzionale alla sua lunghezza ma sia una cosa indipendente che, in un modo o nell’altro, può essere definita rigorosamente. Però... credo di avere perso il filo del discorso. Stavamo parlando di complessità e di casualità. Adesso, siamo approdati ad una nozione abbastanza diversa.

A.-Possiamo riepilogare tutti i passaggi: una stringa si dice casuale se non ha regole nascoste che la possano rendere più corta. Grazie alla nozione di “macchina di Turing universale” queste nozioni possono essere perfettamente formalizzate (a meno di costanti che non sono rilevanti dal punto di vista generale). Si può definire formalmente la quantità di informazione (chiamata anche complessità nel senso di Kolmogorov) contenuta in una stringa. A questo punto, una stringa può essere definita casuale se il suo contenuto di informazione I(x) è più o meno uguale alla lunghezza |x| della stringa stessa.


Andrey Kolgomorov

B.-Ma che cosa vuol dire “più o meno uguale”? Questa non è certo una asserzione matematica.

A.-Certamente, bisogna dare una valutazione quantitativa. Per motivi tecnici si è deciso di definire x casuale se:

Per esempio, se una stringa con un milione di caratteri non è casuale, può essere prodotta da una stringa un po’ più corta, ovvero da una stringa di soli:

caratteri.

 

3.2. Quante sono le stringhe casuali?

 

B.-Quindi, almeno per stringhe sufficientemente lunghe, ha senso parlare di stringhe intrinsecamente casuali. Ma quante sono? Immagino che siano molte.

A.-Non sono molte, ma moltissime. Calcoliamo ad esempio quante sono le stringhe casuali di lunghezza N. In totale ci sono 2N stringhe di lunghezza N. Quelle che non sono casuali possono essere prodotte da stringhe appena un po’ più corte ovvero da stringhe di lunghezza N – log2N. Ma le stringhe di questa lunghezza sono al più:

e quindi le stringhe casuali sono almeno:

Dunque, tra le stringhe di un milione di caratteri, solo un milionesimo di loro possono essere non casuali. Il 99,9999% sono certamente casuali.

B.-Ma allora è facile avere stringhe casuali. Anche considerando stringhe di solo cento caratteri, almeno il 99% di loro sono casuali.

 

3.3. Numeri casuali

 

A.-Quindi la stragrande maggioranza dei numeri sono casuali.

B.-Adesso, cosa c’entrano i numeri?

A.-Poiché le stringhe possono essere poste in corrispondenza biunivoca con i numeri naturali secondo la seguente tabella (ordine lessicografico):

ne segue che ogni numero naturale può essere intrinsecamente casuale. Un numero n si dice casuale se:

 

B.-Vacci piano. Non ti seguo.

A.-In base alla tabella, parlare di numeri naturali o di stringhe è la stessa cosa...

B.-... e così si tira in ballo anche l’Aritmetica...

A.-... e quindi possiamo parlare di numeri casuali. Un numero n, in base alla tabella scritta sopra, può sempre essere rappresentato con log2(n+2) simboli. Ma può anche avere delle regole nascoste; per esempio, il numero 6.915.878.970 è il prodotto dei primi 10 numeri primi. Usando queste regole nascoste si può scrivere un programma che produce il numero n sul display del tuo computer. La lunghezza del più corto di questi programmi si denota con I(n) ed è il contenuto di informazione di n. Quindi non solo ti ho spiegato cos’è una stringa casuale ma anche che cosa è un numero casuale. Naturalmente, con questa definizione, i numeri piccoli sono tutti casuali...

B.-Senti, per le stringhe ti posso anche dare ragione ma identificare i numeri con le stringhe e dire che in questa maniera si può definire che cos’è un numero a caso mi sembra una grande forzatura. Se tu avessi ragione, si avrebbe che quasi tutti i numeri sono casuali e quindi, non potendo distinguere un numero casuale dall’altro, avrei che sono più o meno quasi tutti equiprobabili...

A.-Non ho detto che quasi tutti i numeri sono equiprobabili; la probabilità è un’altra cosa...

 

3.4. Probabilità a priori di un numero

 

B.-Non mi dire che, con la tua teoria, si può anche definire la probabilità a priori di un numero o di un qualunque altro oggetto. Ti posso dare ragione quando dici che puoi definire che cos’è una stringa casuale ma, per definire la probabilità, penso che “il vecchio lancio della moneta” resti il metodo più efficiente o almeno il più intuitivo.

A.-Cosa mi diresti se affermassi che la probabilità a priori di un numero n non è altro che P(n) = 2–I(n)?

B.-Direi che è una definizione come un’altra, ma non mi sembra minimamente correlata alla idea intuitiva di probabilità che abbiamo “a priori”. A meno che tu non abbia argomenti per convincermi.

A.-Certo che ce li ho. Altrimenti, non avrei tirato in “ballo” questa questione. Mi dici che sei ancora affezionato al vecchio buon “lancio della moneta”. Bene: supponiamo di avere la tua moneta perfetta, lanciamola e vediamo qual è la probabilità che mi dia un certo numero.

B.-Se codifichi i primi 230 numeri in un qualunque modo e fai trenta lanci, è chiaro che ogni numero ha la stessa probabilità che è 2-30. E ciò resta vero anche se sostituisci la moneta con una stringa casuale di 30 caratteri.

A.-Non correre. Non voglio fare trenta lanci, voglio fare infiniti lanci. O meglio voglio fare N lanci e tenere conto di tutte le possibilità che esistono, qualunque sia il numero N.

B.-Forse sto capendo. Fammi indovinare: guardando la tua tabella, si può dire che il numero 0 e il numero 1 hanno probabilità 1/2 poiché possono essere ottenuti con un lancio con probabilità 1/2. I numeri 2, 3, 4 e 5 hanno probabilità 1/4 perché possono essere ottenuti con due lanci con probabilità 1/4...

A.-Guarda che la somma delle probabilità di ciascun evento indipendente deve essere uguale ad 1 e tu con soli sei numeri hai già raggiunto il numero 2:

P(0)+P(1)+P(2)+P(3)+P(4)+P(5)=1/2+1/2+1/4+1/4+1/4+ 1/4 = 2.

B.-Ma basta che poi divida per un fattore di normalizzazione (che in questo caso è 2) e ottengo:

P(0) = P(1) = 1/4
P
(2) = P(3) = P(4) = P(5) = 1/8

A.-La tua idea è buona, se vuoi definire la probabilità a priori di una quantità finita di numeri ma, se vuoi considerare tutti i numeri, il tuo fattore di normalizzazione diventa:

B.-Già è vero... , ma allora come si fa?

A.-Quasi nel modo che hai detto tu. Lanci la tua moneta e la successione di “0” ed “1” che ti viene sarà considerata un programma e messa in una macchina di Turing universale. Quindi aspetti il risultato. Questa volta la somma delle probabilità di ciascun numero ti verrà minore (o al più uguale) a uno, almeno se usi un piccolo accorgimento, ovvero che nessun programma sia uguale alla parte iniziale di un altro programma. Questo capita molto spesso nei programmi reali. Basta che un programma “dichiari” in anticipo la sua lunghezza. In questo caso la probabilità a priori di un numero è definita da:

ovvero la probabilità a priori di un numero è uguale alla probabilità che questo numero venga prodotto da un programma scritto lanciando in aria la tua moneta “perfetta”.

B.-Io, veramente, di codesta formula non ci ho capito nulla...

A.-Cerco di spiegartela: la probabilità che la tua moneta produca il programma p è data da 2–|p|. Quindi, se vuoi definire la probabilità che il tuo computer produca il numero n devi sommare le probabilità di tutti i programmi p che producono n ovvero tutti i programmi tali che U(p) = n.

B.-E se il programma non si ferma e quindi non produce alcun numero?


Gregory Chaitin

A.-Non c’è niente di male: dato che esiste questa possibilità, se poniamo:

risulta Ω < 1. Ω è proprio la probabilità che un programma casuale si fermi. Il numero Ω si chiama numero di Chaitin e ha importanti proprietà aritmetiche legate a certe equazioni diofantee... ma non divaghiamo troppo...

B.-Anche perché, volendo dire tutta la verità, si finisce con il parlare di cose troppo difficili che neppure tu conosci...

A.-Torniamo alla nostra formula. Si può dimostrare che:


e quindi la probabilità a priori di un numero differisce di pochissimo da 2–I(n).

B.-E quindi quasi tutti i numeri sono casuali ma ci sono dei numeri che, avendo leggi nascoste, hanno una maggiore probabilità di altri di essere prodotti dal “caso” e quindi hanno una maggiore probabilità di “esistere”. Ma questa è cabalistica. Pitagora sarebbe stato felicissimo e i maghi del Medioevo avrebbero fatto salti di gioia.

A.-Non prendermi in giro.

B.-Non ti sto prendendo in giro. Anzi, mi sto divertendo molto. Facciamo un po’ di cabalistica. Prendiamo un numero magico; per esempio il numero di Avogadro. I chimici dicono che sia N = 6, 28x1023. Ma N non può essere il vero numero di Avogadro perché è comprimibile; bastano 9 simboli per divenirlo Il vero numero di Avogadro deve certamente essere casuale. Sarà il più grande numero casuale minore di N. Perché non me lo calcoli?

A.-È facile ottenere un numero o una stringa casuale, ma è difficile dimostrare che essi sono casuali. In un certo senso, si può soltanto dimostrare che una stringa non è casuale.

B.-Come sarebbe a dire?

 

3.5. Il paradosso di Berry ed il teorema di Chaitin


A.-Intuitivamente è molto semplice: una stringa non è casuale se ha una regola nascosta. Se trovi tale regola, allora non è casuale. Se invece non trovi nulla, non sai se la tua stringa è casuale oppure se devi cercare ancora... e ancora... e ancora… e non sai mai quando fermarti.

B.-Ma esisterà certamente un metodo sistematico per stabilire se una stringa è casuale. In fondo, tutti i computer di questo mondo hanno “zippatori”.

A.-Ora sei tu che fai uso di brutti neologismi: “zippatore” fa più schifo della parola “stringa”.

B.-Ma tutti sanno che uno zippatore è un programma che permette di comprimere un “file” e, poiché un file non è altro che una stringa, uno zippatore mi permette di stabilire se una stringa è casuale o no.

A.-I tuoi zippatori funzionano solo perché i file che si usano sono ben lontani dall’essere casuali.

B.- E chi ti dice che io non possa, magari tra 30 anni, inventare lo zippatore perfetto?

A.-Me lo dice il teorema di Chaitin. È un fatto della vita che la perfezione non esiste e qualche volta questo fatto si può dimostrare. Così non ci saranno più illusi come te che cercano la “pietra fifilosofale”.

B.-Allora, se vuoi spezzare definitivamente le mie illusioni, spiegami il teorema di Chaitin.

A.-Non è altro che la versione informatica del paradosso di Berry.

B.-E cosa dice il paradosso di Berry?

A.-Parla di numeri e della loro definibilità mediante “parole”. Per esempio le proposizioni:

il più grande numero primo minore di cento il più piccolo numero perfetto il numero ottenuto moltiplicando i primi dieci numeri primi tra di loro sono proposizioni che definiscono rispettivamente i numeri 97, 6 e 6.915.878.970. Adesso considera la seguente proposizione:

@ Il minimo numero intero che, per essere definito, richieda più simboli di quanti ce ne sono in questa proposizione.

B.-Bene, fin qui ti seguo. Un tale numero esisterà certamente: dato un qualunque insieme di numeri naturali, il minimo esiste sempre!

A.-Ma ne sei proprio sicuro?

B.-Certo, ci sono moltissimi teoremi che derivano dal fatto che un sottoinsieme degli interi ha sempre un minimo.

A.-E sei anche sicuro che i numeri descrivibili “a parole” formino un insieme?

B.-Certamente!

A.-Allora supponiamo che tale numero esista e chiamiamolo β: il numero di Berry. Poiché la proposizione “@” contiene 115 simboli (contando anche gli spazi vuoti), ciò vuol dire che per definire β ci vogliono almeno 116 simboli.

B.-Benissimo, il tuo ragionamento non fa una grinza.

A.-Ma dimentichi una cosa: la proposizione “@” contiene 115 simboli e definisce il numero β.

B.-Gasp!

A.-Cosa hai detto?

B.-Ho detto “Gasp!” che vuol dire “sono confuso, stupito e non capisco più nulla”.

A.-Non è proprio il caso che ti stupisca tanto. I paradossi e le antinomie, in Logica come in Matematica, esistono fin da quando è stato inventato il ragionamento astratto cioè dai tempi dell’antica Grecia. In genere, nascono dall”’autoreferenza” cioè dal disporre di un linguaggio che può parlare di se stesso.

B.-Come quando l’Autore di questo articolo ha citato se stesso.

A.-Più o meno. Pensa, per esempio, al paradosso di Epimenide: se uno dice “io mento”, se mente veramente, dice la verità; ma, se dice la verità, allora mente. Con l’autoreferenza si possono trovare tutte le antinomie che vuoi.

B.-Sarà, ma questo numero β‚ lo digerisco proprio male. Comunque, penso che queste antinomie siano molto stupefacenti dal punto di vista logico ma che sia molto difficile applicarle a situazioni pratiche come quelle riguardanti computer e programmi. Un programma è un programma. È una cosa concreta che si “vede” e non può essere troppo legato alle astrazioni tipo quelle amate dai Greci che, nonostante il loro genio teorico, dal punto di vista tecnologico non erano poi un gran che.

A.-Ti sbagli, perché antinomie e paradossi, opportunamente interpretati, ti dimostrano che certe cose non si possono fare. Stabiliscono le colonne d’Ercole che separano il possibile dall’impossibile. Come, ad esempio, il paradosso di Berry. Tradotto nel mondo dei computer, diviene un teorema: il teorema di Chaitin, che stabilisce che con un programma P contenente una quantità di informazione I(P) = k non si può comprimere (in modo ottimale) una stringa avente un’informazione maggiore di k bit.
Per “tradurre” il paradosso nel teorema, occorre spostare l’accento dal campo dell’esistenza a quello della dimostrabilità. L’espressione che richieda deve essere sostituita da che si può provare che richieda. Inoltre la vaga nozione di numero di simboli può essere rimpiazzata dalla informazione algoritmica che è una quantità ben definita e misurabile in bit. Usando questi accorgimenti, la “@” diventa:

@@ il programma che è capace di provare che una stringa ha complessità algoritmica maggiore del numero di bit contenuti in questo programma.

Se il programma P esistesse, usandolo come subroutine, si potrebbe facilmente costruire il programma @@ che ha una quantità di informazione poco superiore a quella di P, diciamo k + k1 ed opera nel seguente modo:

  • prende tutte le stringhe ordinate lessicograficamente;

  • le comprime usando la subroutine P;

  • misura la loro quantità di informazione cioè la lunghezza della stringa compressa;

  • se trova che questa è maggiore di k +k1, stampa questa stringa e si ferma.

In altre parole, il programma @@ ha prodotto una stringa x che ha informazione algoritmica maggiore di k + k1 ovvero U(@@) = x con I(x) > k + k1. Ma, dalla definizione di informazione, si ha:


e dunque si ha l’assurdo: k + k1< k + k1. Ma, mentre il paradosso di Berry ti ha soltanto fatto meravigliare, il teorema di Chaitin ti insegna anche che non può esistere lo zippatore perfetto.