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

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

Il teorema di indecidibilità

Questo teoremasi può enunciarecon qualche semplificazionecome segue:

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:

• enunciato in un sistema formale
• sua dimostrazione

• programma per calcolatore
• sua esecuzione

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:

• enunciato:
  esiste almeno un numero quadrato esprimibile come somma di due quadrati
• dimostrazione:
  ne esistono infiniti: Vedi il problema delle ternepitagoriche

• programma per calcolatore:

  a=1; b=1; c=1.ripeti da qui:se a2=b2+c2 allora stampa abc; terminaaltrimenti poni a=a+1.se a2<b2+c2 allora poni a=a+1altrimenti se b<c allora poni b=b+1altrimenti poni c=c+1.:fino a qui.

• sua esecuzione:
  prova: dopo aver ripetuto il ciclo per 9 voltenel corso della decima ilprogramma 'stampa' 534 e termina. In effetti è vero che 5²=3²+4².

Chiamiamo questo programma P₀.Vediamo che in un senso ben preciso P₀ 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 P₀ agente sul numero '2' conla notazione P₀(2). Come abbiamo visto P₀(2)riferentesi ad un enunciato verotermina con successo. Vediamo cosasuccede con P₀(1) cioè al programma analogo a P₀(2)dove la condizione:

se a2=b2+c2

se a=b+c.

Il banale enunciato relativoanch'esso veroafferma cheesiste almeno un numero esprimibile come somma di due numerie P₀(1)termina al secondo ciclodopo aver banalmente stampato 211.
Per trovare qualcosa di più interessante non ci occorrerà essereparticolarmente originali: P₀(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 P₀(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!

Torniamo al nostro programma P₀ edosserviamo chequando opportunamente generalizzato

• P₀(1) realizza l'enunciato banalmente vero'esiste un numero somma di due numeri'.
  Tale programma termina
• P₀(2) realizza l'enunciato vero relativoall'esistenza di terne pitagoriche.
  Tale programma termina
• P₀(n) con n>2 realizza l'enunciato falsocorrispondente all'ultimo teorema di Fermat.
  Tale programma non termina

Tutti questi enunciati realizzati da P₀hanno 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 P₁ che realizza un enunciato differenteechea seconda del valore di ntermina o non termina in dipendenza del fattoche l'enunciato corrispondente a P₁ relativo ad n (cioèP₁(n)) sia vero o falsoe così via con P₂P₃eccetera.
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 P_m con m=0123... rappresentinotutti questi possibili enunciati. Come prima esprimeremo la dipendenza di P_mda n con la notazione P_m(n).
Ora chiediamoci se è possibile scrivere un gran bel programmachiamiamolo Dcheapplicato a P_m(n)sia in grado di dircisenzasbagliarese P_m(n) termina oppure no. Cosa stiamochiedendo al nostro bel programma D? Ad esempiocosa dovrebbe dirci D applicatoa P₀(3)? Dopo averlo esaminato ben beneD dovrebbe terminaree dirci una cosa del tipo:

P0(3) non termina

P0(4) non termina

P0(5) non termina

e così via... InsommaD dovrebbe essere in gradoquandoapplicato ai vari P₀(n) con n > 2di comportarsicome una dimostrazione dell'ultimo teorema di Fermat! Come se nonbastasse Dapplicato a P₁(n)dovrebbe poter'dimostrare' allo stesso modo l'enunciato relativo al programma P₁(n)e così via per P₂(n)P₃(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 P_m(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 P_m(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 P_m(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 P_m(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 P_kcioè:

(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 P_k(k)termina o noe cominciamo col supporre che termini. Dalla sconcertante (G1.5)concludiamo che se P_k(k) terminasse allora nonterminerebbee questa è una contraddizione bella e buona. Tale contraddizioneci forza a concludere che in effetti P_k(k) nontermina! Ma la (G1.3) ci dice che P_k(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 P_k(k)non termina.

La conclusione è questa: abbiamo trovato il programma P_k(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):

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

• Perché succede questo?
  Questo succede perché noi riusciamo a cogliere il significato della(G1.5) e a concludere correttamente che P_k(k) nontermina mentre invece D(kk)=P_k(k) è per cosìdire 'costretto' a non terminare e basta! D(kk) non può 'riflettere' su sestesso (come noi 'riflettiamo' sulla (G1.5)) per concludere "OKio nontermino" e terminare per dircelo!

• In che senso noi conosciamo P_k(k)?
  Non a caso ho appena usato l'espressione "D(kk) è costretto a nonterminare". È infatti importante osservare che il programma che nontermina P_k(k) dipende in modo esplicito (ed ancheabbastanza semplicemente)dal programma D. Insommase 'conosco' Dconosco allo stesso modo P_k(k).Ora si potrebbe discutereper giorni interi sul fatto di conoscere o no un qualunque D; in ogni casoil teorema di Gödel si applica ai sistemi formali S conosciuti oconoscibilied in questo caso l'enunciato V è costruito ad arte a partiredal sistema S in modo tale che noi vediamo che deve essere vero ma la suastessa costruzione ci convince che la sua verità rimane indimostrabileutilizzando le sole regole di S.

• Abbiamo usato un argomento circolare?
  A prima vista sembra di sì: insommaP_k(k) nontermina proprio perché si era partiti dall'affermazione (G1.1) per poiarrivare con un paio di colpi di mano alla sconcertante (G1.5) cheinsiemealla (G1.3)butta la 'colpa' della mancata terminazione di P_k(k)su D(kk) che si trova ad ignorare che lui stesso non termina appuntoperché non termina... Nel linguaggio del sistema formale S si costruisce unenunciato V che (detto alquanto rozzamente) afferma: 'Io non sonodimostrabile in S' e Gödel dimostra che in S sia V che la sua negazioneconducono ad una contraddizione. Quindi V non si può dimostrare in S mapoiché V afferma proprio questo(!)V è vero! A questo proposito Gödel afferma (nota 15 del suo lavorooriginaleliberamente tradotta):
  
  

  A dispetto delle apparenzenon vi è nulla dicircolare in un tale enunciatodal momento che inizia ad asserirela non dimostrabilità di una formula ben determinata (eprecisamente la k-esima in un ben definito ordinamento) e solosuccessivamente (quasi per caso) risulta che questa formula èproprio quella che esprime questo enunciato.