6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

Senza Fermarsi Mai

Posted by scardax su febbraio 25, 2009

E’ difficile pensare all’Informatica come ad una Scienza. O, meglio, é difficile immaginarsi la scienza dell’Informatica. Niente sembra più lontano dalle astratte formule e misteriosi concetti studiati al liceo dalla “realtà” dei computer con cui lavoriamo, giochiamo e comunichiamo con il resto del mondo ogni giorno. Eppure, gli Informatici in quanto Scienziati esistono davvero: ed anche loro hanno i loro modelli teorici con cui si rappresentano un ‘calcolatore modello’ (più o meno come i Fisici hanno le loro rappresentazioni di un atomo), i loro libri pieni di formule matematiche a più non posso, ed i loro bei risultati, spesso anche sorprendenti.

Il più famoso, e forse uno dei più interessanti, fu scoperto da Alan Turing qualche decennio fa, e va sotto il nome di Problema dell’Arresto. Mi piacerebbe cercare di spiegarlo, in maniera abbastanza informale (terra-terra, se vogliamo), evitando qualunque appesantimento formale o teorico (Macchine di Turing e via dicendo). Spero apprezziate il tentativo o, se siete Informatici, spero quantomeno che non mi denunciate.

Per cominciare, pensate ad un qualche programma informatico scritto in un qualunque linguaggio di programmazione (il Java, il C, fate voi, va bene pure un linguaggio che vi siete appena inventati). Se non avete mai visto un simile programma, non credo capirete molto del resto del post. L’idea generale di un programma del genere é molto semplice: prende dei dati in input, li elabora in qualche maniera, e restituisce dei dati in output. Ad esempio possiamo pensare ad un programma isPrime, che prende in ingresso un numero intero n, e verifica che il resto della divisione n/m sia sempre diverso da zero, per qualunque m compreso fra 0 ed (n-1), per verificare se il numero é primo.

Ora, quando i programma crescono in complessità, non é sempre facile capire che succederà all’interno della sua esecuzione. Magari a prima vista sembra funzionare, poi pero’ incontriamo un determinato input che comincia a far “ciclare” il programma all’infinito, non facendolo terminare mai (ad esempio, isPrime potrebbe controllare il resto della divisione per qualunque valore di m, non solo per quelli compresi fra 0 ed (n-1)). Questo é un problema serio: un programma che su alcuni input va bene e su altri no non sembra granché, e mi piacerebbe saperlo in anticipo. Ma se sapessi farlo guardando il codice, probabilmente non mi sarei neanche posto il problema. Quindi, ecco la domanda:

Potrebbe esistere un qualche programma T che, dato un altro programma P, ed un input I, dica se il programma P applicato all’input I termina oppure no?

Ecco, questo é il Problema dell’Arresto espresso nei suoi termini più generali. L’aver inserito la condizione di un dato input I sembra una presa in giro, perché adesso, per verificare la correttezza di P in generale dovrei applicare T a tutti i possibili input di P, e quindi al massimo potrei dire “esiste un input che non fa terminare P” se ne trovassi uno, ma non potrei mai dire “non esiste nessun input che non lo fa terminare“, ovvero “P termina sempre“. Il punto chiave é che, come dimostreremo fra un attimo, un programma come T non potrebbe esistere, e quindi il problema neanche si pone.

Prima di buttarci subito sulla dimostrazione, riagganciamoci un secondo alla realtà (si fa per dire), e vediamo di preciso cosa ci potremmo fare con T. Prendiamo una qualunque congettura matematica non dimostrata sui numeri interi, ad esempio la congettura di Goldbach, che afferma che qualunque numero pari maggiore di due é la somma di due numeri primi (nessuno ha ancora trovato una dimostrazione valida). In pochi minuti, potremmo scrivere un programma che verifichi che un dato numero soddisfa questa congettura (basterebbe provare tutte le possibili somme di numeri primi minori di quel numero), ed utilizzarlo per scrivere un altro programma che verifichi, partendo da 3, la validità di questa congettura per tutti i possibili valori, fermandosi appena trova un numero che non la soddisfa. Fermandosi: ecco la parola magica. E’ sufficiente applicare T al nostro programma e vedere se:

  1. Si ferma, quindi esiste un numero che non soddisfa la congettura di Goldbach, quindi questa non é valida.
  2. Non si ferma e quindi, per un ragionamento simile, la congettura é valida.

Da notare come 1) questa é una dimostrazione a tutti gli effetti e 2) si puo’ ripetere per qualunque ipotesi matematica sui numeri! Se T esistesse, sarebbe una vera e propria “manna“! Ma, come già detto, T non puo’ esistere (“e meno male”, commentano i matematici). Procediamo alla dimostrazione usando un procedimento che dovrebbe essere ben noto agli assidui (o assiDUE, visto che mi sa che non sono molti (e con questa battuta mi sa che me n’é rimasto uno solo, che quindi ora é assiUNO (ed ecco che i lettori sono finiti))) lettori di questo blog: la diagonalizzazione di Cantor.

Per prima cosa, dobbiamo pensare di associare ad ogni possibile programma un numero che lo identifichi: questo si puo’ fare (come già visto tempo fa) assegnando ad ogni carattere (compresi gli spazi ed i caratteri speciali) un numero che li identifichi (ad esempio il corrispettivo ASCII), e quindi sostituire nel programma ad ogni carattere il numero corrispondente. Vengono numeri molto lunghi, esageratamente lunghi forse, ma pur sempre numeri. Notate come ad ogni programma corrisponda un numero, ma ad alcuni numeri non corrisponda un programma: ad esempio 101103 corrisponde (in ASCII) ad “ac“, che in nessun linguaggio di programmazione (credo) é un programma valido. Possiamo pensare di modificare T in questa maniera: dati un numero a corrispondente ad un programma, ed un input (numerico) b:

  • Se il programma é corretto (ovvero, in gergo tecnico, “se si compila”) e termina per l’input b, dà in output 0.
  • Altrimenti, dà in output 1.

La modifica é banale, quindi non ci perdiamo tempo. A questo punto (seconda idea geniale dopo l’assegnamento di un numero univoco ad ogni programma) possiamo costruire una tabella in cui un generico elemento (a,b) é proprio l’applicazione di T ad a e b. Una tabella del genere, insomma:

1 2 3 4 5 …
1545465688412120003164 1 1 0 1 1
44979896432313164499 0 0 1 0 1
366595944112654747662 1 1 1 1 1

Ovviamente i numeri a sinistra, nel caso generale, sarebbero decisamente più grandi. Pero’, grazie alla modifica che abbiamo fatto, a sinistra comparirà ogni singolo numero naturale intero (e stessa cosa per le colonne). A questo punto, prendiamo i numeri sulla diagonale:

1 2 3 4 5 …
1545465688412120003164 1 1 0 1 1
44979896432313164499 0 0 1 0 1
366595944112654747662 1 1 1 1 1

Mettiamoli uno in coda all’altro, ed invertiamoli (ovvero, se c’é 1 sostituiamo con 0 e viceversa). Otteniamo un altro numero (in questo caso che comincerebbe con 010…). Poiché abbiamo detto che ogni numero ha la sua riga (ovvero si trova fra gli elementi a sinistra), ne deduciamo che anche il numero appena ottenuto ci deve essere. Ma notiamo che:

  1. Differisce dalla prima riga per il primo valore.
  2. Differisce dalla seconda riga per il secondo valore.
  3. Differisce dalla riga n per il valore n-esimo.

Ovvero: non si trova nella tabella. Contraddizione! Risalendo il ragionamento, ne deduciamo che: T non puo’ esistere. E, come ogni scienziato che si rispetti, mi sa che ci siamo pure dimenticati di cosa stavamo parlando. Quindi, per oggi, basta! 😀

Annunci

6 Risposte to “Senza Fermarsi Mai”

  1. Andrea P said

    Che bello se esistesse un algoritmo T… niente più teoremi da dimostrare per i matematici. Chi lo dice a mia sorella?!?
    Cmq scard credo per verificare la primalità di un numero sia sufficiente incrementare m fino a n/2 😛 Bel post, continua così!

  2. Pietro said

    La spiegazione da te fornita sulla diagonalizzazione è quella che si trova sui libri ,ma mi chiedo perchè proprio la diagonale ?

    grazie ciao.

  3. scardax said

    Perché altrimenti non puoi asserire che il numero che ottieni sia diverso da tutti gli altri nella tabella.

    Ad esempio, sempre nella tabella da esempio, supponi di prendere sempre la prima cifra, al posto di spostarti lungo la diagonale, e di invertirla: ottieni il numero 010… Questo numero é sicuramente differente dal primo numero della tabella per la prima cifra, ma non si puo’ dire nulla sugli altri numeri (perché le cifre utilizzate sono state messe in una posizione differente nel nuovo numero costruito).

    Comunque, esiste una seconda dimostrazione di questo risultato che si trova sui libri, e cerchero’ di spiegarla nella pagina dedicata ai problemi di Hilbert.

    Grazie di essere passato, e del commento! 😉

  4. Johnny said

    Terribile. Era difficile sbagliare una dimostrazione che si trova scritta su tutti i libri, ma ci sei riuscito (parlo della diagonalizzazione). Non so perché certa gente voglia a tutti i costi fare divulgazione quando ha le idee così confuse sui concetti elementari.
    Senza contare che il tuo presunto “algoritmo” di primalità comincia con una bella divisione per 0 e, come se ciò non bastasse, continua con un’ancor più bella divisione per 1, la quale implicherebbe che nessun numero è primo (poiché sempre divisibile per 1).
    Si continua poi con delle gaffe storiche clamorose: “Ma, come già detto, T non puo’ esistere (“e meno male”, commentano i matematici)”. Guarda caso, proprio il matematico Hilbert, del cui nome apparentemente ami riempirti la bocca, non solo NON avrebbe commentato “meno male”, ma anzi credeva e sperava così fortemente nell’esistenza di quel T che pose tale esistenza a fondamento filosofico della sua strenua opposizione alla corrente disfattista dell’ignorabimus. E dimostrare l’esistenza di quel T è proprio il famoso Entscheidungsproblem proposto da lui nel 1928. Nota che, dal momento in cui ci si accorse che T non esiste, anziché commentare “meno male”, Hilbert non pubblicò proprio alcun commento ufficiale per tutti i 12 anni di vita che gli restarono, tale era la sua rabbia e frustrazione (e non lo dico io, ma lo dicono i suoi biografi, Constance Reid in testa).
    Tralascio poi le numerosissime altre inesattezze, nonsense, imprecisioni e quant’altro, sulle quali ci sarebbe da scrivere un fiume di testo, ma su cui preferisco calare un enorme velo pietoso. Che disastro…

  5. Ed io non capisco come mai tu decida di commentare se trovi il blog così orribile. 🙂
    Tra l’altro, al di là di una svista nell’esempio del calcolo di un numero primo, hai deciso di insultarmi per una battuta inserita nel post? L’aneddoto di Hilbert è interessante, riferito con un minimo di garbo sarebbe stato anche bene accetto.
    PS; non ti preoccupare di voler commentare ulteriormente, data la tua arroganza non mi farò problemi di eliminare ulteriori commenti su questo tono.

  6. Johnny said

    Il grave problema dell’articolo (cosa che tuttora ti ostini imperterrito a voler ignorare) è una voragine concettuale condita da un errore grossolano nella dimostrazione per diagonalizzazione.
    Tutto il resto del mio commento era ovviamente solo a contorno: la parte sull’algoritmo di primalità è introdotta da un “senza contare che”, mentre la battuta sull’inesistenza di T l’ho deifinita “gaffe” (come in effetti è), nemmeno “errore”. Poi, se vuoi vedere solo queste piccolezze e non ti accorgi della trave che hai nell’occhio, fai pure come ti pare. Se addirittura vuoi censurare uno che può insegnarti qualcosa gratis, sarebbe solo l’ennesimo atto autolesionista che commetti in questo blog (stavolta lesivo della tua cultura, non solo della tua immagine).
    Il motivo della mia furia, che scambi furbescamente per arroganza, è l’osservazione della quantità di gente che legge queste robe nel compiacimento di aver capito qualcosa. In questo senso diffondi la peggior forma d’ignoranza, che è l’illusione di sapere, ed è per questo che condanno la tua opera.
    Quanto al perché perdo tempo a scrivere commenti se trovo il blog tanto orribile, è presto detto: perché sono generoso, e spero che non sia tempo completamente perso. Perché se vedo qualcuno che piscia e caga su un’opera d’arte, circondato da un pubblico perso nell’adorazione del gesto, io me ne dispiaccio, allontano il vandalo, e cerco di recuperare l’opera d’arte.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

 
%d blogger hanno fatto clic su Mi Piace per questo: