Giovedì 29 Giugno 2006

- Sezione 3 - Dal 1600 al 1945 - Temi principali

I problemi (Russel-Turing)

La crisi

Nel 1901 Bertrand Russell scopre un paradosso che coinvolge il concetto ingenuo di “insieme” (riflettendo sulle tematiche introdotte da George Cantor che negli ultimi 30 anni dell’ottocento aveva elaborato una teoria degli insiemi non finiti e introdotto una tecnica detta metodo diagonale).

Alcuni insiemi (detti insiemi normali) non sono membri di se stessi (per esempio l’insieme dei gatti non è un gatto e quindi non appartiene a se stesso); altri insiemi (detti insiemi anomali) appartengono a se stessi (per esempio l’insieme delle cose pensabili è esso stesso pensabile). Il paradosso si presenta quando si pone l’attenzione all’insieme di tutti gli insiemi normali: non può essere normale (perché apparterrebbe a se stesso, contro la definizione di insieme normale) e non può essere anomalo (perché apparterebbe a se stesso contro la sua stessa definizione).

Un altro esempio è costituito da una biblioteca che contiene (un numero finito di) volumi: libri e cataloghi; ogni catalogo descrive un certo numero dei volumi presenti nella biblioteca (che hanno una certa proprietà: per esempio parlano di fisica o sono stati scritti nell’ottocento); il catalogo generale contiene l’elenco di tutti i volumi presenti in biblioteca (compreso se stesso!). Il paradosso consiste nel considerare un catalogo che elenchi i cataloghi che non contengono se stessi: contiene se stesso o no?

L’anno seguente (1902) Russell espone in una lettera il paradosso a Frege; questi riconosce che il paradosso mette in pericolo la coerenza dei suoi “Principi fondamentali dell’aritmetica” (di cui sta per uscire il secondo volume).

La riflessione successiva mostra come evitare il paradosso: lo stesso Russell con Alfred Whitehead pubblica “Principia Matematica” (1910-1913) mostrando che la formalizzazione completa della matematica era realizzabile; tuttavia si poneva un problema assai concreto: come evitare “tutti” i paradossi ed essere sicuri della coerenza di un sistema formale? (cioè che non si potesse con le regole del sistema trarre dalle stesse premesse una conclusione e il suo contrario)

Nel 1928 Hilbert pone esplicitamente due problemi per un sistema formale (in realtà enunciati per la cosiddetta aritmetica di Peano, un sistema che definisce i numeri interi e le operazioni tra questi):

a) problema della completezza (delle regole di deduzione), cioè dimostrare che ogni proposizione (costruibile correttamente) è o vera (deducibile) o falsa (non deducibile).

b) problema della decisione, cioè trovare il metodo costruttivo (o algoritmo) per decidere (effettivamente) se ogni proposizione (costruibile correttamente) è vera o falsa.

La soluzione (parziale)

Nel 1931 Gödel pubblica uno straordinario articolo “Su alcune proposizioni formalmente indecidibili dei Principia mathematica”: tramite un ragionamento ispirato al metodo diagonale di Cantor, pone dei limiti alla completezza e coerenza dei sistemi formali.

L’altro problema di Hilbert, quello della decisione, viene affrontato da Alan Turing (nel 1936) che parte dando una definizione rigorosa di algoritmo (astraendola dal comportamento di una persona che fa di conto): un algoritmo è tutto (e solo) quello che può fare una “macchina” detta appunto di Turing.

Una macchina di Turing è composta da

- un nastro infinitamente lungo suddiviso in caselle, ciascuna delle quali può contenere un simbolo (equivale al foglio di carta a quadretti utilizzato da una persona che fa conti);

- una testina che esamina una casella alla volta e può leggere e cambiare il simbolo della casella (equivale alla persona che fissa l’attenzione su una cifra o ne scrive una);

- degli stati (che rappresentano gli stati mentali della persona);

- un insieme di regole che, dato lo stato e il contenuto della casella corrente, dicono cosa bisogna fare (per esempio scrivere un simbolo o spostarsi a una altra casella).

Per un particolare algoritmo occorre stabilire l’alfabeto dei simboli, e costruire l’insieme degli stati e l’insieme delle regole: scritti in (opportune) caselle del nastro i dati di partenza, si avvia la macchina. Se quello realizzato è effettivamente un algoritmo, la macchina (dopo un certo tempo) si ferma con il risultato contenuto sul nastro in opportune caselle. (Con parole attuali gli stati e le regole costituiscono il programma).

Turing, con un ragionamento essenzialmente analogo (ancora!) al metodo diagonale di Cantor mostra che il problema della decisione non può avere soluzione in un caso “particolarmente” semplice (quello di “riconoscere” un certo insieme di numeri naturali).

Naturalmente il risultato si basava appunto sulla definizione data di algoritmo; nel cercare di renderla più plausibile, Turing costruisce la “macchina universale” cioè quella (con un certo insieme di stati e regole) capace di realizzare “ogni” algoritmo: l’idea di base è di codificare stati e regole di una particolare macchina di Turing e scriverle sul nastro insieme con i dati di partenza; una stessa macchina, con un particolare (ma fisso) insieme di stati e regole può (simulare quella macchina e quindi) realizzare qualunque algoritmo.

È quindi nata l’idea del programma memorizzato (cadendo la distinzione tra dati e programma) e si è aperta la strada alla realizzazione del computer (cioè di una macchina che può realizzare “qualunque” algoritmo).

Home Tour virtuale Sezione 3 Temi principali