%% This document created by Scientific Word (R) Version 2.0




 
\documentclass[12pt]{article}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{sw20jart}%
%
%
%\input italian.doc%
%
%TCIDATA{TCIstyle=Article/art4.lat,jart,sw20jart}%
%
%TCIDATA{OutputFilter=Latex.dll}%
%TCIDATA{LastRevised=Sun Oct 04 11:37:12 1998}%
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}%
%TCIDATA{Language=American English}%
%
%\input tcilatex%
%
\begin{document}%
%
\author{Vieri Benci}%
\title{Chiacchierata \\%
sulla teoria algoritmica \\%
dell'informazione}%
\maketitle%
%
\bigskip\ %

{\it Ho deciso di scrivere questa nota introduttiva alla teoria%
algoritmica dell' informazione nella forma di dialogo per almeno tre motivi.}%

{\it Il primo \`e per renderla pi\`u agevole e divertente ad un lettore%
che potrebbe venire scoraggiato da un articolo scritto in modo sistematico:%
con la forma del dialogo si susseguono domande e risposte e quindi diventa%
pi\`u facile seguire il filo logico. }%

{\it Il secondo motivo nasce dal fatto che io non sono un esperto di%
questa teoria. Mettendo le varie affermazioni nelle bocche dei signori A. e%
B., posso tranquillamente dissociarmi dalle loro affermazioni qualora si%
dovessero rivelare esposte in modo approssimativo ed un po' impreciso.}%

{\it La terza motivazione sta nel fatto che questi due signori sono%
giovani studenti ed in quanto tali hanno tutto il diritto di fare galoppare%
la loro fantasia, diritto che non si addice a un professore. Noi tutti siamo%
disposti a perdonare le loro estrapolazioni anche quando sono un po' troppo%
ardite, ma un professore deve essere una persona seria (anche quando diventa%
noioso).}%

{\it Naturalmente esiste anche il rovescio della medaglia: questi due%
signori non sempre si esprimono in buon italiano. Mescolano vocaboli%
tecnico-scientifici con parole del gergo studentesco e qualche volta usano%
vocaboli troppo coloriti che fanno disonore al mondo accademico: ma anche%
all'Universit\`a se ne vedono di tutti i colori e bisogna rassegnarsi. }%

\


{\bf  Prologo }


B.- Ciao, come ti va la vita all'Universit\`a.%

\

A.- Ma....le lezioni sono abbastanza noiose...%

\
B.- Allora facevi meglio a restare al Liceo.%

\

A.- Per\`{o} si incontrano persone interessanti e si parla di molte cose,%
anche fuori dei corsi ufficiali. Per esempio, parlando con alcuni compagni e%
con i professori ho scoperto una teoria molto interessante che risponde%
anche ad alcune questioni filosofiche che ti dovrebbero interessare.%

\

B.- E qual'\`e questa teoria?%

\

A.- Si chiama teoria algoritmica dell'informazione.%

\

B.- Che nome complicato.%

\

A.- S\`\i , il nome \`e complicato ma i fondamenti della teoria sono%
abbastanza semplici.%

\

B.- Ma io la posso capire?%

\

A.- S\`\i , se hai un po' di pazienza.%

\

B.- Allora spiegamela.%

\


{\bf \large Cos'\`e il caso}%
%

\

{\bf L'indovinello}%

\

A.- Va bene. Te la spiego con un indovinello. Considera queste due stringhe: %
\[%
S_1="0001000100010001000100010001000100010001" %
\]%
\[%
S_2="1110010111001101101011010011001111101101". %
\]%


La domanda \`e la seguente%

\begin{center}%
''quale delle due stringhe \`e casuale?''%
\end{center}%


B.- Stai parlando delle stringhe delle tue scarpe?%


A.- Non fare lo spiritoso ed il purista della lingua italiana; sai bene che%
oggi si usa la parola ''stringa'' per denotare una successione finita di 0 e%
di 1. Ammetto che \`{e} una brutta traduzione della parola inglese {\it %%
string }ma con tutti questi {\it computer} che girano, ormai \`{e}%
entrata a fare parte della lingua parlata.%

B.- Ed anche scritta visto che qualcuno ha scritto questo articolo.%

A.- Non divagare e rispondi alla mia domanda.%

\

{\bf Complessit\`a}%

\

{\it Dopo avere osservato per pochi secondi queste due stringhe il signor%
B da la sua risposta.}%

B.- Mi sembra che la tua domanda sia demenziale, \`e ovvio che la stringa%
casuale \`e la $S_2$%

A.- Se la mia domanda \`e demenziale, lo \`e di pi\`u la tua risposta%
perch\`e non mi hai dato alcuna motivazione.%

B.- E' ovvio che la prima stringa non \`e casuale perch\`e segue una {\it %%
regola} ben precisa: \`e formata da tre ''0'' ed un ''1'' che si ripetono%
per dieci volte.

A.- Ma anche la seconda stringa potrebbe avere una {\it regola nascosta}.%
Per esempio si potrebbe ottenere con la seguente regola %
\begin{eqnarray*}%
&&\mbox{prendi il decimo numero primo}, \\%
&&\mbox{sommaci la mia et\`a,} \\%
&&\mbox{inverti l'ordine delle cifre, sommaci 7 se il numero \`e pari, o%
moltiplicalo per 8 } \\%
&&\mbox{se il risultato \`e un numero dispari,} \\%
&&\mbox{converti il numero ottenuto in notazione binaria,} \\%
&&\mbox{e cos\`\i\ otterrai la stringa }S_2%
\end{eqnarray*}%

Sei sicuro che la seconda stringa non segua questa regola?%

B.- No! Non sono sicuro e non ho affatto voglia di fare il conto.%

A.- Neanche io, ma posso sostenere senz'altro che la stringa $S_2$ segue%
certamente qualche regola nascosta, perch\`e essendoci infinite regole, essa%
pu\`o senz'altro essere ottenuta mediante alcune di esse.%

B.- Questo \`e certamente vero, ma la $S_1$ segue una regola semplice e con%
questo ti ho fregato.%

A.- Bravo! Hai fatto centro...basta che tu mi definisca quando una regola si%
dice semplice.%

B.-Una regola \`e semplice...quando si capisce subito.%

A.-E chi ti dice che la $S_2$ non segua una regola che io ho capito subito%
quando l'ho scritta.%

B.- Con regola semplice...voglio dire una regola che non \`e {\it %%
complessa.}%

A.- In questo modo hai semplicemente cambiato nome ai termini del problema.%
Hai sostituito la parola {\it complessit\`a} alla parola {\it %%
casualit\`a.\ }Possiamo convenire che la {\it casualit\`a} e la {\it %%
complessit\`a }sono due concetti strettamente collegati ma non hai risposto%
alla mia domanda iniziale. Se ti fa piacere a questo punto ti riformula la%
ta domanda con i termini che preferisci:%

\begin{center}%
''quale delle due stringhe $S_1$ e $S_2$ \`e pi\`u complessa?''%
\end{center}%

\

{\bf Probabilit\`a}%

\

{\it Il signor B rimane un po' interdetto e si mette a riflettere; allora%
l'amico riprende la parola}.%

A.- Ti voglio aiutare. Una di queste stringhe l'ho prodotta con questa%
moneta. L'ho lanciata in aria per 40 volte ed ho scritto un ''1'' quando mi%
\`e venuto testa ed uno ''0'' quando mi \`e venuto croce. Questa%
informazione ti aiuta? Sai dirmi quale delle due stringhe $S_1$ e $S_2$ \`e%
stata prodotta col metodo del lancio di una moneta?%

B.- Ovviamente la $S_2.$%

A.- Perch\'e?%

B.- Perch\`e per ottenere una stringa come la $S_1$ avresti dovuto passare%
qualche secolo a lanciare monete.%

A.- Oppure potrei avere avuto molta fortuna....%

B.- ...ma vai....%

A.- Ammetto che la $S_2$ \`e stata prodotta col metodo del lancio di una%
moneta, ma tu non mi hai ancora risposto alla domanda iniziale.%

B.- Adesso la risposta \`e semplice; la stringa casuale \`e la seconda,%
perch\`e \`e stata prodotta con un metodo casuale, cio\`e il lancio della%
tua moneta.%

A.- Veramente tu hai risposto ad un'altra domanda: quale delle due stringhe%
\`e stata prodotta casualmente, non quale \`e casuale.%

B.- Ma \`e la stessa cosa.%

A.- Non \`e vero infatti non lo potrai mai provare. Lancia questa moneta e%
vediamo se ti viene la stringa $S_2.$%

B.- Non fare lo spiritoso, sai che questo \`e impossibile; ognuna di queste%
due stringhe ha la stessa probabilit\`a di uscire che \`e 2$^{-40}.$%

A.- Da questo punto di vista le due stringhe sono equivalenti. Ognuna di%
esse ha la probabilit\`a di essere prodotta con lanci casuali di uno su 1%
trilione e 99 miliardi 511 milioni 627 mila 776.%

B.- Sempre minore del debito pubblico.%

A.- Non divagare. Tu non hai ancora risposto alla mia domanda per almeno due%
motivi: io voglio sapere se una delle due stringhe possa ritenersi casuale%
in se stessa e non per il modo in cui \`e stata prodotta; inoltre se tu usi%
nozioni probabilistiche devi spiegarmi cosa intendi per probabilit\`a.%

B.- Ma sai bene che la probabilit\`a \`e un concetto essenzialmente%
indefinibile. Hanno versato fiumi di inchiostro per definire la%
probabilit\`a ed ogni definizione di probabilit\`a (frequentista,%
soggettivista etc.) si \`e sempre prestata ad un mare di obiezioni.%

A.- E' proprio qui che ti volevo. Se tu definisci quale delle due stringhe%
\`e casuale in un certo senso definisci cos'\`e il caso, ovvero il%
fondamento della nozione di probabilit\`a.%

B.- Spiegami un po' meglio questo concetto....%

A.- Prendiamo nuovamente questa moneta. Tu dici che la probabilit\`a che%
esca testa o croce \`e esattamente 1/2. Questo perch\`e 1/2 \`e l'inverso%
del numero degli eventi possibili purch\`e questi eventi siano {\it %%
equiprobabili}.%

B.- E questa \`e una definizione circolare in quanto usi il concetto di equi-%%
{\it probabilit\`a }per definire la {\it probabilt\`a}.%

A.- Proprio cos\`\i . Quindi dobbiamo avere un criterio per sapere se le%
uscite di testa o croce di questa moneta sono equiprobabili. Che cosa%
diresti se lanciando questa moneta ottenessi la stringa $S_1$?%

B.- Direi che la tua moneta \`e truccata.%

A.- Dunque, per sapere se la mia moneta \`e un oggetto i cui lanci si%
comportano in maniera casuale devo sapere che cosa \`e una stringa casuale.%

B.- In pratica questo va bene, ma dal punto di vista astratto no; infatti da%
un punto di vista puramente teorico, non si pu\`o escludere che la stringa $%%
S_1$ sia stata ottenuta col lancio della moneta.%

A.- Hai ragione, ma solo in parte. Infatti la stringa $S_1$ ha una qualche%
probabilit\`a di essere prodotta a caso solo perch\`e \`e molto corta. Basta%
che tu la prenda un po' pi\`u lunga e la probabilit\`a diventer\`a%
praticamente 0. Per esempio, producendo una stringa al secondo, per ottenere%
una data stringa di 60 caratteri, non basta l'et\`a dell'universo.%

B.- Va bene, ma dal punto di vista teorico, tra 2$^{-40}$ e 2$^{-60}$\ non%
cambia nulla.%

A.- Ma lo sai che sei pi\`u pedante di un matematico...%

B.- Non mi dire che non sai rispondere alla mia domanda.%

A.- Ma non essere sciocco. Io so rispondere a tutte le tue domande perch\`e%
sono un personaggio inventato dall'Autore proprio con questo scopo. Per%
evitare il problema che tu dici basta prendere stringhe casuali infinite e%
sviluppare il calcolo delle probabilt\`a come ha fatto Von Mises pi\`u di 50%
anni fa.%

B.- Ma allora la tua teoria \`e pi\`u vecchia di 50 anni.%

A.- No, perch\`e Von Mises ha basato la nozione di probabilt\`a su quella di%
successione casuale, ma non \`e riuscito a dare una buona nozione di stringa%
casuale. Con questa teoria invece si pu\`o definire che cos'\`e una%
successione casuale: basta che ogni segmento iniziale della successione sia%
una stringa casuale.....%

B.- Va bene! Ti do atto che tu sai tutto, ma smettila di usare parole troppo%
difficili perch\`e tanto non ci capisco nulla.%

A.- Bene. Allora ragioniamo pi\`u alla buona. Se io ti mostro le stringhe $%%
S_1$ e $S_2\;$e ti dico che una di esse \`e stata prodotta a caso mi dici%
che questa stringa \`e la $S_2$ ma non sai il perch\`e.%

B.- Questo \`e vero, ma solo perch\`e non ho studiato statistica.%
Altrimenti, potrei applicare uno dei molti test statistici e darti una%
risposta definitiva.%

A.- Anche questo non \`e vero. Tu sai che un {\it computer}$\,$%
qualsiasi, anche con un programmino molto semplice, riesce a produrre%
stringhe casuali che resistono alla maggior parte dei test statistici. Ma%
queste stringhe non sono casuali perch\`e sono prodotte da un programma%
determistico, infatti vengono chiamate stringhe (o successioni) {\it %%
pseudocasuali.}%

B.- Ma almeno in linea di principio si pu\`o ammettere l'esistenza di test%
statistici che smascherino tutte le stringhe pseudocasuali.%

A.-Certo, ma per fare una distinzione appropriata tra stringhe casuali e%
pseudocasuali devi avere gi\`a definito che cosa intendi per stringhe%
casuali, altrimenti come fai a smascherare le pseudocasuali?%

B.- Allora siamo ritornati alla domanda iniziale.%

A.- Certamente: perch\`e la $S_2$ \`e casuale?%

B.- Ma allora come stanno le cose?%

A.- A questo punto della nostra discussione abbiamo appurato che ricorrere a%
nozioni probabilistiche per rispondere alla domanda iniziale non aiuta%
affatto, perch\`e per dare una definizione non assiomatica di probabilit\`a%
devi gi\`a sapere che cos'\`e una stringa casuale per distinguerla da una%
pseudocasuale. Quindi devi definire la casualit\`a in maniera intrinseca. Se%
riesci a fare ci\`o, non solo sai che cos'\`e una stringa casuale, ma dai un%
fondamento accettabile al calcolo delle probabilit\`a.%

\

{\bf Quantit\`a di informazione}%

\

B.- Mi \`e venuta un'altra idea per definire la casualit\`a di una stringa.%

A.- E quale?%

B.- Nessuna stringa \`e casuale. Tutto segue una regola. Ci\`o che esiste,%
esiste per necessit\`a. Come dice Hegel ci\`o che \`e reale \`e razionale.%
Quello che esiste, esiste per volont\`a di Dio e niente pu\`o essere%
lasciato al caso. Ci\`o che noi chiamiamo caso \`e solo la misura della%
nostra ignoranza...%

A.- ...e magari \`e frutto del demonio, una prova dell'esistenza di Satana.%
Non essere ridicolo, lo so che sei bravo in filosofia, ma noi vogliamo fare%
un discorso terra terra e non \`e il caso di scomodare Dio. Vogliamo sapere%
solo perche la $S_2$ \`e causale e la risposta, anche se \`e concettualmente%
profonda, deve essere formalmente semplice.%

B.- Io mi sono gi\`a scocciato. Dimmi quello che sai e basta.%

A.-Supponi che io voglia comunicare la mia stringa ad un amico che%
vive...sulla luna e che le trasmissioni tra qui e la luna costino molto care%
e pertanto mi conviene rendere il mio messaggio il pi\`{u} corto possibile%
per risparmiare. Se voglio trasmettere la stringa $S_{1}$ basta che%
trasmetta il messaggio %
\[%
0001%
\]%
che mi ''prende'' 4 bit, ed il messaggio di ripeterlo 10 volte, che mi%
prende altri 4 bit in quanto 10 in numerazione binaria si scrive ''1010''.%
Dunque posso trasmettere la mia stringa con 8 bit di informazione. %

Per trasmettere invece la stringa $S_{2}$ non posso fare altro che%
trasmettere ogni simbolo alla volta ed impiegare 20 bit.%

B.- Ma devi anche trasmettere le regole per ricostruire il messaggio spedito%
in forma abbreviata.%

A.- D'accordo, ma se parliamo di stringhe lunghe, l'informazione per%
trasmettere tali regole \`e irrilevante.%

B.- Dunque tu dici che una stringa \`{e} casuale se l'informazione%
necessaria per ricostrurla \`{e} di tanti bit quanto \`{e} la lunghezza%
della stringa.%

A.- Pi\`u o meno.%

{\it Il signor B. riflette un poco.}%

B.- Aspetta un momento! Tu mi stai fregando. L'informazione necessaria per%
trasmettere un messaggio dipende da quello che sa la persona che riceve il%
messaggio. Se io voglio trasmettere sulla luna il quinto canto della Divina%
Commedia, non devo trasmetterlo verso per verso. Basta che trasmetta la%
frase 
\[%
\mbox{Il V canto della divina Commedia} %
\]%
ed il mio interlocutore sulla luna va nella bibliteca di Selenia (capitale%
della colonia lunare) e se lo legge.%

A.- Ma bisogna ammettere che il tuo interlocutore sulla luna non sappia%
nulla.%

B.- Se non sa nulla non pu\`o capire nessun messaggio.%

A.- D'accordo, bisogna ammettere che sappia molto poco....%

B.- Quanto poco; adesso sei tu che usi concetti non non definiti e fai una%
gran confusione per risolvere una questione che appare evidente a priori.%

A.- Hai ragione. Adesso ti spiego tutto con ordine.%

\

{\bf \large Teoria algoritmica dell'informazione}%

\

{\bf Come si misura la quantit\`a di informazione?}%

\

A.- Hai presente che cos'\`e una macchina di Turing universale?%

B.- Certamente no, lo sai bene che al Liceo queste cose non ce le spiegano.%

A.- E' vero; in realt\`a molte volte questi concetti non sono insegnati%
neppure all'Universit\`a.%

{\it Il signor A. mostra all'amico un disegno di una macchina di Turing%
che appare come una scatola con un quadro munito di una lancetta che segna%
gli stati interni; essa poggia su una finestrella nella quale scorre un%
nastro simile a quello degli antichi telegrafi. Accanto si vede una tabella%
che schematizza il funzionamento della macchina.}%

B.- Mamma mia, o cos'\`e?...un ibrido tra un macina-caff\`e ed il computer%
di Matusalemme?!%

A. - Ma no! Questo e 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 tu sei scemo. Ho ben altro da fare che studiarmi la tua tabella.%

A.- Comunque non ha importanza perch\`e al posto di una macchina di Turing%
universale si pu\`o sostituire il tuo computer con un semplice linguaggio di%
programmazione.%

B.- Come per esempio il Basic che \`e l'unico linguaggio che conosco?%

A.- S\`\i , 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; io posso immaginarmi un computer con memoria infinita,%
ma non posso immaginare 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; e siccome non si pu\`o sapere a priori la%
memoria necessaria, si deve supporre che gli si possa aggiungere un po' di%
memoria tutte le volte ci\`o si renda necessario.%

B.- Ho capito; \`e come quando in un compito di esame si pu\`o sempre%
richiedere nuovi fogli bianchi quando si sono esauriti i fogli che ci hanno%
dato precedentemente.%

A.- Hai capito benissimo. Una macchina di Turing si dice universale se pu\`o%
''simulare'' ogni altra macchina di Turing. I computer che noi usiamo sono%
macchine di Turing universali, infatti puoi mettergli dentro il linguaggio%
che ti pare: Pascal, Basic, Lisp. E ciascuno di questi linguaggi pu\`o%
simulare un qualsiasi altro linguaggio.%

B.- Bene; fin qui ci arrivo.%

A.- Allora supponiamo che tu ed il tuo amico sulla luna abbiate due computer%
con lo stesso linguaggio di programmazione. Allora se tu vuoi fare in modo%
che sul display del tuo amico compaia la stringa $S_{1}$ basta che tu%
spedisca il seguente messaggio:%

\begin{eqnarray*}%
\mbox{for }n &=&1\mbox{ to 10} \\%
&&\ \mbox{print ''0001''} \\%
&&\ \mbox{next}%
\end{eqnarray*}%

Questo messaggio \`e pi\`u corto del messaggio%

\[%
\mbox{print}\;"0001000100010001000100010001000100010001"%
\]%
in quanto le parole ''print'', ''next'' etc. vengono codificate da pochi bit.%

A questo punto, si pu\`o definire la quantit\`a di informazione contenuta in%
una qualunque stringa come la lunghezza del pi\`u corto programma che%
produce quella stringa.%

Una volta fissata una macchina di Turing universale $U$, o per dirlo in%
parole povere, una volta fissato il linguaggio di programmazione, la%
quantit\`a di informazione contenuta in una stringa $S$ risulta essere un%
numero intero ben definito. Esso sar\`a denotato col simbolo %
\[%
I_U(x). %
\]%

In simboli possiamo scrivere %
\[%
I_U(x)=\min \left\{ \left| p\right| \mid U(p)=x\right\} %
\]%
ove $\left| p\right| $ denota la lunghezza del programma $p$ (cio\`e 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\`a di informazione viene a dipendere dal linguaggio di%
programmazione scelto, cio\`e da $U$.%

A - Questo \`e vero; ma questa dipendenza non \`e troppo grave. Infatti, se $%%
V$ \`e un altro linguaggio di programmazione, risulta che %
\[%
\left| I_U(x)-I_V(x)\right| \leq C(U,V) %
\]%
ove $C(U,V)$ \`e una costante che dipende da $U$ e $V$ ma non dalla stringa.%
Quindi, se cambi programma, la quantit\`a di informazione risulta modificata%
solo di una quantit\`a finita. Questo fatto ci garantisce che la quantit\`a%
di informazione \`e un buon concetto e la dimostrazione, dovuta a%
Kolmogorov, tralasciando alcuni dettagli tecnici \`e molto immediata e te la%
voglio dire.%

Infatti, supponiamo che sia %
\[%
I_U(x)=l; %
\]%
ci\`o significa che esiste un programma $p_{U,x}$, di lunghezza $l$, che,%
fatto girare nella macchina $U$ produce la stringa $x:$%%
\[%
U(p_{U,x})=x. %
\]%

Ora, vuoi scrivere un programma che ti produce la stringa $x$ con la%
macchina $V$, basta che tu abbia il programma $p_{V,U}$ che permette di%
simulare la macchina $U$ con la $V$, e poi dai alla macchina $V$ il%
programma $p_{U,x}$ e cos\`\i\ otterrai la stringa $x$: %
\[%
V(p_{V,U},\;p_{U,x})=x %
\]%

Probabilmente questa non \`e la maniera migliore di ottenere la stringa $x$%
dalla macchina $V$; quasi certamente il programma pi\`u corto $p_{V,x}$%
sar\`a diverso dal programma $(p_{V,U},\;p_{U,x})$; denotando con $\left|%
p\right| $ la lunghezza di un programma si ha che %
\[%
\left| p_{V,x}\right| \leq \left| p_{V,U}\right| +\left| p_{U,x}\right| %
\]%
e quindi %
\[%
\left| p_{V,x}\right| -\left| p_{U,x}\right| \leq \left| p_{V,U}\right| ; %
\]%
ma questa formula resta valida se scambiamo $U$ con $V$ e quindi %
\[%
\left| p_{U,x}\right| -\left| p_{V,x}\right| \leq \left| p_{U,V,}\right| ; %
\]%
da cui segue che %
\[%
\left| \left| p_{V,x}\right| -\left| p_{U,x}\right| \right| \leq \max%
(\left| p_{V,U}\right| ,\left| p_{U,V,}\right| ). %
\]%

Poich\`e abbiamo definito %
\[%
I_U(x)=\left| p_{U,x}\right| %
\]%
e %
\[%
I_V(x)=\left| p_{V,x}\right| , %
\]%
ponendo %
\[%
C(U,V)=\max (\left| p_{V,U}\right| ,\left| p_{U,V,}\right| ) %
\]%
il teorema di Kolmogorov risulta dimostrato.%

B. - E quindi la quantit\`a di informazione contenuta in una stringa \`e un%
concetto ben definito, a meno di una costante. In fondo \`e abbastanza%
naturale pensare che la quantit\`a di informazione contenuta in una stringa%
non \`e proporzionale alla sua lunghezza, ma \`e una cosa indipendente che%
in un modo o nell'altro possa essere definita rigorosamente. Per\`o...credo%
di avere perso il filo del discorso; stavamo parlando di complessit\`a e di%
casualit\`a. Adesso siamo approdati ad una nozione abbastanza diversa.%

A.- Bene possiamo riepilogare tutti i passaggi: una stringa si dice {\it %%
casuale} se non ha regole nascoste che la possano rendere pi\`u 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). Infatti si pu\`o definire%
formalmente la quantit\`a di informazione (chiamata anche complessit\`a nel%
senso di Kolmogorov) contenuta in una stringa; a questo punto, una stringa,%
pu\`o essere definita casuale se il suo contenuto di informazione $I(x)$ \`e%
pi\`u o meno uguale alla lunghezza $\left| x\right| $ della stringa stessa.%

B.- Ho capito; ma che cosa vuol dire ''pi\`{u} o meno uguale''? Questa non %
\`{e} certo una asserzione matematica.%

A.- Certamente; bisogna dare una valutazione quantitativa. Per motivi%
tecnici si \`e deciso di definire $x$ \`e casuale se %
\[%
I(x)\geq \left| x\right| -\log _2\left| x\right| %
\]%
Per esempio, se una stringa con un milione di caratteri non \`e casuale,%
pu\`o essere prodotta da una stringa un po' pi\`u corta, ovvero da una%
stringa di soli %
\[%
1.000.000-\log _21.000.000\simeq %
\]%
\[%
\simeq 1.000.000-19,931\simeq %
\]%
\[%
\simeq 999.980 %
\]%
caratteri.%

\

{\bf 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 2$^N$ stringhe di%
lunghezza $N$. Quelle che non sono casuali possono essere prodotte da%
stringhe appeno un po' pi\`u corte, ovvero da stringhe di lunghezza $N-\log%
_2N$. Ma le stringhe di questa lunghezza sono al pi\`u %
\[%
2^{N-\log _2N}=\frac{2^N}N %
\]%
e quindi le stringhe casuali sono almeno %
\[%
2^N-\frac{2^N}N=(1-\frac 1N)2^N. %
\]%
Dunque, tra le stringhe di un milione di caratteri, solo un milionesimo di%
esse possono essere non casuali, il 99,9999\% sono certamente casuali.%

B. - Ma allora \`e facile avere stringhe casuali. Anche considerando%
stringhe di solo cento caratteri, almeno il 99\% di esse sono casuali.%

\

{\bf Numeri casuali}%

\

A. E quindi la stragrande maggioranza dei numeri sono casuali.%

B.-E adesso cosa c'entrano i numeri?%

A. Poich\`{e} le stringhe possono essere poste in corrispondenza biunivoca%
con i numeri naturali secondo la seguente tabella (ordine lessicografico) %
\[%
\begin{array}{ccc}%
0 &  & 0 \\ %
1 &  & 1 \\ %
00 &  & 2 \\ %
01 &  & 3 \\ %
10 &  & 4 \\ %
11 &  & 5 \\ %
000 &  & 6 \\ %
001 &  & 7 \\ %
010 &  & 8 \\ %
011 &  & 9 \\ %
100 &  & 10 \\ %
..... &  & ....%
\end{array}%
\]%
ne segue che ogni numero naturale pu\`{o} essere intrinsecamente casuale. Un%
numero $n$ si dice casuale se %
\[%
I(n)\geq \log _{2}(n)-\log _{2}\log _{2}(n)%
\]%

B. -Vacci piano; non ti seguo.%

A. -In base alla tabella, parlare di numeri naturali o di stringhe \`e la%
stessa cosa.....%

B. - .....e cos\`\i\ 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\`{o} sempre essere rappresentato con $%%
\log _{2}(n+2)$ simboli. Ma esso pu\`{o} anche avere delle regole nascoste;%
per esempio il numero %
\[%
6.915.878.970%
\]%
\`{e} il prodotto dei primi 10 numeri primi. Usando queste regole nascoste%
si pu\`{o} scrivere un programma che produce il numero $n$ sul display del%
tuo computer. La lunghezza del pi\`{u} corto di questi programmi si denota%
con $I(n)$ ed \`{e} il contenuto di informazione di $n.$%

Quindi non solo ti ho spiegato cos'\`e una stringa casuale, ma anche cosa%
\`e 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\`o definire%
cos'\`e 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\`u o meno%
quasi tutti equiprobabili ....%

A.- Io non ho detto che quasi tutti i numeri sono equiprobabili; la%
probabilit\`a a priori di un numero \`e un altra cosa...%

\

{\bf Probabilit\`a a priori di un numero}%

\

B.- Non mi dire che con la tua teoria si pu\`o anche definire la%
probabilit\`a a priori di un numero o di un qualunque altro ogggetto. Ti%
posso dare ragione quando dici che puoi definire cos'\`e una stringa%
casuale, ma per definire la probabilit\`a penso che ''il vecchio lancio%
della moneta'' resti il metodo pi\`u efficiente, o almeno il pi\`u%
intuitivo; e poich\`e i numeri sono infiniti, la nozione di numero casuale%
mi sfugge.%

A.- E cosa mi diresti se io affermassi che la probabilit\`a a priori di un%
numero $n$ non \`e altro che %
\[%
P(n)=2^{-I(n)} %
\]%

B.- Direi che \`e una definizione come un'altra, ma non mi sembra%
minimamente correlata alla idea intuitiva di probabilit\`a che abbiamo ''a%
priori''. A meno che tu non abbia argomenti per convincermi.%

A.- Certo che ce l'ho. Altrimenti non avrei portato in ''ballo'' questa%
questione. Tu mi dici che sei ancora affezionato al vecchio buon ''lancio%
della moneta''. Bene supponiamo di avere la tua moneta perfetta, lanciamola%
e vediamo qual'\`e la probabilit\`a che mi dia un certo numero.%

B.- Se tu codifichi i primi 2$^{30}$ numeri in un qualunque modo e fai%
trenta lanci, \`e chiaro che ogni numero ha la stessa probabilit\`a che \`e 2%%
$^{-30}.$ E ci\`o resta vero anche se sostituisci la moneta con una stringa%
casuale di 30 caratteri.%

A.- Ma non correre, io non voglio fare trenta lanci, voglio fare infiniti%
lanci. O meglio voglio fare $N$ lanci e tenere conto di tutte le possibilt%%
\`{a} che esistono qualunque sia il numero $N.$%

B. - Forse sto capendo....Fammi indovinare: guardando la tua tabella si%
pu\`o dire che il numero 0 e il numero 1 hanno probabilit\`a $\frac 12$%
poich\`e possono essere ottenuti con un lancio con probabilit\`a $\frac 12$;%
i numeri 2, 3, 4 e 5 hanno probabilit\`a $\frac 14$ perch\`e possono essere%
ottenuti con due lanci con probabilit\`a $\frac 14$...%

A.- Guarda che la somma delle probabilt\`a di ciascun evento indipendente%
deve essere uguale ad 1 e tu con soli sei numeri hai gia raggiunto il numero%
2: %
\[%
P(0)+P(1)+P(2)+P(3)+P(4)+P(5)= %
\]%
\[%
=\frac 12+\frac 12+\frac 14+\frac 14+\frac 14+\frac 14=2 %
\]%

B.- Ma basta che poi divida per un fattore di normalizzazione (che in questo%
caso \`e 2) ed ottengo %
\[%
P(0)=P(1)=\frac 14 %
\]%
\[%
P(2)=P(3)=P(4)=P(5)=\frac 18 %
\]%

A. - La tua idea \`{e} buona se vuoi definire la probabilit\`{a} a priori di%
una quantit\`{a} finita di numeri; ma se vuoi considerare tutti i numeri il%
tuo fattore di normalizzazione diventa %
\[%
2\cdot \frac{1}{2}+4\cdot \frac{1}{4}+8\cdot \frac{1}{8}+.....=1+1+1+.....=%%
\infty %
\]%

B.- Gi\`a \`e 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\`a considerata un programma e messa in%
una maccina di Turing universale e aspetti il risultato. Questa volta la%
somma delle probabilit\`a di ciascun numero ti verr\`a minore (o al pi\`u%
uguale) a uno, almeno se tu 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 a priori di un%
numero \`e definita da %
\[%
P(n)=\sum_{U(p)=n}2^{-\left| p\right| } %
\]%
ovvero la probabilit\`a a priori di un numero \`e uguale alla probabilit\`a%
che questo numero venga prodotto da un programma scritto lanciando in aria%
la tua moneta ''perfetta''.%

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

A.- Cerco di spiegartela: la probabilit\`{a} che la tua moneta produca il%
programma $p$ \`{e} data da $2^{-\left| p\right| };$ quindi se vuoi definire%
la pobabilit\`{a} che il tuo computer produca il numero $n$ devi sommare le%
probabilit\`{a} di tutti i prorammi $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?%

A. - Non c'\`{e} niente di male: dato che esiste questa possibilit\`{a}, se%
poniamo %
\[%
\Omega =\sum_{n=0}^{\infty }P(n),%
\]%
risulta che $\Omega <1.\,\Omega $ \`{e} proprio la probabilit\`{a} che un%
programma casuale si fermi. Il numero $\Omega $ si chiama numero di Chaitin%
ed ha importanti propriet\`{a} aritmetiche legate a certe equazioni%
diofantee...ma non divaghiamo troppo....%

B. - Anche perch\`e, volendo dire tutta la verit\`a, si finisce col parlare%
di cose troppo difficili che neppure tu conosci....%

A. - Torniamo alla nostra formula; si pu\`o dimostrare che %
\[%
\sum_{U(p)=n}2^{-\left| p\right| }\simeq \max \left\{ 2^{-\left| p\right|%
}\mid U(p)=n\right\} %
\]%
e quindi la probabilit\`a 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 probabilt\`a di altri di essere%
prodotti dal ''caso'' e quindi hanno una maggiore probabilit\`a di%
''esistere''. Ma questa \`e cabalistica. Pitagora sarebbe stato felicissimo%
e i maghi del Medioevo avrebbero fatto salti di gioia.%

A.- Non prendermi in giro.%

B.- Non ti sto prendendi 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 esso sia %
\[%
N=6,28\cdot 10^{23}.%
\]%
Ma $N$ non pu\`{o} essere il vero numero di Avogadro perch\`{e} \`{e}%
comprimibile; bastano 9 simboli per definirlo. Il vero numero di Avogadro%
deve certamente essere casuale. Esso sar\`{a} il pi\`{u} grande numero%
casuale minore di $N$.%

Perch\`e non me lo calcoli?%

A.- E' facile ottenere un numero o una stringa casuale, ma \`e difficile%
dimostrare che essi sono casuali. In un certo senso si pu\`o soltanto%
dimostrare che una stringa non \`e casuale.%

B.- O come sarebbe a dire?%

\

{\bf Il paradosso di Berry ed il teorema di Chaitin}%

\

A. - Intuitivamente \`e molto semplice: una stringa non \`e casuale se ha%
una regola nascosta; se tu trovi tale regola, allora essa non \`e casuale.%
Se invece non trovi nulla non sai se la tua stringa \`e casuale oppure se%
devi cecare ancora...e ancora...e ancora...e non sai mai quando fermarti.%

B.- Ma esister\`{a} certamente un metodo sistematico per stabilire se una%
stringa \`{e} casuale. In fondo, tutti i computer di questo mondo hanno%
''zippatori''.%

A- Ora sei tu che fai uso di brutti neologismi; il nome ''zippatore'' fa%
pi\`u schifo della parola ''stringa''.%

B.- Ma tutti sanno che uno zippatore \`e un programma che permette di%
comprimere un ''file'' e poich\`e un file non \`e altro che una stringa, uno%
zippatore mi permette di stabilire se una stringa \`e casuale o no.%

A.- I tuoi zippatori funzionano solo perch\`e 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. E' un fatto della vita che la%
perfezione non esiste, e qualche volta questo fatto si pu\`o dimostrare e%
cos\`\i\ non ci saranno illusi come te che cercano la ''pietra filosofale''.%

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

A.- Esso non \`e 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\`a mediante ''parole''. Per%
esempio le proposizioni%

\begin{itemize}%
\item  il pi\`{u} grande numero primo minore di cento.%

\item  il p\`{u} piccolo numero perfetto%

\item  il numero ottenuto moltiplicando i primi dieci numeri primi tra di%
loro%
\end{itemize}%

sono proposizioni che definiscono rispettivamente i numeri 97, 6 e%
6.915.878.970.%

Adesso considera la seguente proposizione:%

\begin{itemize}%
\item[@]  Il minimo numero intero che, per essere definito, richieda pi\`{u}%
simboli di quanto ce ne sono in questa proposizione.%
\end{itemize}%

B. Bene fin qui ti seguo. Un tale numero esister\`a certamente; infatti dato%
un qualunque insieme di numeri naturali il minimo esiste sempre.%

A.- Ma ne se proprio sicuro?%

B.- Certo, altrimenti la matematica sarebbe contraddittoria: 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 $\beta $: il%
numero di Berry. Poich\`e la proposizione ''@'' contiene 115 simboli%
(contando anche gli spazi vuoti), ci\`o vuol dire che per definire $\beta $%
ci vogliono almeno 116 simboli.%

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

A.- Ma tu dimentichi una cosa: la proposizione ''@'' contiene 115 simboli e%
definisce il numero $\beta .$%

B.- Gasp!%

A.- Cosa hai detto?%

B.- Ho detto ''Gasp!'' il che vuol dire ''sono confuso, stupito e non%
capisco pi\`u nulla''.%

A.- Non \`e proprio il caso che tu ti stupisca tanto; i paradossi e le%
antinomie in logica come in matematica esistono fino da quando \`e stato%
inventato il ragionamento astratto, cio\`e dai tempi dell'antica Grecia. In%
genere, esse nascono dall'''autoreferenza'', cio\`e dal disporre di un%
linguaggio che pu\`o parlare di se stesso.%

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

A.- S\`\i , pi\`u o meno le cose stanno cos\`\i . Pensa per esempio al%
paradosso di Epimenide: se uno dice: %
\[%
\mbox{''io mento'',} %
\]%
se mente veramente, dice la verit\`a, ma se dice la verit\`a allora mente.%
Con l'autoreferenza si possono trovare tutte le antinomie che vuoi.%

B.- Sar\`{a}, ma questo numero $\beta $ lo digerisco proprio male. Comunque%
penso che queste antinomie sono molto stupefacenti dal punto di vista%
logico, ma che sia difficile applicarle a situazioni pratiche come quelle%
riguardanti computer e programmi. Un programma \`{e} un programma: \`{e} una%
cosa concreta che si ''vede'' e non pu\`{o} 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\`e 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, esso diviene un teorema, il teorema di%
Chaitin che stabilisce che con un programma $P$ contenente una quantit\`{a}%
di informazione %
\[%
I(P)=k%
\]%
non si pu\`{o} 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\`{a}. L'espressione ''che%
richieda'' deve essere sostituita da ''che si pu\`{o} provare che%
richieda''. Inoltre la vaga nozione di ''numero di simboli'' pu\`{o} essere%
rimpiazzata dalla ''informazione algoritmica'' che \`{e} una quantit\`{a}%
ben definita e misurabile in bit. Usando questi accorgimenti, la ''@''%
diventa%

\begin{description}%
\item[@@]  il programma che \`{e} capace di provare che una stringa ha%
complessit\`{a} algoritmica maggiore del numero di bit contenuti in questo%
programma.%
\end{description}%

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

\begin{quote}%
prende tutte le stringhe ordinate lessicograficamente,%

le comprime usando la subroutine $P$,%

misura la loro quantit\`a di informazione cio\`e la lunghezza della stringa%
compressa,%

e se trova che questa \`e magggiore di $k+k_1$ stampa questa stringa e si%
ferma.%
\end{quote}%

In altre parole il programma @@ ha prodotto una stringa $x$ che ha%
informazione algoritmica maggiore di $k+k_1,$ ovvero $U(@@)=x$ con %
\[%
I(x)>k+k_1. %
\]%
$.$%

Ma dalla definizione di informazione, si ha che %
\[%
I(x)=\min \left\{ \left| q\right| \mid U(q)=x\right\} \leq \left| @@\right|%
=k+k_1 %
\]%
e dunque si ha che %
\[%
k+k_1<k+k_1. %
\]%

Assurdo.%

Ma mentre il paradosso di Berry ti ha soltanto fatto meravigliare, il%
teorema di Chaitin ti insegna anche che non pu\`o esistere lo zippatore%
perfetto.%

\

{\bf \large Un po' di filosofia}%

\

{\bf La versione informatica del teorema di G\"odel}%

\


B.- Ma allora la tua teoria algoritmica dell'informazione non serve quasi a%
nulla; in pratica non si pu\`o mai sapere se una stringa \`e casuale.%
Tutt'al pi\`u si pu\`o solo sapere quello che non si ha speranza di scoprire.%

A.- Anche fosse cos\`\i\ non sarebbe poco...%

B.- ....a proposito di quello che non si pu\`o mai sapere....questi discorsi%
mi fanno venire in mente il teorema di G\"odel, quello che dice che in%
aritmetica ci sono cose vere che non possono essere dimostrate...%

Questa teoria ha qualcosa a che vedere col teorema di G\"odel?%

A.- S\`\i , questa teoria ha molto a che vedre col teorema di ''{\it %%
incompletezza}'' di G\"odel. Chaitin stesso ha dato molte dimostrazioni%
''informatiche'' di questo teorema.%

Ti voglio raccontare in modo un po' intuitivo di cosa si tratta. Torniamo%
all'aritmetica, alla cabalistica come dici tu.%

Prendiamo un numero $m$ e vediamo se ha regole nascoste, ovvero, se pensato%
come stringa, esso \`e comprimibile. Questo fatto non pu\`o essere%
dimostrato con un programma $p$ che ha un contenuto di informazione minore%
di $I(m).$%

B.- Ma noi, almeno in linea di principio, possiamo prendere programmi lunghi%
quanto ci pare e alla fine scopriremo se $m$ \`e o non \`e un numero casuale.%

A.- Certo. Ma ora seguimi un po' in questo ragionamento. Se tu scegli un%
numero finito di assiomi e formalizzi tutte le regole di inferenza di una%
teoria matematica (per esempio l'aritmetica), otterrai un ''programma'' che%
ha un contenuto di informazione magari grande, ma finito.%

B.- Tu vuoi dire che il mio libro di matematica potrebbe essere ridotto ad%
un programma.%

C.- Certo. Un programma, chiamiamolo $\mathcal{L}$, al quale, come input dai%
un' enunciato, e come output aspetti una risposta: questo enunciato \`e vero%
(cio\`e \`e un teorema) oppure questo enunciato \`e falso. Basta che tu%
formalizzi bene le regole di inferenza, e il tuo programma pu\`o produrre%
tutti i teoremi e verificare se essi sono uguali all'enunciato dato, oppure%
sono uguali alla sua negazione. A questo punto il programma ti da la%
risposta e si ferma.%

Il teorema di G\"odel\ ti dice che un tale programma non pu\`o esistere, ma%
questo fatto te lo dice anche il teorema di Chaitn.%

B.- Certo ed ho capito anche perch\'e. Infatti basta prendere l'enunciato%

\begin{center}%
''il numero $m$ \`e casuale''.%
\end{center}%

Se la quantit\`a di informazione contenuta in $m$ \`e maggiore di quella di $%%
\mathcal{L}$ (ossia della quantit\`a di informazione contenuta in assiomi e%
regole di inferenza) sicuramente, per il teorema di Chaitin, non potrai mai%
ricevere la risposta.%

A.- Bravo, le cose stanno proprio cos\`\i .%

B.- Accidenti! Ho capito il teorema di G\"odel che \`e considerato%
difficilissimo.%

A.- Non ti gasare troppo; in realt\`a noi abbiamo saltato tutti i dettagli%
tecnici. Comunque, per me, c'\`e una cosa ancora pi\`u sorprendente: preso%
un qualunque numero %
\[%
m>I(\mathcal{L}), %
\]%
nonostante che quasi certamente sia casuale, sappiamo con assoluta certezza%
che non lo possiamo dimostrare. In altre parole sono pi\`u le cose che non%
sappiamo di quelle che sappiamo.%

B.- Questo veramente non \`e una grande novit\`a, Socrate lo aveva predicato%
pi\`u di 2000 anni fa.%
%
A.- Gi\`a, ma la novit\`a consiste nel fatto che questo vale per semplici%
propriet\`a aritmetiche. Se noi, con un computer potentissimo e con un%
programma $p$ con %
\[%
I(p)>m %
\]%
riuscissimo a provare che $m$ \`e casuale, questo fatto andrebbe assunto%
come assioma indipendente.%

B.- E allora?%

A.- Ma non capisci; se questo \`e vero, viene distrutto il vecchio%
pregiudizio che la matematica sia un sistema assiomatico deduttivo. In%
realt\`a essa \`e una scenza empirica.%

B.- Come!!!%

A.- La maggior parte delle verit\`a verificate da un semplice modello come%
l'insieme dei numeri naturali, non possono essere dedotte da un sistema%
finito di assiomi, anche se potrebbero essere verificate con altri mezzi;%
proprio come capita nelle scienze empiriche: una teoria, qualunque essa sia,%
non ti permette di prevedere tutto. Ci sono sempre fatti che le sfuggono e%
che richiedono che la teoria venga ampliata. In Aritmetica, quello che \`e%
dato a priori \`e l'insieme dei numeri naturali, ma le verit\`e che li%
riguardano, non possono essere dedotte da un insieme finito di assiomi e di%
regole di inferenza. E quindi l'Aritmetica \`e una scienza sperimentale.%

B.-Ma vai, ora sei tu che mi prendi in giro.%

A.-Un po' s\`{i} e un po' no. In realt\`{a}, a questo proposito Chaitin ha%
proposto di introdurre la nozione di incerezza in Matematica ed accettare%
enunciati del tipo:%

\begin{quote}%
''il teorema tal dei tali ha una probabilit\`a a priori del 99\% di essere%
vero''.%
\end{quote}%

B.-Adesso capisco perch\`e mi hai detto che la teoria algoritmica%
dell'informazione ha conseguenze filosofiche.%

\

{\bf L'epistemologia di Salomonoff}%

\


A.- No! in realt\`a quando ho detto questo stavo pensando all'epistemologia%
di Salomonoff.%

B.- Ma come, non ti basta di aver gi\`a tirato in ballo la probabilit\`a,%
l'informatica, l'aritmetica, la logica e la critica dei fondamenti? Ora tiri%
fuori anche l'epistemologia? E chi \`e questo signor Salomonoff.%

A.- Insieme a Kolmogorov e a Chaitin \`e il padre di questa teoria. Anzi \`e%
il primo ad averne scoperto i punti essenziali. Ma fino a quando Kolmogorov%
non li ha riscoperti nessuno ci aveva fatto caso.%

Comunque lui \`e arrivato a questa teoria attraverso altre motivazioni. Egli%
voleva trovare un criterio per sapere, almeno virtualmente, quale, tra due%
teorie scientifiche fosse la migliore.%

Salomonoff ha pensato di rappresentare le osservazioni di uno scienziato%
mediante una successione di cifre binarie.%

B.-Ed ecco che siami tornati ancora una volta alle stringhe.%

A.-Alla teoria spetta il compito di ''spiegare'' le osservazioni e di%
predirne delle nuove. Quindi una teoria scientifica pu\`o essere considerata%
come un programma che permette ad un computer di riprodurre le osservazioni.%

Se tra due teorie si deve scegliere la migliore quale sceglieresti tu?%

B.-E' ovvio, quella pi\`u corta, quella capace di zippare maggiormente i%
dati empirici. Tutto questo \`e molto bello, ma la teoria non \`e nuova, \`e%
la vecchia storia del rasoio di Occam: tra due teorie equivalenti si sceglie%
quella pi\`u semplice tagliando via i fronzoli inutili.%

A.-Certo che \`e la vecchia teoria del rasoio di Occam, ma formulata%
matematicamente. E questo fatto la fa uscire dalla filosofia delle opinioni%
per farla approdare ad una epistemologia adatta alla scienza dei nostri%
giorni.%

B.- Certo questa storia non sar\`a molto apprezzata da Popper il quale%
sostiene che il valore conoscitivo di una teoria scientifica si misura dalla%
sua falsificabilit\`a.%

Se ci sono due teorie in competizione e se queste teorie sono scentifiche,%
deve esserci la possibilit\`a di fare un ''esperimento cruciale'' che%
falsifichi una delle due e quindi stabilisca quale delle due \`e ''pi\`u%
vera''. Se questa possibilit\`a non esiste, non siamo pi\`u nel mondo della%
scienza ma della metafisica.%

A.- Non so cosa pensino i popperiani, ma ti posso dire quello che penso io.%
A me pare che il criterio di scientificit\`a proposto da Popper sia%
estremamente riduttivo. Per esempio niente della matematica sarebbe una%
teoria scientifica; o forse lo sarebbe la geometria Euclidea, in seguito ad%
accurate misurazioni relative agli enunciati dei suoi teoremi. E non solo la%
matematica sarebbe esclusa dal mondo della Scienza, ma anche molte teorie%
quali la teoria dell'evoluzione naturale, la teoria del big-bang, la teoria%
della deriva dei continenti, l'astronomia,...%

B.- Forse hai ragione. In fondo la scienza moderna \`e nata con la%
rivoluzione Copernicana, e Copernico, a fare gli esperimenti, non ci pensava%
nemmeno. Per lui la teoria eliocentrica era ''vera'' solo perch\`e zippava%
le osservazioni fatte dagli astronomi nei 2000 anni precedenti. E ora che ci%
penso anche Kepler, ha sostituito le ellissi agli epicicli perch\`e con%
pochi parametri riusciva a descrivere le posizioni dei pianeti con%
altrettanta accuratezza; e se anche teniamo conto delle osservazioni%
successive, aumentando opportunamente il numero degli epicicli si sarebbe%
potuto descrivere il moto di qualunque pianeta con l'accuratezza desiderata.%

A.-Vorresti dire che Kepler \`e stato il pi\`u grande zippatore della Nuova%
Scienza?%

B.-Ma anche Galileo non schezava mica..... Ma come la mettiamo con il fatto%
che non si pu\`o sapere quando una stringa \`e zippabile.%

A.- Vuoi dire qual'\`e il significato epistemologico del teorema di Chaitin?%
In fondo ci dice quello che il buon senso ci ha sempre detto: non si pu\`o%
sperare di avere un algoritmo che ci permette di trovare in ogni occasione%
la teoria ottimale. La scoperta di una buona teoria \`e frutto di lavoro,%
intelligenza, intuizione e molta fortuna.%

B.- Vuoi dire che il cervello umano con {\it lavoro, intelligenza,%
intuizione e molta fortuna }riesce a fare quello che un computer non riesce%
a fare?%

\

{\bf  La tesi di Church}%

\

A.- Questo ovviamente non lo sa nessuno. Ma possiamo provare a formulare%
meglio il problema mediante la tesi di Church.%

B.- Che ovviamente io non so che cosa sia....%

A.- Church \`e un signore che \`e considerato il maggior logico di questo%
secolo dopo G\"odel. Mentre G\"odel ha dimostrato che esistono cose vere che%
non possono essere dimostrate, Church ha provato che non esiste alcun metodo%
per sapere se una cosa \`e dimostrabile.%

B.- Per favore cerca di precisare meglio quello che intendi perch\`e non ti%
sto capendo.%

A.- Considera un sistema formale, ovvero un linguaggio, degli assiomi e%
delle regole di inferenza. Il tutto deve essere perfettamente formalizzato:%
questo in pratica vuol dire che tutto il lavoro potrebbe essere fatto da un%
computer. Inoltre il nostro sistema formale deve ''contenere'' una teoria%
abbastanza ricca: diciamo l'aritmetica. Dandogli tempo infinito, questo%
computer dovrebbe essere capace di stampare tutti i teormi.%

B.- Fin qui ti seguo.%

A. Bene! G\"odel ti di dice che certe proposizioni non saranno mai stampate.%
N\`e loro n\`e le loro negazioni. Dunque, aggiungendoci un po' di fantasia%
si pu\`o dire che certe cose non sono n\`e vere, n\`e false. Questo fatto si%
esprime dicendo che il sistema \`e {\it incompleto}.%

B.- E Church cosa dice.%

A.- Dice che non esiste una {\it procedura di decisione}, ovvero, per%
sapere se una cosa \`e dimostrabile o no, non ti resta altro che aspettare%
che il computer stampi quella proposizione o la sua negazione. Fino alla%
fine del tempo. Non c'\`e alcun metodo generale che ti permetta di sapere a%
priori quali sono i teoremi dimostrabili. L'unico mezzo a disposizione \`e%
quello di provare a dimostrarli, ma se non ci riesci, non puoi dedurre%
nemmeno che non sei abbastanza bravo.%

B.- Per\`o, da come io vedo le cose, mi sembra che sia dal teorema di%
G\"odel che dal teorma di Church non si possano trarre troppe conseguenze%
filosofiche. G\"odel e Church hanno provato che tutti i sistemi formali sono%
incompleti e mancano di una procedura di decisione. Ma questo \`e come dire%
che in geometria Euclidea non si pu\`o quadrare il cerchio o trisecare%
l'angolo. In realt\`a queste costruzioni sono possibili; basta aggiungere%
qualche nuovo marchingegno alla riga e al compasso. Analogamente, \`e%
possibile inventare qualche nuovo strumento, per esempio un supercomputer%
parallelo, oppure, ampliare le regole del gioco per poterne sapere di pi\`u%
sulle verit\`a aritmetiche. In fondo potrebbe capitare di tutto; chissa come%
stanno le cose?%

A.- In realt\`a sembra proprio che questo ampliamento non sia possibile;%
infatti Turing usando la sua macchina ideale, con metodi completamente%
diversi \`e giunto proprio alla stessa conclusione. E questo fatto ha%
portato Church a suggerire che qualunque effettiva computazione (o%
dimostrazione) operata da uomini e macchine poteva essere duplicata dall'%%
{\it uomo ideale} o dalla {\it macchina ideale} e questa \`e la famosa%
tesi di Church. E' una affermazione empirica, ma l'evidenza a suo favore \`e%
schiacciante. Poich\`e ogni operazione fatta da una macchina ideale o da un%
uomo ideale pu\`o essere fatta da una macchina di Turing universale, la tesi%
di Church-Turing pu\`o essere riformulata cos\`\i :%

\begin{center}%
''Tutto quello che pu\`o essere calcolato,%

pu\`{o} essere calcolato da una macchina di Turing''%
\end{center}%

o se ti fa pi\`{u} piacere, pensando alla Matematica,%

\begin{center}%
''Tutto quello che pu\`o essere dimostrato,%

pu\`o essere dimostrato da una macchina di Turing''%
\end{center}%

ovvero, pensando alle scienze empiriche e all'epistemologia di%
Occam-Salomonoff:%

\begin{center}%
''Tutto quello che pu\`o essere zippato,%
pu\`o essere zippato da una macchina di Turing''%
\end{center}%

Ogni computer, anche il pi\`u potente non pu\`o fare niente di pi\`u di%
ci\`o che pu\`o fare una macchina di Turing universale. Ovvero, qualunque%
algoritmo pu\`o essere simulato da qualunque semplice computer, basta%
supporre che abbia memoria infinita e che si abbia la pazienza di aspettare.%

B.- Sembra impossibile che quel macinino da caff\`e possa fare tutti i conti%
e dimostrare tutti i teoremi concepibili. Ma, se le cose stanno cos\`\i ,%
allora tutto quello che vediamo e facciamo pu\`o essere simulato da una%
macchina di Turing.%

A.- Adesso non esagerare, tu non stai formulando la tesi di Church-Turing,%
ma la tesi di Church-Turing-Signor B. che recita cos\`{i}:%

\begin{center}%
''Tutto quello che pu\`o essere calcolato dall'intero universo,%

pu\`{o} essere calcolato da una macchina di Turing''%

e francamente mi sembra che sia un po' troppo. In fondo l'universo \`{e}%
piuttosto grande. {\it Ci sono pi\`{u} cose in cielo e terra di quanto la%
tua filosofia possa sognare}. Nel mondo fisico ci possono essere fenomeni%
che sfuggono ad una descrizione algoritmica. Dando per buona la tesi di%
Church, ci si pu\`{o} porre la seguente domanda:%

Esiste qualche fenomeno fisico che calcola qualcosa di non-calcolabile?%
\end{center}%

B.- Ho capito dove vuoi arrivare. Stai semplicemente riformulando la mia%
domanda: pu\`o il cevello umano fare quello che un computer non riesce a%
fare, nemmeno ipoteticamente?%

A.- Proprio cos\`\i : il problema, riformulato opportunamente diventa questo:%

\begin{quote}%
''il cervello umano, con {\it lavoro, intelligenza, intuizione e molta%
fortuna,} pu\`o calcolare qualcosa che \`e (algoritmicamente)%
non-calcolabile o dimostrare qualcosa che \`e (algoritmicamente)%
non-dimostrabile o comprimere una teoria che \`e (algoritmicamente)%
non-comprimibile?''%
\end{quote}%

B.- Ho l'impressione che a questa domanda non sai rispondere neppure tu.%

A.- Hai ragione; ormai abbiamo chiacchierato anche troppo. Andiamo al bar%
della facolt\`a a farci la solita partita a Magic con il resto della%
compagnia.%

\end{document}%                      







