MATEMATICA - GODEL

Applicazione del teorema di Godel

Il teorema di Godel sull'incompletezza dei sistemi logici formali (matematica inclusa ovviamente) è uno dei risultati più importanti della ricerca nei settori della filosofia matematica, dell'intelligenza artificiale, della logica e di diversi altri settori scientifici.

In questa pagina questo splendido risultato verrà affrontato in maniera "leggera" ed alla portata della maggioranza delle persone, inoltre se ne mostrerà un'applicazione pratica di estrema utilità nell'ambito dell'informatica e del trattamento e comunicazioni delle informazioni in generale.

Si immagini di costruire un sistema logico formale di ragionamento (per brevità "sistema formale") ossia "... nelle scienze di logica e matematica, una teoria astratta che organizza simboli, termini e relazioni al fine di costituire la base per analizzare razionalmente fatti e poter svolgere delle deduzioni." In definitiva un sistema formale altro non è che un insieme di regole e di oggetti cui applicarle che permette ad una persona di fare considerazioni razionali su fatti, di organizzare delle idee dopo un'analisi (razionale), ecc. Si tratta della base del ragionamento razionale.

Dato che razionalità e coerenza sono cose diverse è bene anche dire che un sistema formale può essere consistente o meno. In dettaglio un sistema formale S di dice consistente se data una qualsiasi affermazione P, vera in esso, questa non può risultare contemporaneamente vera e falsa. Tale fatto non deve sorprendere! L'essere umano può "gestire" pensieri razionali ma non coerenti, si pensi alla marea di paradossi che i filosofi hanno trovato negli anni che sono trascorsi ossia ragionamenti apparentemente perfetti e razionali che conducono a conclusioni assurde ed ambivalenti. In un sistema formale consistente questo non è possibile, la matematica come ce la insegnano alle elementari è un sistema formale consistente perchè non ci sono ambivalenze, è tutto preciso ed apparentemente perfetto.

Tanto per chiudere il cerchio aggiungiamo che un sistema formale S* è corretto se si possono dimostrare solo affermazioni vere in esso (NB1: non significa che tutte le affermazioni vere in S* siano dimostrabili; NB2: S* è sicuramente consistente). Inoltre il sistema formale corretto è anche completo se qualsiasi affermazione vera in esso TRUE(P) è dimostrabile (esiste una sequenza di deduzioni logiche formali che porta a P).

Il teorema di Godel sull'incompletezza, in senso abbastanza semplificato asserisce che non esistono sistemi formali corretti e completi, ossia in ogni sistema formale consistente vi è almeno una proposizione vera TRUE(P) ma non dimostrabile logicamente.

Ossia sebbene sussista TRUE(P) neanche teoricamente è ammissibile una sequenza di deduzioni che dimostri tale fatto. Si potrebbe dire che un sistema formale non può essere auto-consistente, deve appoggiarsi, alla fine, necessariamente, su qualcosa che si sa essere vero ma non si può dimostrare, una sorta di verità assoluta!

Questo è stato un durissimo colpo per i matematici perchè tale teorema definisce in via definitiva che la matematica (la quale è un sistema formale consistente) non è assoluta come la si pensava e non si può in essa dimostrare tutto, a prescindere da quanto sia bravo lo studioso e dal livello di approfondimento degli studi che si raggiunge.

Lo stesso è stato un durissimo colpo per gli studiosi di intelligenza artificiale che ritenevano all'inizio di poter costruire macchine deduttrici logiche in grado di imbrigliare tutta la capacità razionale di un cervello umano. Si è infatti dimostrato, a partire da Godel, che le logiche proposizionali di ordine superiore al primo su cui si basavano i primi studi (si pensi alla costruzione del linguaggio di programmazione prolog) erano sistemi formali consistenti ma non completi per cui già di principio alcuni ragionamenti non potevano essere modellizzati e quindi automatizzati.

A questo punto si può studiare l'esempio applicativo.

Si va a considerare un qualsiasi sistema formale corretto Sb in cui i termini siano stringhe binarie x = "01001110..." di lunghezza finita ed in cui affermazioni tipo "x è casuale" (in logica predicativa "casuale(x)") abbia un senso ed in particolare quello che segue:

"x è casuale se la stringa x non può essere compressa in una stringa x* di lunghezza inferiore ad x" o, che è lo stesso: "la descrizione minima x* di x ha la stessa lunghezza di x" (per lunghezza di una stringa binaria si intente il numero di bit che la formano) o per finire, in logica dei predicati "casuale(x) se e solo se incomprimibile(x)".

Si supponga ora che:

a) N sia il numero di bit necessario a descrivere integralmente Sb (N potrebbe essere il numero di bit atti a descrivere tutti i caratteri di tutti i termini, i predicati e le regole di Sb).

b) sia x* una stringa binaria di lunghezza n* superiore ad N per la quale sia possibile dimostrare la casualità.

dato che per l'ipotesi (b) e la definizione di casualità impiegata la stringa x* non è comprimibile si ha che la sua rappresentazione (interna a Sb) non può essere formata da meno di n* bit e quindi da un numero di bit sicuramente maggiore di N.

Questo è un assurdo in quanto x* è un termine di Sb e come tale la sua rappresentazione ha concorso a formare il numero N.

Di seguito la dimostrazione appena svolta descritta in logica formale predicativa:

(hp0) corretto(sistema_formale(Sb))
(hp1) lunghezza(descrizione(Sb),N).
(hp2) in Sb si può dimostrare casuale(x*).
(hp3) lunghezza(descrizione(x*),n*).
(hp4) n* > N.
(r1) casuale(x*) se e solo se incomprimibile(x*).

da (hp2) ed (r1) si deduce:
--> (f1) in Sb si può dimostrare incomprimibile(x*).

da (f1) ed (hp3) ed (hp4) si deduce:
--> (f2) N < n*.

da (hp1) si deduce:
--> (f3) N = n* + k > n* (con k > 0).

(f2) ed (f3) si contraddicono --> assurdo.

Dato che c'è un assurdo possono essere false alcune delle ipotesi ed è interessante la disamina che ne consegue (tralasciando (hp0) ed (hp1) per ovvi motivi):

IPOTESI DI FALSITA' SU HP2:

Se (hp2) è falsa vorrebbe dire che non è mai possibile dimostrare la proprietà casuale(x) per stringhe binarie la cui lunghezza (finita) sia superiore a quella della descrizione del sistema formale in cui si sta operando (questo non vuole però dire che non possano esistere stringhe x per le quali TRUE(casuale(x)) ma semplicemente non sarebbe possibile dimostrarlo).

Nulla potrebbe essere detto per stringhe la cui lunghezza sia inferiore ad N. In definitiva per casuale(x) si può dire che è un'affermazione in Sb sistema formale corretto, la quale può risultare vera ma non dimostrabile ossia un esempio concreto del risultato evidenziato dal teorema di Godel.

IPOTESI DI FALSITA' SU HP4:

Si può falsificare (hp4) andando a considerare delle sequenze binarie x di lunghezza infinita su un sistema formale Sb la cui descrizione è anch'essa di lunghezza infinita. In questo caso la condizione (hp4) perde di senso così come il concetto di incomprimibilità e la stessa dimostrazione.

In definitiva questo significa che la proprietà di casualità per sequenze binarie di lunghezza finita è totalmente differente da quella omonima per sequenze infinite.

IPOTESI DI FALSITA' SU R1:

La regola R1 crea un equivalenza tra casualità ed incomprimibilità della sequenza (finita). Si potrebbe ipotizzare che ciò non sia vero ossia che anche per sequenze finite (per quelle infinite si è già visto non essere vero) casualità non significhi incomprimibilità. In tal caso la lunghezza della descrizione minima di una sequenza x potrebbe non coincidere con la lunghezza della sequenza stessa e ciò comprometterebbe la validità della dimostrazione presentata.

Se casualità ed incomprimibilità per sequenze binarie finite sono proprietà differenti allora casuale(x) in Sb non è detto che sia un esempio concreto del teorema di Godel.

***

marcomattiucci.it

Matematica: