Logica matematica e informatica: dalla origine della scienza dei calcolatori alla tematica mente macchina

2 Introduzione
come caso particolare il calcolo delle proposizioni di Boole. Se Boole si limito`
a considerare le proposizioni e alle regole logiche che intervengono quando
piu` proposizioni elementari si mettono insieme a formarne una piu` complessa,
Frege entro` nei dettagli della struttura di ogni singola proposizione. L’odierna
formalizzazione del linguaggio logico con i quantificatori, simboli di funzione
e simboli di predicati e` dovuta interamente a Frege, il quale scopr`ı anche un
insieme di regole di deduzione per il calcolo dei predicati, grazie alle quali
il processo di derivazione di conclusioni a partire da premesse e` del tutto
meccanico.1
Cantor studio` il problema dell’infinito in matematica, fu l’inventore (o
scopritore, a seconda della filosofia della matematica che piu` si confa` ai
nostri gusti) dei numeri transfiniti. Si inserisce in questa linea di pensiero
per aver contribuito al dibattito sui fondamenti della matematica (uno dei
punti piu` delicati a questo riguardo era appunto il problema dell’infinito
in matematica, portato prepotentemente alla ribalta da Cantor) ed aver
introdotto ed utilizzato il cosiddetto metodo diagonale nelle dimostrazioni
matematiche, destinato ad avere un’importanza enorme nel lavoro successivo
di Go¨del e Turing.
Il lavoro logico di Boole, Frege e Cantor, cui si devono ovviamente
aggiungere i contributi di altri logici molto importanti tra cui Peano e Russel,
spiano` la strada al dibattito filosofico sui fondamenti della matematica a
cavallo tra la fine del XIX secolo e l’inizio del XX secolo. Non e` stata
nostra intenzione analizzare in dettaglio nella tesi le varie correnti filosofiche
che si disputarono il primato nella discussione sui fondamenti (logicismo,
formalismo, intuizionismo), anche se ovviamente e` stato necessario inserire
qualche accenno al riguardo. Di particolare importanza per noi e per le
questioni che stiamo analizzando (cioe` l’impatto della logica sull’informatica)
sono la figura ed il lavoro di David Hilbert. La scuola di Hilbert, tra i cui
appartenenti ricordiamo in particolar modo Bernays, apportera` un grosso
contributo alla logica matematica moderna (con Hilbert nasce la Teoria
della dimostrazione) soprattutto mettendo in evidenza con la cosiddetta
metamatematica la possibilita` di studiare matematicamente un sistema
rappresentante la matematica. Il successo del cosiddetto Programma di Hilbert,
delineato nel Capitolo 1.5 di questa tesi, il cui scopo, per dirlo con le parole di
Bernays, era quello di trasferire i problemi e le difficolta` che si presentavano
nella fondazione della matematica dal dominio filosofico–epistemologico a
quello proprio della matematica, avrebbe implicato (semplificando forse un
po’ troppo) tra le altre cose:
• un sistema di assiomi per la matematica, formalizzato al primo ordine, in
cui grazie alle regole logiche di Boole e Frege si potessero dimostrare tutti
1Successivamente il Teorema di Completezza di Go¨del dimostro` che tali regole catturano
a pieno la nozione di validita` logica.
Introduzione 3
gli enunciati veri della matematica (questa proprieta` viene chiamata la
proprieta` di completezza del sistema);
• una dimostrazione finitista2 della consistenza del sistema all’ “interno”
del sistema;
• un algoritmo per decidere, dato un enunciato, se questo sia dimostrabile
oppure no nel nostro sistema (Hilbert chiamo` questa parte del suo
programma l’ Entscheidungsproblem, o problema della decisione).
Il Programma di Hilbert tenne occupati alcuni dei migliori logici dei primi
tre decenni del XX secolo, tra cui von Neumann. Nei primi anni ’30 Go¨del,
con i suoi celebri Teoremi di Incompletezza, dimostro` che il Programma di
Hilbert era destinato a fallire. Per un sistema matematico formalizzato al
primo ordine consistente, esistera` sempre un enunciato vero che non si puo`
dimostrare (Primo Teorema di Incompletezza di Go¨del); inoltre non si puo`
dimostrare all’interno di un tale sistema la sua consistenza (Secondo Teorema
di Incompletezza di Go¨del).
Del Programma di Hilbert rimaneva ancora l’Entscheidungsproblem. E` a
questo punto che subentra Turing. Turing analizza le nozioni di algoritmo
e computazione, ne individua per cos`ı dire le caratteristiche essenziali, e
propone un modello di macchina (macchina di Turing) che “calcoli” secondo
tali caratteristiche essenziali. Quindi argomenta in modo assolutamente
convincente che ogni compito che possa essere eseguito calcolando, puo` in
effetti essere esguito da una macchina di Turing. Risolvere negativamente
l’Entscheidungsproblem si riduce quindi a dimostrare che per i sistemi
matematici in cui formalizzare la matematica (sotto opportune ipotesi di
consistenza) non esiste nessuna macchina di Turing in grado di decidere se un
dato enunciato sia o no un teorema. Ed e` quanto Turing fece nel famoso articolo
On computable numbers, with an application to the Entscheidungsproblem del
1936. Da notare che la soluzione negativa dell’Entscheidungsproblem implica
anche l’esistenza di enunciati “indecidibili”3 (Primo Teorema di Incompletezza
di Go¨del), perche´ un sistema formale (cioe` con un insieme decidibile di assioni
e con regole di deduzione meccaniche) completo e` ipso facto decidibile.
Nell’ introdurre il suo modello di computazione, Turing si imbatte in
un concetto assolutamente nuovo, quello di macchina universale. Si tratta
di una scoperta veramente rivoluzionaria. Fino ad allora la macchina
era stata concepita solamente come un oggetto fisico, quello che oggi si
chiama comunemente hardware, distinto dal programma (software), “immesso”
dall’esterno; infine alla macchina venivano forniti dati, come input. La
macchina universale di Turing elimina sostanzialmente la distinzione tra
2Facente uso cioe` solo dei metodi elementari dell’ aritmetica (vedi 1.5.7).
3cioe` tali che ne´ l’enunciato ne´ la sua negazione siano dimostrabili
4 Introduzione
queste tre categorie di oggetti. Nell’ utilizzarlo per eseguire le istruzioni
corrispondenti, la macchina universale manipola e tratta come dati il
programma di una qualsiasi altra macchina di Turing. E` la nascita del concetto
di programma memorizzato, e di macchina all-purpose. Non a caso Turing
e` stato forse il primo a concepire macchine che potessero fare di tutto, dai
calcoli aritmetici fino a giocare a scacchi. Questa universalita` spinse Turing al
paragone tra la mente e la macchina universale. Turing pensava che la mente
potesse funzionare come una macchina universale. E` interessante osservare
che Turing anticipo` o controbatte` ante litteram, [30], molte delle obiezioni
successive circa la presunta superiorita` della mente sulle macchine, avanzate
da alcuni pensatori (tra cui ad esempio Searle e Penrose, [25], [22], [23]), in
particolar modo quelle che affermano che questo si possa inferire dai Teoremi
di Go¨del. Al problema mente/macchina sono dedicate alcune osservazioni di
questa tesi, in particolare il Capitolo 2. A tal proposito Turing puo` essere
visto anche come il fondatore della moderna Intelligenza Artificiale. Turing
infatti studio` il problema di che cosa significhi pensare e, pur senza pretendere
di dare risposte definitive di cui si rendeva ben conto come fosse impossibile
darle, forn`ı ipotesi di lavoro e criteri a tutt’ oggi insuperati, quali il famoso
Test di Turing.
Per varie ragioni, l’impronta fondamentale data da Turing alla nascita
della scienza dei calcolatori non fu immediatamente riconosciuta. Secondo
una consuetudine di pensiero, l’artefice ed architetto degli odierni calcolatori e`
von Neuman (per cui si parla di “architettura di von Neumann” per descrivere
l’organizzazione degli elaboratori elettronici). Ma si puo` argomentare che ben
poco di quanto viene attribuito a von Neumann non fosse gia` stato ideato e
pensato da Turing. Anzi molto spesso la visone di Turing era piu` ampia ed
elegante.
I meriti di Turing sono stati riconosciuti dalla rivista Time il 29 marzo
1999, che in una rassegna dei venti piu` grandi scienziati e pensatori del XX
secolo include Turing di cui dice:
Cos`ı tante idee a scoperte tecnologiche hanno contribuito a creare
il calcolatore moderno che e` temerario dare ad un singolo individuo
il credito di averlo inventato. Ma rimane il fatto che tutti
coloro che battono ad una tastiera, aprono un foglio di calcolo
od un programma di scrittura, lavorano ad un’incarnazione di una
macchina di Turing.
Dall’Entscheidungsproblem (problema puramente teorico di logica) ai
calcolatori!
Ed ecco quello che Time dice di von Neumann:
Virtualmente, tutti i computer dai supercomputer da 10 milioni di
dollari a minuscoli chip che azionano i telefoni cellulari e i Furbies
Introduzione 5
hanno una cosa in comune: sono tutti “macchine di von Neumann”,
variazioni dell’architettura di base dei computer che von Neuman,
basandosi sul lavoro di Alan Turing, propose negli anni ’40.
Il riconoscimento dei meriti di Turing anche a confronto di quelli, seppure
immensi, di von Neumann non potrebbe essere piu` chiaro.
6 Introduzione
Capitolo 1
Dalla Characteristica
Universalis alla Macchina
Universale
Ritorniamo all’analogia delle macchine che eseguono computazioni. . . Si
puo` dimostrare che una singola macchina di questo tipo puo` eseguire
il lavoro di ognuna. Potrebbe infatti essere fatta funzionare come un
modello di ogni altra macchina.
Questa macchina speciale sara` chiamata macchina universale.
Alan Turing, 1947
Le origini dei computers al contrario di quanto si possa pensare sono molto
lontane e si possono trovare in quell’ aurora del pensiero europeo in cui si
intuisce che la conoscenza dell’ uomo si basa sulla possibilita` di rappresentare
tramite il linguaggio da un lato un mondo di cose e fatti, dall’ altro un mondo
di idee e pensieri. I computers moderni sono il frutto di idee e concetti che sono
stati sviluppati nel corso di secoli da importanti pensatori. Ma e` soprattutto
nel Novecento che si e` avuta la grande svolta che e` partita dall’ ambiente
matematico come effetto delle discussioni attorno alle questioni riguardanti
i fondamenti della matematica. E` in questo contesto che sono maturate,
negli anni 30, le definizioni di concetti intuitivi quale quello di computabilita`
effettiva, cos`ı importante per quanto riguarda la realizzazione dei computers i
quali trovano il loro modello teorico nel concetto astratto–logico di macchina di
Turing Universale. Lo studio e la chiarificazione di questi concetti ha portato a
risultati sconvolgenti riguardanti i limiti della computabilita` quali il Teorema
di Incompletezza di Go¨del che qui viene presentato e nel prossimo capitolo
viene ripreso, in considerazione alla recente discussione sulla mente.
8 Dalla Characteristica Universalis alla Macchina Universale
1.1 Il sogno di Leibniz
Il Seicento fu un’ epoca travagliata da numerose guerre ma fu
contemporaneamente fervida e creativa. Al Seicento dobbiamo infatti, in
primo luogo, la fondazione della moderna metodologia scientifica, cui diedero
contributi decisivi, oltre che Galileo Galilei e Cartesio, filosofi e ricercatori
di tutte le nazioni europee. Gottfried Wilhelm Leibniz (Lipsia 1.7.1646 -
Hannover 14.11.1716) fu uno di questi. Nell’ambito della cultura razionalistica
inaugurata da Cartesio e sviluppata da Spinoza e Hobbes, Leibniz occupa
una posizione di particolare importanza per le originali elaborazioni tanto
nel campo della metafisica quanto in quello della matematica e della logica.
Svolse nella sua vita attivita` diplomatiche e politiche, fu un giurista di fama, e
svolse l’attivita` di storiografo al servizio del duca di Hannover. In campo
logico egli fu affascinato fin da molto giovane dalla logica che Aristotele
aveva sviluppato due millenni prima e per il resto della sua vita rimase
legato ai contenuti della filosofia aristotelica. Leibniz ebbe una visione di
grande capacita`. Fu, insieme e parallelamente a Newton, il creatore del
calcolo infinitesimale, e la notazione che sviluppo` per questo, superiore a
quella di Newton tanto che e` la notazione ancora usata oggi, rendeva semplice
l’esecuzione di calcoli complicati. Con la sua notazione le operazioni del calcolo
infinitesimale erano ridotte a manipolazioni su simboli governate da poche e
semplici regole, allo stesso modo in cui avviene nell’algebra la manipolazione
dei simboli che rappresentano concetti numerici. Nella visione di Leibniz,
qualcosa di simile poteva essere fatto per l’intero ambito della conoscenza
umana. Voleva trovare un alfabeto speciale i cui elementi rappresentassero
non suoni, ma concetti; questi simboli avrebbero dovuto avere quella che
lui chiamo` la characteristica universalis, cioe` la capacita` di racchiudere tutto
l’intero ambito del pensiero umano. Leibniz penso` inoltre che il ragionamento
umano poteva essere ridotto a manipolazioni su questi simboli governate da
poche regole allo stesso modo dei calcoli algebrici. Egli chiamo` questo calcolo
del ragionamento calculus ratiocinator, quello che ai giorni nostri chiamiamo
logica simbolica. Il sogno, irrealizzabile, si puo` comprendere solo dal punto di
vista della visione del mondo di Leibniz. Per lui assolutamente niente al mondo
era in qualche modo indeterminato o accidentale; ogni cosa seguiva un piano,
chiaro nella mente di Dio, attraverso i significati del quale Egli aveva creato il
miglior mondo che poteva essere creato. Quindi, tutti gli aspetti del mondo,
naturali e soprannaturali, erano connessi attraverso collegamenti che si poteva
sperare di scoprire attraverso la ragione. Solo in questa prospettiva possiamo
capire come, in un famoso passaggio, Leibniz poteva scrivere a proposito di
uomini di buona volonta` seduti intorno ad un tavolo per risolvere qualche
problema critico che, dopo aver scritto il problema nel linguaggio immaginato,
la characteristica universalis, avrebbero esclamato “Signori, calcoliamo!” e la
1.1 Il sogno di Leibniz 9
GOTTFRIED WILHELM LEIBNIZ
10 Dalla Characteristica Universalis alla Macchina Universale
risposta al problema sarebbe stata trovata definitivamente dato che nessuno
avrebbe mai dubitato della sua correttezza.
Diversamente dalla characteristica universalis, per la quale Leibniz scrisse
con tanta passione e convinzione, ma produsse poco in modo specifico, egli
fece dei tentativi per produrre il suo calculus ratiocinator. Possiamo vedere
nella tabella (1.1) parte dei risultati piu` interessanti dei suoi sforzi in questa
direzione. Egli introdusse un nuovo simbolo speciale ⊕ per rappresentare la
combinazione delle piu` arbitrarie pluralita` di termini. L’ idea era qualcosa di
simile alla combinazione di due collezioni di cose in una singola collezione
contenente tutti gli elementi di entrambi. Il segno + allude all’ordinaria
addizione, ma il cerchio intorno ci avverte che non e` esattamente la stessa
cosa perche´ non sono numeri gli oggetti su cui ⊕ agisce. Alcune regole a cui
⊕ e` sottoposta sono simili alle regole che si applicano ai numeri. Altre regole
pero` sono molto differenti da quelle per i numeri; ad esempio l’ Assioma 2,
A ⊕ A = A, esprime il fatto che combinando una pluralita` di termini con se
stessa non si ottiene nulla di nuovo. Nell’addizione tra numeri cio` ovviamente
non vale: 2 + 2 = 4, non 2. In termini moderni il simbolo ⊕ e` quello che viene
rappresentato come ∪ nella teoria degli insiemi e cioe` l’unione tra insiemi. In
un contesto in qualche modo differente lo stesso contenuto dell’ Assioma 2 e`
stato preso in considerazione da George Boole piu` di un secolo dopo Leibniz,
che ne ha fatto la sua pietra angolare della sua algebra della logica.
Un importante argomento che viene messo in risalto da Leibniz e` poi quello
che nei primi anni del Novecento venne ad essere riconosciuto comunemente
come il problema principale della logica e che fu chiamato da Hilbert
Entscheidungsproblem (vedi 1.5). In una lettera a Galloys del 1677, Leibniz
aveva prospettato la necessita` di un “filo di Arianna” che guidasse l’ intelligenza
evitandole di perdersi nel labirinto della deduzione:
Il metodo esatto ci deve fornire il filo d’ Arianna, cioe` un certo mezzo
sensibile e pratico che guidi l’ intelligenza [. . . ]. Senza questo la nostra
intelligenza non potrebbe compiere un lungo cammino senza arenarsi.
G. W. Leibniz1.
In una lettera ad Oldenburg, egli chiar`ı che il metodo in questione doveva
essere di tipo meccanico, applicabile senza l’ uso dell’ intelligenza:
Chiamo filo del meditare un indirizzamento sensibile e come meccanico
della mente, che possa essere conosciuto anche dai piu` stupidi.
G. W. Leibniz (Idem pag. 14)
1
In Die Philosophischen Schriften, a cura di C. I. Gerhardt, pag. 22, Hildesheim, Olms,
vol. VII, 1961