Readme.it in English  home page
Readme.it in Italiano  pagina iniziale
readme.it by logo SoftwareHouse.it

Yoga Roma Parioli Spedizioni Raccomandate Roma

Ebook in formato Kindle (mobi) - Kindle File Ebook (mobi)

Formato per Iphone, Ipad e Ebook (epub) - Ipad, Iphone and Ebook reader format (epub)

Versione ebook di Readme.it powered by Softwarehouse.it


Il teorema di indecidibilità

Questo teoremasi può enunciarecon qualche semplificazionecome segue:

Se un sistema formale S è consistenteallora esiste un enunciato Vvero ma non dimostrabile in S

cioè la consistenza di S implica l'esistenza di (almeno un)enunciato V vero ma non dimostrabile in S.
Prima di discutere sensatamente di questo teorema bisognerebbe definireaccuratamente il concetto di sistema formalema preferisco lasciarperdere (vedi comunque quidove scrivo 'assiomatico'invece che 'formale'). Non che la faccenda siaparticolarmente complessa manello spirito di queste paginevoglio esseredavvero semplice nei ragionamenti e devo dire cheanche se il lavorooriginale di Gödel non è poi così mostruosamente difficile come si puòessere portati a credereè senz'altro vero che tale lavoro non è semplice...Ho cercato di semplificarlo ma non ci sono riuscito (grazie!) peròanche senon sono stato abilesono stato fortunato: mi è capitato tra le mani un librodi Roger Penrose(Ombre della menteRizzoli 1996) dove viene discussa una 'versione'estremamente semplice del teorema di Gödelversione sviluppata appunto daPenroseche sfrutta il concetto di macchina di Turinge cheper essere compresanon abbisogna di tutto l'enorme apparato formale chesi trova - necessariamente - nel lavoro originale di Gödel. Qui riporteròquesta versione di Penrose con alcune modifiche cheprobabilmenteneindeboliranno la struttura formale ma checredorendono il teorema di Gödeldavvero alla portata di tutti.

Il significato del teorema

Prima di dimostrare il teorema peròcerchiamo di capiredavvero il significato di quanto dimostrato da Gödel. A prima vista sembra diaver raggiunto un limite insuperabile: ci sono affermazioni vere che sonoindimostrabilidella cui verità cioè non ci potremo maiconvincere. Giusto? Nosbagliato! Direi invece che il teorema di indecidibiltàse lo si segue con un po' di attenzioneci dice proprio il contrario! Ineffetticome vedremosi può ben dimostrare che una certa proposizioneesprimibile nel (e dipendente dal) sistema formale S è veraanche se questadimostrazione non potrà mai essere espressa nella sintassi del sistema Sstesso! InsommaGödel dimostra che l'intuito del matematico umano è in gradodi 'svincolarsi' dai limiti imposti da un qualsivoglia sistema formale percogliere delle verità che resteranno per sempre inconoscibilicome tali se si resta nei limiti del sistema.

Sistemi formali ed informatica

Per dimostrare il teorema di Gödel nella forma diTuring-Penrose si deve dapprima evidenziare il rapporto (che dovrà essere il piùstretto possibile) tra sistemi formali ed informaticaanzipiù precisamentetra la coppia di concetti:

e

Senza stare a diventar matti col formalismovediamo diconvincerci di quanto stretto possa essere questo rapporto con un esempiobanaletratto dall'ordinaria aritmetica (che qui gioca il ruolo del sistemaformale S) ed espresso in uno pseudolinguaggio che spero sia chiaro a tutti:

Linguaggio del sistema formale S:

Linguaggio dell'informatica:

Chiamiamo questo programma P0.Vediamo che in un senso ben preciso P0 dipende dalnumero intero '2'infatti nel corso della sua esecuzione ciascun numeroutilizzato 'internamente' (ab e c) viene elevato all'esponente 2.Ovvioperché l'enunciato di partenza si riferiva a numeri quadrati.Indichiamo il programma P0 agente sul numero '2' conla notazione P0(2). Come abbiamo visto P0(2)riferentesi ad un enunciato verotermina con successo. Vediamo cosasuccede con P0(1) cioè al programma analogo a P0(2)dove la condizione:

se a2=b2+c2
viene sostituita da
se a=b+c.

Il banale enunciato relativoanch'esso veroafferma cheesiste almeno un numero esprimibile come somma di due numerie P0(1)termina al secondo ciclodopo aver banalmente stampato 211.
Per trovare qualcosa di più interessante non ci occorrerà essereparticolarmente originali: P0(3) equivaleall'enunciato 'esiste almeno un cubo esprimibile come somma di due cubi' ed èun caso particolare del celeberrimo ultimoteorema di Fermat. Sappiamo quindi che l'enunciato è falso; chesuccede al nostro programma P0(3)? Behvisto che nonesiste un cubo esprimibile come somma di due cubila condizione:

se a3=b3+c3

non verrà mai soddisfattaquindi il programma nonpotrà mai stampare ab e ccontinuerà a ripetere insensatamente il cicloprogrammatoincrementando sempre ab e c e non terminerà mai!

Attenzione: questo fatto non ha niente ache vedere con le proposizioni indecidibili di Gödel: avremmopotuto essere più bravi nello scrivere il programma che realizzal'enunciato in questionee farlo terminare stampando ad esempio: 'CASOIMPOSSIBILE'. È proprio considerando programmi di questo generecheterminano quando i nostri programmi tipo P0(n)non terminanoche troveremo le proposizioni indecidibili.

Torniamo al nostro programma P0 edosserviamo chequando opportunamente generalizzato

Tutti questi enunciati realizzati da P0hanno in comune il fatto di riferirsi a tentativi di trovare un numero (di uncerto 'tipo' dipendente da n - quadratocubo...) esprimibile come somma di duenumeri del medesimo 'tipo'.
Non è difficile convincersi che è effettivamente possibile scrivere unprogramma P1 che realizza un enunciato differenteechea seconda del valore di ntermina o non termina in dipendenza del fattoche l'enunciato corrispondente a P1 relativo ad n (cioèP1(n)) sia vero o falsoe così via con P2P3eccetera.
Oraproviamo a convincerci di avere a disposizione un elenco completo di tuttigli enunciati possibili nel sistema formale S dipendenti da un solo numerocosìche i programmi Pm con m=0123... rappresentinotutti questi possibili enunciati. Come prima esprimeremo la dipendenza di Pmda n con la notazione Pm(n).
Ora chiediamoci se è possibile scrivere un gran bel programmachiamiamolo Dcheapplicato a Pm(n)sia in grado di dircisenzasbagliarese Pm(n) termina oppure no. Cosa stiamochiedendo al nostro bel programma D? Ad esempiocosa dovrebbe dirci D applicatoa P0(3)? Dopo averlo esaminato ben beneD dovrebbe terminaree dirci una cosa del tipo:

P0(3) non termina
e dovrebbe anche poterci dire
P0(4) non termina
e ancora
P0(5) non termina

e così via... InsommaD dovrebbe essere in gradoquandoapplicato ai vari P0(n) con n > 2di comportarsicome una dimostrazione dell'ultimo teorema di Fermat! Come se nonbastasse Dapplicato a P1(n)dovrebbe poter'dimostrare' allo stesso modo l'enunciato relativo al programma P1(n)e così via per P2(n)P3(n)eccetera... Insommail nostro bel programma D svolge praticamente il ruolodelle regole del sistema formale Sregole che dovrebbero essere in grado diassegnare il valore vero o falso a tutti gli enunciati (dipendentida un solo numero) esprimibili in S!
Vedremo che un tale Dindipendentemente dalla nostra bravuranon può venirscrittoe questa impossibilità è l'espressione del teorema diindecidibiltà di Gödel nella versione di Penrose-Turing.

Dimostrazione

Coerentemente con quanto detto poco soprasupponiamo diavere a disposizione i programmi Pm(n) (cherappresentano tutti i possibili enunciati del sistema formale Sdipendenti da un solo numero n) ed indichiamo l'azione di D (che rappresenta leregole di S) su Pm(n) con D(mn) e diciamo:

(G1.1)

se D(mn) termina allora Pm(n)non termina

e questo sia senza errori: se D(mn) termina allora è'davvero vero' che Pm(n) non termina.
Nostro scopo è dimostrare che D non può racchiudere il nostro concetto di veritàe questo lo otterremo trovando un ben definito programma tra i Pm(n)tale che noi sappiamo che non termina ma che D non riesce ad identificare.
A questo scopo consideriamo il valore m=n (procedura di diagonalizzazione)eotteniamo:

(G1.2)

se D(nn) termina allora Pn(n)non termina.

Ora D(nn) è un programma che dipende dal solo numero n enon più da duecome prima: sarà quindi presente nella lista dei programmi cheabbiamo costruito e che dipendono appunto da un solo numero. Diciamo che questoprogramma sia Pkcioè:

(G1.3)

D(nn) = Pk(n)

così che la (G1.2) diventa:

(G1.4)

se Pk(n) termina allora Pn(n)non termina.

Applichiamo ancora il procedimento diagonale e poniamo n=k.Otteniamo:

(G1.5)

se Pk(k) termina allora Pk(k)non termina.

Questo suona un po' come una presa per i fondelliperò sipuò concludere qualcosa di buono dalla (G1.5): chiediamoci se Pk(k)termina o noe cominciamo col supporre che termini. Dalla sconcertante (G1.5)concludiamo che se Pk(k) terminasse allora nonterminerebbee questa è una contraddizione bella e buona. Tale contraddizioneci forza a concludere che in effetti Pk(k) nontermina! Ma la (G1.3) ci dice che Pk(k) è lastessa cosa di D(kk)e allora 'anche' D(kk) non termina. Quindi il nostrobel programma D non riesce a dirci che il particolare programma Pk(k)non termina.

La conclusione è questa: abbiamo trovato il programma Pk(k)che noi sappiamo che non terminama il programma che dovrebbe avvertirci diquesto fattocioè D(kk)non è in grado di accorgersene.

Questa conclusione si può enunciare così (tra parentesi l'enunciato neitermini dei sistemi formali che - si noterà - è proprio il teorema di Gödelenunciato all'inizio):

Se il programma D(mn) non commette errori neldichiarare che un programma Pm(n) non termina(se un sistema formale S è consistente) allora esiste un programma Pk(k)che non termina e D(kk) non è in grado di dichiarare questo fatto(allora esiste un enunciato V vero ma non dimostrabile in S)

Notiamo esplicitamente che questa conclusionein un sensomolto forteè del tutto indipendente da quale D stiamo considerando.Qualunque D' possiamo trovare ha per così dire 'nascosto dentro di sé' ilprogramma che se ne fa beffe: per trovarlo basta ripetere il ragionamento appenafatto sostituendo al nostro vecchio D il nuovo D'. Nei termini dei sistemiformali in qualunque sistema formale esistono affermazioni vere ma nondimostrabili.

Alcune osservazioni conclusive