>>>>>

Scheda 8 - Caso, informazione e algoritmi

5. ALGORITMI e definizione di SUCCESSIONE CASUALE. Il teorema di INCOMPLETEZZA di Godel-Chaitin.

    Riprendiamo il discorso avviato in §2. Fissiamo un linguaggio di programmazione L e una codifica binaria Cod di L. Scriviamo [s] e len(s) al posto di Cod(s) e lunghezza di s. Sia w una stringa.

    La complessità di w è n (I(w) = n) se:

  1)  esiste un programma P di L che ha come output w

  2)  len([P]) = n.

  3)  n è il minimo numero naturale tale che valgano 1) e 2)

Osservazione: data una generica stringa esistono infiniti programmi in grado di generarla (ad es., preso comunque un programma che la genera, basta aggiungere delle istruzioni "inutili").

    L'approccio al concetto di casualità che abbiamo delineato in §2 è stato sviluppato negli anni '60 da Chaitin e Kolgomorov indipendentemente l'uno dall'altro. Grosso modo, essi proposero di considerare casuale una stringa se la sua complessità è approssimativamente uguale alla lunghezza della sua codifica binaria:  I(w) ≈ len([w]), cioè se la sua descrizione non può essere "compressa" in modo sostanziale.

    L'avverbio "approssimativamente" corrisponde sia al fatto che I(w) dipende dalla scelta di L e Cod (di questo aspetto si è già discusso in §2), sia al fatto che è opportuno accettare un certo scarto tra complessità e lunghezza in bit:

–   presi come L la versione di Qbasic discussa in §2 e il codice Ascii, la stringa 1000110 ha come programma minimale PRINT "1000110", che è lungo 8 caratteri (64 bit) in più;

–   invece la stringa (che scriviamo su più righe per facilitarne l'esame):
100011000001100111100
100011000001100111100
1100001111110010010001110110000101110110
ha:
x$="100011000001100111100":
PRINT x$+x$+"1100001111110010010001110110000101110110"
come programma minimale; è un programma più corto della stringa; per quanto questa stringa venga allungata con altri 0 e 1 che costituiscano una sequenza non descrivibile in modo compresso, la presenza del segmento iniziale 100011000001100111100100011000001100111100 fa sì che l'intera stringa risulti essere comunque comprimibile.

    Per le stringhe "infinite" si può dare la definizione:

una successione infinita di caratteri si dice casuale (secondo Chaitin) se esiste k numero naturale t.c. per ogni segmento iniziale w della successione: I(w) > len([w]) – k (cioè se nessuna porzione iniziale può essere compressa più di un certo tot, ossia se la differenza relativa tra lunghezza e complessità di w tende a 0 al crescere della dimensione del segmento iniziale w).

    In questo modo l'eventuale comportamento iniziale "non casuale" non pregiudica la possibilità che la successione sia considerata casuale se è tale il suo comportamento "all'infinito".

[il variare di L e di Cod non modifica l'esistenza o meno di k, ma solo il suo eventuale valore; infatti è possibile mettere a punto meccanismi automatici di traduzione da un linguaggio all'altro e da una codifica all'altra]

    Se fissiamo in n il numero dei caratteri utilizzabili per costruire stringhe, le considerazioni svolte a proposito dell'entropia (vedi secondo punto dopo il quesito 3) ci fanno supporre che, per stringhe di dimensioni sufficientemente grandi, quelle in cui i caratteri sono presenti più o meno con la stessa frequenza, avendo un contenuto informativo maggiore, siano più "casuali" (cioè richiedano programmi più lunghi) di quelle in cui alcuni caratteri sono molto più frequenti di altri. In effetti si può dimostrare che:

•   se una successione di caratteri è casuale secondo Chaitin il carattere che compare in un posto della successione è stocasticamente indipendente dal carattere che compare al posto successivo e la frequenza relativa in un segmento iniziale w di ogni carattere tende a 1/n al tendere all'infinito della lunghezza di w.

    A questo punto è chiaro (ma ciò aveva già cominciato a emergere in §2) che non si sta matematizzando il concetto di successione genericamente casuale (cioè non deterministica), ma, in qualche modo, di successione "massimamente" casuale (nessun carattere privilegiato, elementi indipendenti l'uno dall'altro, …). È stata messa a punto (da Kolgomorov e Loveland) una definizione più generale, che corrisponde a quella che tentava di dare von Mises (successione di caratteri per cui le frequenze relative dei vari caratteri tendono a stabilizzarsi su valori non necessariamente uguali; vedi §1). Per una successione "genericamente" casuale sarebbe sufficiente richiedere che non esista alcun programma (senza file) in grado di generarla.

    L'insieme dei programmi costruibili in un determinato linguaggio di programmazione L ha cardinalità numerabile: sono un sottoinsieme dell'insieme di espressioni (di lunghezza finita) generabili con una quantità finita di simboli, insieme che è numerabile (posso numerare le espressioni lunghe 1, poi le espressioni lunghe 2, poi quelle lunghe 3, … ). Le successioni (con caratteri estratti da un alfabeto di cardinalità n) sono in quantità più che numerabile (pensandole come parte frazionaria di numeri reali rappresentati in base n e inizianti con "0.", si ha immediatamente che hanno la stessa cardinalità dell'intervallo [0,1) di IR). Quindi esiste una quantità più che numerabile di successioni non generabili con un programma, cioè di successioni "genericamente" casuali.

5

  La successione delle cifre di un numero irrazionale è casuale?

    Questa formalizzazione del concetto di sequenza casuale permette anche di ottenere facilmente una versione molto generale del Teorema di Incompletezza, cioè di esprimere in modo molto generale i limiti intrinseci dei sistemi formali.

    Supponiamo di disporre di un sistema formale S per dimostrare formule del tipo I(w)>n (supponiamo che il sistema sia "corretto", cioè che se in S è derivabile una formula allora effettivamente accada che quella formula è vera). Allora esiste un numero naturale N tale che non è possibile dimostrare in S alcuna formula del tipo I(w)>n con n>N.

Dimostrazione. Idea: argomentazione con "autoriferimento".

•  In accordo con le richieste di "calcolabilità" dei sistemi formali (avere procedimenti meccanici per stabilire se un'espressione è una formula o no, per stabilire se una formula è un assioma, … per realizzare le inferenze), se p_i è l'i-esima prova rispetto a un dato ordinamento delle prove, possiamo ritenere realizzabile un programma P che implementi il seguente algoritmo, in cui N è un numero naturale fissato:

(1)  x=N

(2)  i=1

(3)  se p_i dimostra una formula del tipo I(w)>n con n>x fermati con output w, se no poni i=i+1 e vai a (2)

In altre parole P trova (se esiste) una stringa w che si possa dimostrare essere di complessità maggiore di N.

•  Supponiamo che P dia un output w. Per definizione di complessità deve essere: I(w)≤len([P]).

•  Posso sicuramente prendere N in modo che len([P])<N: infatti len([P]) è pari a k+len[N], dove k è la somma delle lunghezze delle codifiche di "x=", di (2) e di (3), e la differenza tra un numero N e la lunghezza della sua codifica len[N] (che cresce come log N) tende all'infinito.

•  Allora: I(w)≤len([P]))<N. Ma – vedi passo (3) – dovrebbe essere anche I(w)>N: assurdo.

•  Quindi per tali N P non può arrestarsi e dare un output w, ma deve entrare in un loop (2)-(3) senza fine, cioè non esistono prove in S di formule del tipo I(w)>n con n>N.

    Quindi in un sistema formale è possibile determinare la complessità solo di stringhe non troppo lunghe e "casuali".

Nota. Il fattore limitativo (N) dipende dalla parte (3) di P che a sua volta dipende dalla "dimensione" del sistema formale.

    In particolare non è possibile dimostrare che una successione infinita di caratteri è casuale.