Il teorema di indecidibilità

Questo teorema si può enunciare, con qualche semplificazione, come 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 definire accuratamente il concetto di sistema formale, ma preferisco lasciar perdere (vedi comunque qui, dove scrivo 'assiomatico', invece che 'formale'). Non che la faccenda sia particolarmente complessa ma, nello spirito di queste pagine, voglio essere davvero semplice nei ragionamenti e devo dire che, anche se il lavoro originale 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 se non sono stato abile, sono stato fortunato: mi è capitato tra le mani un libro di Roger Penrose (Ombre della mente, Rizzoli 1996) dove viene discussa una 'versione' estremamente semplice del teorema di Gödel, versione sviluppata appunto da Penrose, che sfrutta il concetto di macchina di Turing e che, per essere compresa, non abbisogna di tutto l'enorme apparato formale che si trova - necessariamente - nel lavoro originale di Gödel. Qui riporterò questa versione di Penrose con alcune modifiche che, probabilmente, ne indeboliranno la struttura formale ma che, credo, rendono il teorema di Gödel davvero alla portata di tutti.

Il significato del teorema

Prima di dimostrare il teorema però, cerchiamo di capire davvero il significato di quanto dimostrato da Gödel. A prima vista sembra di aver raggiunto un limite insuperabile: ci sono affermazioni vere che sono indimostrabili, della cui verità cioè non ci potremo mai convincere. Giusto? No, sbagliato! Direi invece che il teorema di indecidibiltà, se lo si segue con un po' di attenzione, ci dice proprio il contrario! In effetti, come vedremo, si può ben dimostrare che una certa proposizione esprimibile nel (e dipendente dal) sistema formale S è vera, anche se questa dimostrazione non potrà mai essere espressa nella sintassi del sistema S stesso! Insomma, Gödel dimostra che l'intuito del matematico umano è in grado di 'svincolarsi' dai limiti imposti da un qualsivoglia sistema formale per cogliere delle verità che resteranno per sempre inconoscibili come tali se si resta nei limiti del sistema.

Sistemi formali ed informatica

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

• enunciato in un sistema formale
• sua dimostrazione

• programma per calcolatore
• sua esecuzione

Senza stare a diventar matti col formalismo, vediamo di convincerci di quanto stretto possa essere questo rapporto con un esempio banale, tratto dall'ordinaria aritmetica (che qui gioca il ruolo del sistema formale 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 terne pitagoriche (vai alla pagina relativa)

• programma per calcolatore:

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

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

Chiamiamo questo programma P₀. Vediamo che in un senso ben preciso P₀ dipende dal numero intero '2', infatti nel corso della sua esecuzione ciascun numero utilizzato 'internamente' (a, b e c) viene elevato all'esponente 2. Ovvio, perché l'enunciato di partenza si riferiva a numeri quadrati. Indichiamo il programma P₀ agente sul numero '2' con la notazione P₀(2). Come abbiamo visto P₀(2), riferentesi ad un enunciato vero, termina con successo. Vediamo cosa succede con P₀(1) cioè al programma analogo a P₀(2) dove la condizione:

se a2=b2+c2

se a=b+c.

Il banale enunciato relativo, anch'esso vero, afferma che esiste almeno un numero esprimibile come somma di due numeri, e P₀(1) termina al secondo ciclo, dopo aver banalmente stampato 2,1,1.
Per trovare qualcosa di più interessante non ci occorrerà essere particolarmente originali: P₀(3) equivale all'enunciato 'esiste almeno un cubo esprimibile come somma di due cubi' ed è un caso particolare del celeberrimo ultimo teorema di Fermat. Sappiamo quindi che l'enunciato è falso; che succede al nostro programma P₀(3)? Beh, visto che non esiste un cubo esprimibile come somma di due cubi, la condizione:

se a3=b3+c3

non verrà mai soddisfatta, quindi il programma non potrà mai stampare a, b e c, continuerà a ripetere insensatamente il ciclo programmato, incrementando sempre a, b e c e non terminerà mai!

Torniamo al nostro programma P₀ ed osserviamo che, quando 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 relativo all'esistenza di terne pitagoriche.
  Tale programma termina
• P₀(n) con n>2 realizza l'enunciato falso corrispondente 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 un certo 'tipo' dipendente da n - quadrato, cubo...) esprimibile come somma di due numeri del medesimo 'tipo'.
Non è difficile convincersi che è effettivamente possibile scrivere un programma P₁ che realizza un enunciato differente, e che, a seconda del valore di n, termina o non termina in dipendenza del fatto che l'enunciato corrispondente a P₁ relativo ad n (cioè P₁(n)) sia vero o falso, e così via con P₂, P₃, eccetera.
Ora, proviamo a convincerci di avere a disposizione un elenco completo di tutti gli enunciati possibili nel sistema formale S dipendenti da un solo numero, così che i programmi P_m con m=0,1,2,3... rappresentino tutti questi possibili enunciati. Come prima esprimeremo la dipendenza di P_m da n con la notazione P_m(n).
Ora chiediamoci se è possibile scrivere un gran bel programma, chiamiamolo D, che, applicato a P_m(n), sia in grado di dirci, senza sbagliare, se P_m(n) termina oppure no. Cosa stiamo chiedendo al nostro bel programma D? Ad esempio, cosa dovrebbe dirci D applicato a P₀(3)? Dopo averlo esaminato ben bene, D dovrebbe terminare e dirci una cosa del tipo:

P0(3) non termina

P0(4) non termina

P0(5) non termina

e così via... Insomma, D dovrebbe essere in grado, quando applicato ai vari P₀(n) con n > 2, di comportarsi come una dimostrazione dell'ultimo teorema di Fermat! Come se non bastasse D, applicato 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... Insomma, il nostro bel programma D svolge praticamente il ruolo delle regole del sistema formale S, regole che dovrebbero essere in grado di assegnare il valore vero o falso a tutti gli enunciati (dipendenti da un solo numero) esprimibili in S!
Vedremo che un tale D, indipendentemente dalla nostra bravura, non può venir scritto, e questa impossibilità è l'espressione del teorema di indecidibiltà di Gödel nella versione di Penrose-Turing.

Dimostrazione

Coerentemente con quanto detto poco sopra, supponiamo di avere a disposizione i programmi P_m(n) (che rappresentano tutti i possibili enunciati del sistema formale S dipendenti da un solo numero n) ed indichiamo l'azione di D (che rappresenta le regole di S) su P_m(n) con D(m,n) e diciamo:

e questo sia senza errori: se D(m,n) 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), e otteniamo:

Ora D(n,n) è un programma che dipende dal solo numero n e non più da due, come prima: sarà quindi presente nella lista dei programmi che abbiamo costruito e che dipendono appunto da un solo numero. Diciamo che questo programma sia P_k, cioè:

così che la (G1.2) diventa:

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

Questo suona un po' come una presa per i fondelli, però si può concludere qualcosa di buono dalla (G1.5): chiediamoci se P_k(k) termina o no, e cominciamo col supporre che termini. Dalla sconcertante (G1.5) concludiamo che se P_k(k) terminasse allora non terminerebbe, e questa è una contraddizione bella e buona. Tale contraddizione ci forza a concludere che in effetti P_k(k) non termina! Ma la (G1.3) ci dice che P_k(k) è la stessa cosa di D(k,k), e allora 'anche' D(k,k) non termina. Quindi il nostro bel 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 termina, ma il programma che dovrebbe avvertirci di questo fatto, cioè D(k,k), non è in grado di accorgersene.

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

Notiamo esplicitamente che questa conclusione, in un senso molto forte, è del tutto indipendente da quale D stiamo considerando. Qualunque D' possiamo trovare ha per così dire 'nascosto dentro di sé' il programma che se ne fa beffe: per trovarlo basta ripetere il ragionamento appena fatto sostituendo al nostro vecchio D il nuovo D'. Nei termini dei sistemi formali in qualunque sistema formale esistono affermazioni vere ma non dimostrabili.

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) non termina mentre invece D(k,k)=P_k(k) è per così dire 'costretto' a non terminare e basta! D(k,k) non può 'riflettere' su se stesso (come noi 'riflettiamo' sulla (G1.5)) per concludere "OK, io non termino" e terminare per dircelo!

• In che senso noi conosciamo P_k(k)?
  Non a caso ho appena usato l'espressione "D(k,k) è costretto a non terminare". È infatti importante osservare che il programma che non termina P_k(k) dipende in modo esplicito (ed anche abbastanza semplicemente) dal programma D. Insomma, se 'conosco' D, conosco allo stesso modo P_k(k). Ora si potrebbe discutere per giorni interi sul fatto di conoscere o no un qualunque D; in ogni caso il teorema di Gödel si applica ai sistemi formali S conosciuti o conoscibili, ed in questo caso l'enunciato V è costruito ad arte a partire dal sistema S in modo tale che noi vediamo che deve essere vero ma la sua stessa costruzione ci convince che la sua verità rimane indimostrabile utilizzando le sole regole di S.

• Abbiamo usato un argomento circolare?
  A prima vista sembra di sì: insomma, P_k(k) non termina proprio perché si era partiti dall'affermazione (G1.1) per poi arrivare con un paio di colpi di mano alla sconcertante (G1.5) che, insieme alla (G1.3), butta la 'colpa' della mancata terminazione di P_k(k) su D(k,k) che si trova ad ignorare che lui stesso non termina appunto perché non termina... Nel linguaggio del sistema formale S si costruisce un enunciato V che (detto alquanto rozzamente) afferma: 'Io non sono dimostrabile in S' e Gödel dimostra che in S sia V che la sua negazione conducono ad una contraddizione. Quindi V non si può dimostrare in S ma, poiché V afferma proprio questo(!), V è vero! A questo proposito Gödel afferma (nota 15 del suo lavoro originale, liberamente tradotta):
  
  

  A dispetto delle apparenze, non vi è nulla di circolare in un tale enunciato, dal momento che inizia ad asserire la non dimostrabilità di una formula ben determinata (e precisamente la k-esima in un ben definito ordinamento) e solo successivamente (quasi per caso) risulta che questa formula è proprio quella che esprime questo enunciato.

Per rendersi conto precisamente della verità di questo fatto occorre studiarsi il teorema nella sua forma originale, ma noi ci accontentiamo di quanto detto fin qui, e passiamo ad altro...