Simone MartiniLogica e Informatica:cosa i calcolatori possono e non possono fare

(1)

1

Simone Martini Logica e Informatica:

cosa i calcolatori possono e non possono fare

Dipartimento di Scienze dell’Informazione Alma Mater Studiorum

Università di Bologna

io

 Simone Martini

 Professore di Informatica

 Laurea in Scienze dell’Informazione, Pisa

 Dottore di Ricerca in Informatica, Pisa

 Insegnato a Pisa (fino al 1994) e poi Udine, fino al 2002

 Ricerca: come sopra e:

 Digital Eq. Co. Systems Res. Center, Palo Alto

 Stanford University

 École normale superieure, Parigi

 Université Paris Nord

(2)

2

logica e informatica 3

info

 E-mail:

 martini@cs.unibo.it

 web

 www.cs.unibo.it/~martini

 ricevimento studenti

 mercoledì 13:30

 su appuntamento per posta elettronica

testo



un manuale autocontenuto con tutti i dettagli tecnici:

(3)

Logica e Informatica

I materiali del corso...



La prima parte:

 limiti assoluti alle possibilità del calcolo

– materiale maturo intorno al 1935!



La seconda parte:

 limiti dettati dalle risorse alle possibilità del calcolo

– materiale maturo intorno al 1975

– molta ricerca ancora attiva:

• il problema aperto più importante dell’informatica teorica:

P=NP?

(4)

4

Il primo atto



Circa 1930-1936



Cambridge



Vienna



Princeton

Cambridge: Alan M. Turing



23 June 1912 in London, England



7 June 1954 in Wilmslow

(5)

Princeton: Alonzo Church



14 June 1903 in Washington, D.C., USA



11 Aug 1995 in Hudson, Ohio

Princeton: Stephen C. Kleene



5 Jan 1909 in Hartford, Connecticut,



25 Jan 1994 in Madison, Wisconsin,

(6)

6

Princeton-Vienna: Kurt Gödel



28 April 1906 in Brünn, Austria-Ungheria (Brno, Repubblica Ceca)



14 Jan 1978 in Princeton, New Jersey,

Vienna-Princeton: John (János) von Neumann



28 Dec 1903 in Budapest, Hungary



8 Feb 1957 in Washington D.C.,

(7)

La dote di Zeus



Formalismi per la calcolabilità effettiva

 in cosa consiste una funzione effettivamente calcolabile?

(in opposizione ad enunciati puramente esistenziali)

 Turing

– automa “symbol pushing”

 Gödel-Kleene

– Funzioni ricorsive generali

 Church

– calcolo di funzioni come riscrittura di stringhe

 e molti altri...

Perché la logica se ne interessava ?



I paradossi



La soluzione matematico-logica

 i Principia Mathematica

– Bertrand Russell e Alfred North Whitehead



Il programma di David Hilbert

 la riduzione all’aritmetica

 la dimostrazione di consistenza dell’aritmetica



Una sua componente

(8)

8

Quale esito ha il programma?



Non esiste alcun procedimento meccanico per decidere della verità di un asserto:

Church



L’aritmetica (= gli asserti veri sui numeri) non corrisponde alla sua “teoria logica formalizzata”

 vi sono asserti veri che non sono dimostrabili

– Gödel (I teorema di incompletezza)

 la consistenza dell’aritmetica può essere dimostrata solo con strumenti più potenti di essa

– Gödel (II teorema di incompletezza)

Ma...



Come sottoprodotto

 fonda la logica matematica moderna

 fonda la calcolabilità effettiva

 che von Neumann trasformerà nel primo calcolatore fisico

(9)

Torniamo a Vienna



Gödel presenta il suo primo teorema di incompletezza, 1930

 Carnap, H. Hahn, H. Reichenbach, J. von Neuman

 M. Schlick

 L. Wittgenstein

il Tractatus logico-philosophicus,

1918-1922



Prefazione:

 Quanto può dirsi, si può dir chiaro.



Proposizione 7 (l’ultima):

 Su ciò, di cui non si può parlare, si deve tacere.

(10)

10

Problemi di cardinalità



Quante sono le cose di cui si può parlare?



Quanti i sono i numeri?



E quanti sono i problemi numerici?

La macchina di Turing

(11)

Funzioni Turing-calcolabili



Fissati:

 un insieme di simboli S

 una codifica dei naturali con stringhe finite di S _ : Nat → S*



f : Nat

^k

→ Nat (parziale) è Turing-calcolabile

sse esiste una MdT M t.c.

per ogni n₁,...,n_k, m

f(n₁,...,n_k)≅m sse M(n1,...,n_k) ↓m