Montali - Da Leibniz a Turing: la nascita dei computer e la scoperta dei limiti della matematica

Da Leibniz a TuringLa nascita dei computer

e la scoperta dei limiti della matematica

Marco Montali [email protected]

mailto:[email protected]?subject=

Come ci siamo arrivati?

“Solo” questo?

Ingegneria Fisica

No!

Ingegneria Fisica

Filosofia

Matematica Logica

No!

Ingegneria Fisica

Filosofia

Matematica Logica informatica

Cosa faremo• Nascita dei computer attraverso le vite di alcuni

grandi pensatori • Considereremo solo alcuni dei loro contributi!

• Una storia costellata di paradossi:

I computer nascono quando si scopre

quello che non saranno mai in grado di fare

Linea del tempo1645 1660 1675 1690 1705 1720 1735 1750 1765 1780 1795 1810 1825 1840 1855 1870 1885 1900 1915 1930 1945 1960 1975

GottfriedLeibniz

GeorgBoole

GottlobFrege

DavidHilbert

BertrandRussell

KurtGödel

AlanTuring

Bibliografia

Formule, teoremi, dimostrazioni

• Una formula matematica:

• Questa formula è vera - è un “teorema”? Come faccio a dimostrarlo?

1 + 2 + 3 + 4 + . . .+ n =nX

i=1

i =n(n+ 1)

2

Dimostrazione• Per dimostrare, servono:

• “assiomi” o “postulati” che vengono assunti come veri • Regole per combinarli e “derivare” nuove formule vere

• Nel nostro caso: numeri naturali • Quindi: “assiomi dell’aritmetica”, per definire i concetti di numero,

somma, prodotto, ecc. • Non esiste nessun numero naturale n tale che n+1=0 • Per ogni numero naturale n, n+0=n • …. • Principio di induzione

Dimostrazione• Per dimostrare, servono:

• “assiomi” o “postulati” che vengono assunti come veri • Regole per combinarli e “derivare” nuove formule vere

• Nel nostro caso: numeri naturali • Quindi: “assiomi dell’aritmetica”, per definire i concetti di numero,

somma, prodotto, ecc. • Non esiste nessun numero naturale n tale che n+1=0 • Per ogni numero naturale n, n+0=n • …. • Principio di induzione

aritmetica di Peano

Dimostrazione per induzione(Gauss, 8 anni)

• Passo base dell’induzione:

• Prendiamo n=1

• Otteniamo: 1 = 1(1+1)/2 OK!

1 + 2 + 3 + 4 + . . .+ n =nX

i=1

i =n(n+ 1)

2

• Passo induttivo. Assumiamo che la formula sia vera per un generico “k”. Facciamo vedere che vale per “m=k+1”.

1 + 2 + 3 + 4 + . . .+ n =nX

i=1

i =n(n+ 1)

2

1 + 2 + 3 + 4 + ...+ k| {z }k(k+1)

2

+(k + 1) =k(k + 1)

2+ (k + 1)

= (k + 1)

✓k

2+ 1

◆

=(k + 1)(k + 2)

2

=(k + 1)((k + 1) + 1)

2

=m(m+ 1)

2

Domande• Quali assiomi e regole di derivazione ci servono?

• Come facciamo a sapere che “bastano” per dimostrare rigorosamente qualunque verità matematica?

• Possiamo utilizzarli per effettuare davvero una dimostrazione? Possiamo rendere questo procedimento meccanico? O serve “l’intuizione” del matematico?

• Queste domande hanno assillato generazioni di matematici e filosofi, e… hanno portato alla nascita dei computer!

Il sogno di Leibniz

Gottfried Leibniz• Nasce a Leipzig (Germania)

nel 1646

• Muore ad Hannover (Germania) nel 1716

• Padre: Professore di filosofia morale all’Università di Leipzig

• Cresce fra i libri, e comincia a studiare latino a 8 anni

Alcune curiosità• Studia sia filosofia (laurea) che legge (dottorato) • Lavora sotto la protezione di nobili tedeschi

• Non solo “pensatore”, ma anche politico, diplomatico, storico, … • Per guadagnarsi da vivere, spende molto tempo

nella ricostruzione dell’albero genealogico del suo nobile “protettore”

• Vive molti anni a Parigi, entrando in contatto con grandi pensatori e matematici del tempo

• Sviluppa una filosofia “positiva”, ma si dice fosse pessimista di natura

Leibniz matematico

• Studiando il calcolo infinitesimale e i passaggi al limite, inventa la notazione che usiamo ancora oggi

• Punto cruciale: scegliere simboli adatti e regole precise per manipolarli

• Vivrà una lunga diatriba con Newton sulla paternità di queste idee

Leibniz ingegnere

Leibniz sognatore

• Da giovane, legge Aristotele… • … e ne rimane folgorato

• Convinzione: nell’universo non c’è nulla di indeterminato o accidentale • Dio ha creato il migliore dei mondi possibili • Tutti gli aspetti del mondo sono in relazione tra loro • La ragione può permetterci di scoprire queste

relazioni

La sua “idea meravigliosa”

creare un alfabeto di concetti, e sviluppare un calcolo simbolico per stabilire quali

enunciati sono veri e come sono in relazione logica fra loro

Il piano di Leibniz1.Creare un’enciclopedia di tutta la conoscenza umana (vi dice qualcosa???)

2.Trovare simboli adatti a rappresentare questa conoscenza, abbracciando i fatti ma anche il pensiero umano

3.Definire regole inoppugnabili per manipolare questi simboli: il calculus raziocinator (la nostra “logica simbolica”)

… un piano che non terminò mai …

… DEFINIZIONE 3. Dire che A è in L o che L contiene A è lo stesso che dire che L può essere fatto coincidere con una pluralità di termini, assunti insieme, uno dei quali è A. B⊕N=L significa che B è in L e che B e N insieme compongono o costituiscono L. Questo vale anche di un numero di termini più grande. ASSIOMA 1. B⊕N = N⊕B.

POSTULATO. Più termini qualsiasi come A e B possono essere assunti insieme per comporre un termine solo A⊕B.

ASSIOMA 2. A⊕A = A.

PROPOSIZIONE 5. Se C è in B e A = C, C è in B. Infatti, sostituendo C nella proposizione “A è in B”, si ottiene “A è in C”. … PROPOSIZIONE 20. Se A è in M e B è in N, A⊕B è in M⊕N.

…

Logica• Logica: lo studio del ragionamento e dell’argomentazione,

allo scopo di identificare i procedimenti inferenziali validi

• Esempi di regole di derivazione valide:

• Modus ponens (cf. Aristotele): Gli uomini sono mortali.Socrate è un uomo. QUINDI: Socrate è mortale.

• Sillogismo ipotetico:Gli studenti amano l’estate.Chi ama l’estate, ama le vacanze. QUINDI: gli studenti amano le vacanze.

Logica simbolica• Applicazione della logica alla matematica

• Le inferenze diventano, in questo caso, dimostrazioni

• Modus ponens: a partire da ipotesi, assiomi e teoremi noti, si derivano nuovi teoremi!

• Esempio: il teorema di Pitagora a partire dai 5 postulati di Euclide sulla geometria piana

• Altro esempio: la legge di Gauss vista prima

http://www.wolframalpha.com

children of Barack Obama derive sin(x)

http://www.wolframalpha.com

Boole trasforma la logica in algebraConoscete il termine “logica booleana”?

George Boole• Nasce a Lincoln (Inghilterra) nel 1815

• Muore nel 1864 di polmonite • La moglie cerca di guarirlo da un

raffreddore tenendolo per 4 gg in un letto bagnato

• Il padre è un calzolaio squattrinato, appassionato di strumenti scientifici • Fin da ragazzo si occupa della

propria famiglia

Alcune curiosità• Ama i libri di matematica perché “ci vuole più

tempo per leggerli” • A 16 anni insegna in una scuola metodista

• Viene licenziato per comportamento irreligioso (scoperto a studiare matematica in chiesa)

• A 19 anni fonda una scuola a Lincoln, e ci lavora fino a 34 anni (facendo anche il volontario)

• Diventa poi (finalmente) professore universitario a Cork, nonostante le sue umili origini!

Algebra per la logica?• L’algebra è “lo studio dei simboli matematici e delle

regole per manipolare questi simboli” • Esempio: 2(x + y) = 2x + 2y • Due aspetti fondamentali:

• Simboli rappresentano sia “quantità” che “operazioni” • Questi vengono manipolati usando regole precise

• Non vi ricorda il programma di Leibniz? • Boole si chiede: è possibile sviluppare un’algebra per la

logica?

””

La logica non parla di quantità

Se come termine di una descrizione usiamo un aggettivo, per esempio ‘buono’, con una lettera, y, rappresenteremo tutte quelle cose alle quali può applicarsi la descrizione ‘buono’, vale a dire ‘tutte le cose buone’, o la classe delle ‘cose buone’

””

La logica non parla di quantità

Conveniamo inoltre di rappresentare con xy la classe di cose a cui sono applicabili, simultaneamente, i nomi o le descrizioni rappresentati da x e da y. Così se x da solo sta per “cose bianche”, e y sta per “pecore”, xy starà per “pecore bianche”.

Algebra per la logica• A cosa assomiglia xy?

Algebra per la logica• A cosa assomiglia xy? Prodotto!


• Ma… se x rappresenta una classe:

xx = ?(immaginate x = “pecore”)



xx = x(immaginate x = “pecore”)

• L’algebra parla di quantità… per quali numeri è vero xx = x?



xx = x(immaginate x = “pecore”)

• L’algebra parla di quantità… per quali numeri è vero xx = x? {0,1}

Conclusione di Boole

• L’algebra della logica va applicata ai numeri 0 e 1

• Nota: 0 e 1 sono l’alfabeto del codice binario, il cuore di ogni computer!

• Ma… a cosa corrispondono prodotto, somma e sottrazione?

L’algebra di Boole• Definizione degli operatori

• Moltiplicazionexy = classe degli elementi che stanno in x e y(intersezione)

• Addizionex+y = classe degli elementi che stanno in x o y(unione)

• Sottrazionex - y = classe degli elementi che stanno in x ma non in y

Esempio

• Nell’algebra di Boole, possiamo derivare

x (1-x) = 0

• 1-x = “classe degli oggetti che non soddisfano x”

• Quindi la formula dice: non è possibile che un oggetto stia e non stia in una classe!

L’algebra cattura il sillogismo• Sillogismo ipotetico:

Premesse: “tutti gli X sono Y”, e “tutti gli Y sono Z” Conclusione: “tutti gli X sono Z”

• Traduzione delle premesse nell’algebra di Boole: X = XY Y = YZ

• Ma allora: X = XY = X(YZ) = (XY)Z = XZ

• XZ significa “tutti gli X sono Z” (la conclusione del sillogismo!!!)

Boole e il sogno di Leibniz• L’algebra booleana rappresenta solo un passo

rispetto al sogno di Leibniz

• Non è possibile esprimere proprietà del tipo “tutte le lezioni sono noiose o interessanti”, e ragionare sulla distinzione delle une rispetto alle altre

• Boole non definisce un metodo di “calcolo” che sia capace di derivare tutte le verità matematiche a partire da un piccolo insieme di premesse

Frege: dalla conquista al crollo

Gottlob Frege

• Nasce nel 1848 a Wismar (Germania)

• Muore nel 1925 vicino a Wismar

• Il padre è un teologo evangelico, preside di un liceo femminile

Alcune curiosità• Ottiene il dottorato in matematica, ma il suo lavoro non

viene apprezzato quasi da nessuno

• Lavora per 5 anni senza stipendio all’università, poi diventa professore associato (ma non riuscirà mai a diventare ordinario)

• Nell’ultima fase della sua vita è vittima di forte depressione

• Il suo unico figlio adottivo pubblicherà, dopo la sua morte, il suo diario, in cui emergono idee reazionarie e profondo antisemitismo

La supremazia della logica

• Boole: algebra ordinaria per rappresentare le relazioni logiche

• Per Frege: questo è un errore! • Non si può sviluppare la logica “usando la logica

stessa” • Ma… tutta la matematica va fondata sulla logica • Serve quindi un modo per specificare la logica

senza usare l’algebra

Il linguaggio della logica• Costruisce un “linguaggio artificiale” che

• non si confonde con l’algebra • non cade nelle ambiguità del linguaggio naturale

• risultato: l’Ideografia (Begriffsschrift)• “linguaggio in formule del pensiero puro

modellato su quello dell’aritmetica” • libretto di 100 pagine, considerato forse l’opera

più importante mai scritta in logica • Un linguaggio che usiamo ancora oggi!

Caratteristiche dell’Ideografia

• Permette di formalizzare aspetti molto più complessi di quelli trattati da Boole

• Segue rigide regole grammaticali

• Le regole di inferenza diventano operatori puramente meccanici, che manipolano simboli senza conoscerne il significato

“Per ogni” vs “Esiste”• Frege capisce che l’approccio di Boole è troppo

grossolano

• Differenza tra: Tutti i cavalli sono mammiferiAlcuni cavalli sono purosangue


grossolano


Se x è un cavallo, allora x è un mammifero

x è un cavallo e x è un purosangue


grossolano


Se x è un cavallo, allora x è un mammifero

x è un cavallo e x è un purosangue

Per ogni x

Esiste x


grossolano


∀x. Cavallo(x) ⊃ Mammifero(x)

∃x. Cavallo(x)⋀Purosangue(x)

Esempio“Tutti i corvi stanno su un albero”

Esempio“Tutti i corvi stanno su un albero”

(“Tutti gli studenti hanno una cartella”)

Nella logica di Frege…

∀x.(Corvo(x) ⊃ ∃y.Albero(y)⋀StaSu(x,y))

Nella logica di Frege…

∃y.Albero(y)⋀∀x.(Corvo(x) ⊃ StaSu(x,y))

Il piano di Frege• Come dimostrare che la sua logica è in grado di

catturare la matematica? • Idea: concentrarsi sull’aritmetica e i numeri naturali

• “Dio creò i numeri naturali, tutto il resto è creato dagli uomini” (Leopold Kronecker)

• Piano: fornire una teoria puramente logica dei numeri naturali (e delle loro operazioni)

• Risultato: “Le leggi fondamentali dell’aritmetica”. Vol. 1 (1893), Vol. 2 (1903).

Numeri in logica?• Idea: usare il concetto di insieme!

• Il “numero 3” diventa l’insieme di tutti gli insiemi con “tre elementi”

• Ma allora bisogna caratterizzare gli insiemi in logica. Tra le definizioni di Frege, si trova: • Assioma dell’esistenza.

Data una proprietà (es.: “essere uno studente diligente”) c’è sempre un insieme che caratterizza esattamente quella proprietà

La lettera di Russell a Frege

Bertrand Russell (1872 - 1970). Inglese. Filosofo, matematico, premio Nobel per la letteratura

Sono d’accordo con lei su tutte le cose essenziali […]

Trovo nei suoi lavori analisi, distinzioni e definizioni che invano si cercherebbero

nell’opera di altri logici. C’è solo un punto nel quale ho

incontrato una difficoltà…

16 luglio 1902, mentre il Volume 2 dell’opera di Frege è in stampa…

La demolizione del lavoro di FregeFrege reagisce alla “difficoltà” trovata da Russell aggiungendo di fretta una nota per il suo Volume 2.

””

Per uno scienziato non c’è niente di peggio che veder crollare i fondamenti del suo lavoro proprio quando questo è stato appena completato. Io sono stato messo in tale situazione da una lettera del signor Bertrand Russell.

Cosa contiene la lettera?Un esempio, semplice ma subdolo, che sfrutta la circolarità, o autoreferenza, per mostrare che il lavoro di Frege contiene un paradosso.

La circolarità è pericolosa• Io mi ciamo Marco.

La frase precedente contiene un errore.



• Questa frase contiene un erore.



• Questa frase contiene un erore.

• Questa frase contiene due erori.

Russell e il paradosso del barbiere

””

In un villaggio vi è un solo barbiere, un uomo ben sbarbato, che rade tutti e solo gli uomini del villaggio che non si radono da soli.

Russell e il paradosso del barbiere

””

In un villaggio vi è un solo barbiere, un uomo ben sbarbato, che rade tutti e solo gli uomini del villaggio che non si radono da soli.

Il barbiere rade sé stesso?

Il paradosso del barbiere

• In entrambi i casi, si cade in contraddizione • Se il barbiere si radesse da solo, non

varrebbe più la premessa che il barbiere rade solo chi non si rade da solo

• Se il barbiere non si radesse da solo, allora dovrebbe essere rasato dal barbiere, che però è lui stesso!

Essere o non essere

• Russell definisce la proprietà: “x non appartiene a sé stesso”

• Per l’assioma dell’esistenza, deve esistere un insieme che cattura questa proprietà

• Ma “l’insieme degli insiemi che non contengono sé stessi” è paradossale quanto l’esempio del barbiere. Quindi non può esistere.

Frege e il sogno di Leibniz• La Begriffschrift è, per Frege, la realizzazione del sogno di Leibniz • In realtà

• Leibniz immaginava un linguaggio capace di abbracciare tutte le verità scientifiche, non solo la “deduzione”

• Leibniz immaginava un sistema in grado di “calcolare” in modo efficiente • Frege non propone nessuna idea su come effettuare il

calcolo, né su come decidere se e quando fermarsi… • Punto fondamentale: il lavoro di Frege permette di studiare l’attività

matematica usando i suoi stessi metodi (di nuovo… circolarità!)

Oltre Frege• Russell e Whitehead “migliorano” il lavoro di Frege,

epurandolo dal paradosso del barbiere

• Evitare circolarità richiede di complicare assurdamente il linguaggio

• Risultato: enorme libro in tre volumi, i “Principia Mathematica” (1910, 1912, 1913)

• Per la prima volta, viene mostrato come l’approccio di Frege si può usare per catturare la matematica

Uno più uno fa ???Nei Principia Mathematica, servono centinaia di pagine per dimostrare che… 1+1=2

Hilbert alla riscossa

David Hilbert• Nasce nel 1862 a Königsberg (Prussia) • Muore a Göttingen (Germania) nel 1943 • Amante della vita pubblica, e contrario

all’ascesa del nazismo • Diviene prestissimo famoso per il suo

talento matematico (professore a 30 anni) • Nel 1900, propone una lista di 23

problemi fondamentali da risolvere • Alcuni sono tuttora irrisolti

Alcune curiosità• A sostenere grandi uomini ci sono sempre grandi

donne • Si dice che la moglie abbia letteralmente scritto

alcuni dei suoi articoli • Diventa famoso per una spettacolare dimostrazione di

un teorema molto complicato • Invece di dimostrare direttamente il teorema

(approccio costruttivo), dimostra che negarlo porterebbe a contraddizione

• Per alcuni matematici del tempo, “questa non è matematica, è teologia!”

Il programma di Hilbert• E’ ossessionato dal problema di studiare i fondamenti della

matematica, e provarne la correttezza

• Rinnega l’approccio “logicista” di Frege e Russel: per studiare la matematica, bisogna usare la matematica stessa!

• Ma come si può dimostrare “la correttezza” della matematica se si usano gli stessi metodi che si vorrebbero dimostrare corretti?

• Fonda un nuovo tipo di matematica, detta metamatematica, per lo studio delle dimostrazioni matematiche

Cosa significa “correttezza”?• Formalizzazione: le formule matematiche devono

seguire un linguaggio preciso, e chiare regole di manipolazione

• Completezza: la formalizzazione scelta deve essere in grado di derivare tutte le verità matematiche (teoremi)

• Coerenza: non deve essere possibile derivare formule che si contraddicono tra loro

• Decidibilità: deve esistere un procedimento per decidere se una formula matematica è vera o falsa

La sfida di Hilbert• Hilbert riesce a dimostrare la correttezza della

geometria, e quella della teoria dei numeri reali

• Ma per affrontare le fondamenta della matematica, bisogna studiare l’aritmetica e i numeri naturali!

• Sfida la comunità matematica nel 1928: dimostrare che sistemi formali come quello dei Principia Mathematica sono corretti

• Ovvero: permettono di derivare “in tempo finito” tutti e solo i teoremi dell’aritmetica

La disfatta di Hilbert• 1930: evento per celebrare il pensionamento di Hilbert

• Pronuncia il celebre motto “Wir müssen wissen, wir werden wissen”

• Altri logici e matematici tengono vari interventi in suo onore

• Tra loro, c’è un giovane di 24 anni che, timidamente, distrugge il programma di Hilbert

• Se ne accorge solo John von Neumann, considerato il padre dei moderni calcolatori

Gödel manda tutto per aria

Kurt Gödel• Nasce a Brno (Austria-Ungheria)

nel 1906

• Muore a Princeton (USA) nel 1978

• Il padre gestisce un’azienda tessile

• Soffre di febbri reumatiche fin da piccolo, ed è estremamente ipocondriaco

Curiosità• Considerato il più grande logico mai vissuto, assieme ad

Aristotele

• Partecipa al fervente circolo di Vienna dal 1926

• Ottiene un Dottorato in matematica nel 1930, demolendo parte del programma di Hilbert

• Scappa dalla Germania nazista senza accorgersi di quello che stava succedendo…

• Si trasferisce a Princeton, dove diventerà amico di Einstein e professore

Gödel “primo programmatore”Godel a computer programmer?

Il paradosso del mentitore

Tutti i cretesi sono bugiardi

Il paradosso del mentitore

Tutti i cretesi sono bugiardi

Epimenide… cretese!

Gödel usa Epimenide• Dimostra che i Principia Mathematica sono “completi”,

ovvero in grado di derivare tutti i teoremi dell’aritmetica

• Poi, però, rappresenta nei Principia Mathematica, la seguente formula F

F: “La formula X non è dimostrabile nei Principia Mathematica”

• Cosa succede se applichiamo F a sé stessa?

U: “La formula U non è dimostrabile nei Principia Mathematica”

Il paradosso di Gödel• U è vera?

• Sì! • Se fosse falsa, sarebbe vero che “U è

dimostrabile nei Principia Mathematica”, e quindi U dovrebbe essere vera (contraddizione)

• U è dimostrabile nei Principia Mathematica?

• NO! Dice esattamente il contrario…

Quindi…Parte del programma di Hilbert è fallito:

ci sono verità matematiche che non sono

dimostrabili in nessun sistema formale capace di catturare l’aritmetica

• Quale impatto ha, questo, sull’informatica? Ce lo dirà Alan Turing…

Il lato oscuro di Gödel• Pur essendo estremamente razionale… • Gödel è convinto dell’esistenza di fantasmi e altre

entità soprannaturali • Elimina dalla propria casa termosifoni e frigoriferi

per paura che emettano gas nocivi • Nell’ultima fase della sua vita, è convinto che

qualcuno voglia avvelenarlo • Morirà di inedia…

(ancora un esempio di “circolarità”)

Turing e il “calcolatore universale”

Alan Turing• Nasce a Londra (Inghilterra) nel 1912

• Muore a Winslow (Inghilterra) nel 1954

• Il padre lavora per il

• Alan non è solo il padre fondatore dell’informatica e dell’Intelligenza Artificiale, ma contribuisce alla risoluzione della seconda guerra mondiale

Curiosità

https://www.youtube.com/watch?v=5DtqX54DUFU

Da Leibniz a Turing• Affascinato dall’idea di Leibniz sul “calcolo

automatico”

• Frege, Russell e Whitehead hanno prodotto le regole per simulare il ragionamento umano

• Gödel ha dimostrato che queste regole sono complete (rispetto alla “dimostrabilità”)

• Per realizzare il sogno di Leibniz, bisogna ora risolvere il “problema della decisione”

Problema della decisioneSi può realizzare un “processo” capace di decidere in tempo finito se una certa formula si può derivare applicando le regole di Frege, Russell, Whitehead?

• L’esistenza di questo processo (algoritmo) realizzerebbe finalmente il sogno di Leibniz

Come calcola l’uomo?• Cosa fa una persona (ai tempi, tipicamente una donna)

quando deve moltiplicare due numeri? • Segue un procedimento, utilizzando tanta carta quanta ne

serve• In ogni momento

• è in un certo “stato mentale” (ora devo moltiplicare? O sommare?)

• osserva un insieme piccolo di tutti i simboli (due/tre cifre) • Decide cosa fare in base al proprio stato mentale e ai

simboli che sta osservando

La Macchina di Turing (TM)

• Opera su un nastro infinito, inizializzato con l’input richiesto • Ha una testina posizionata su una cella

• La testina può leggere e scrivere un simbolo sulla cella • Ha uno stato interno (scelto in un insieme finito) • Ha un programma costituito da un insieme finito di istruzioni.

Istruzioni• Ogni istruzione

• Si applica • Quando la macchina è in un certo stato interno • La testina sta leggendo un certo simbolo

• Se valgono queste premesse, l’operazione dice • Quale simbolo viene scritto nella cella corrente • Quale è il nuovo stato interno della macchina • Se la testina deve rimanere ferma o spostarsi di

una cella a dx o sx

La “TM dei dispari”• Alfabeto: cifre da 0 a 9, cella vuota • In input, il nastro contiene il numero da analizzare • Alla fine, il nastro è tutto vuoto tranne una cella, che

contiene “1” se il numero è dispari, “0” se il numero è pari

La “TM dei dispari”

Truing Machines in Action

Consider this Turing Machine

and applying it to this input

• Alfabeto: cifre da 0 a 9, cella vuota • In input, il nastro contiene il numero da analizzare • Alla fine, il nastro è tutto vuoto tranne una cella, che

contiene “1” se il numero è dispari, “0” se il numero è pari


Stop

Mai visti?

“Sempre a destra”Truing Machines have no physical limitations

Turing machine consisting of

Q ⇤ : ⇤ ! Q

when started on a blank tape will keep on moving right “forever”

Truing Machines have no physical limitations

Turing machine consisting of

Q ⇤ : ⇤ ! Q

when started on a blank tape will keep on moving right “forever”

“Qualche volta avanti”Truing Machines may not halt

Turing machine

Q 1 : 1! Q and Q 2 : 1 Q

Input 12 it will bounce back and forth while on input 13 it will halt

Truing Machines may not halt

Turing machine

Q 1 : 1! Q and Q 2 : 1 Q



Turing machine

Q 1 : 1! Q and Q 2 : 1 Q



Turing machine

Q 1 : 1! Q and Q 2 : 1 Q



Turing machine

Q 1 : 1! Q and Q 2 : 1 Q


Trova le differenze (1)

Trova le differenze (2)

Lo smartphone come “macchina universale”

• Cosa succede quando “scaricate una app” sul vostro cellulare?

1. La app viene salvata nella memoria del telefono 2. Il sistema operativo del telefono “interpreta” la app

come una serie di istruzioni 3. Il telefono “esegue” la app quando richiesto

Indirettamente, questo lo dobbiamo a Turing!!!

La TM universale• La “TM del dispari” esegue un solo compito molto

specifico

• E’ possibile realizzare una macchina “generale”?

• In particolare, una macchina che “esegue altre macchine”?

• Risposta: sì! Ma come?

Primo passoCoding a Turing machine as a natural number

Probably inspired by Godel Turing encoded a machine as a naturalnumber.Example:

• Machine for distinguishing between even and odd numbers

• List the instructions one after another separated by asemi-colon

Q 0 : ⇤ ! E ; Q 1 : ⇤ ! O ; Q 2 : ⇤ ! E ; . . .

• Replace each symbol by a string of decimal digits.

TM “specifica”

Coding a Turing machine as a natural number

Probably inspired by Godel Turing encoded a machine as a naturalnumber.Example:

• Machine for distinguishing between even and odd numbers

• List the instructions one after another separated by asemi-colon

Q 0 : ⇤ ! E ; Q 1 : ⇤ ! O ; Q 2 : ⇤ ! E ; . . .

• Replace each symbol by a string of decimal digits.


Say Q,E,O, F are coded by 99, 919, 929 and 939 and other symbols by

The Turing machine is then coded by the number (easy to decode number)Tabella di traduzione


Say Q,E,O, F are coded by 99, 919, 929 and 939 and other symbols by

The Turing machine is then coded by the number (easy to decode number)

Linearizza

Traduci

Secondo passo• Definire una TM capace di “interpretare” il numero

di un’altra TM inserito nel nastro, e applicarne il comportamento sull’input messo nella seconda parte del nastro

• Questa TM è “programmabile”, e assomiglia al funzionamento di un computer (interprete comandi)

• Questa TM può poi essere arricchita con altre istruzioni (quindi… tante TM universali)

Cosa possiamo calcolare con una TM universale?

Qualunque cosa Se non c’è una TM capace di risolvere un problema —> quel problema non si può

risolvere

Il problema della fermata• Abbiamo visto che:

• Alcune TM terminano sempre • Alcune TM non terminano mai • Alcune TM terminano o non terminano in base

all’input

• Se il problema della decisione è risolubile, allora deve essere risolubile anche decidere se ogni TM termina o meno dato un certo input

• Supponiamo sia vero.

Il problema della fermata• Definiamo una TM universale A fatta così:

• A prende in input una TM m (e un input x) • Basta rappresentare m con il suo numero

corrispondente

• A si ferma e restituisce 0 se m non si ferma (con input x)

• A si ferma e restituisce 1 se m si ferma (con input x)

Il problema della fermata

• Modifichiamo A ottenendo U

• U prende in input una TM m

• U si ferma e restituisce 1 se m non si ferma

• U entra in un ciclo infinito (ovvero non si ferma) se m si ferma

La circolarità ritorna

• Cosa succede se applichiamo U alla sua stessa codifica numerica?

• Otteniamo che: • U non si ferma se U si ferma • U si ferma se U non si ferma

La circolarità ritorna• Appena ci passa il mal di testa, concludiamo

• U si ferma se e solo se non si ferma: paradosso!

• Il problema della fermata è irresolubile • Quindi: non è possibile dire “in tempo finito” se una

formula è vera o meno, perché non so distinguere se il mio procedimento terminerà fra un po’ oppure non terminerà mai

• Il piano di Hilbert è completamente fallito

Conclusioni• Generazioni di pensatori hanno cercato di “meccanizzare

il pensiero logico-matematico” a partire dal sogno di Leibniz

• Nel farlo, hanno inaspettatamente scoperto quali sono i limiti della matematica

• Nello scoprire questi limiti, hanno contemporaneamente fatto nascere l’informatica • Turing usa le “macchine universali” per costruire un

risultato negativo • Ma questa idea apre la strada alla costruzione dei

moderni computer: l’architettura di von Neumann, base dei calcolatori, usa pienamente le idee di Turing

Cosa portare a casa• Differenza tra informatica e

tecnologia

• L’importanza del “pensiero laterale” e della “circolarità”

• L’importanza di combinare teoria e pratica

Montali - Da Leibniz a Turing: la nascita dei computer e la scoperta dei limiti della matematica

Presentations & Public Speaking

Transcript of Montali - Da Leibniz a Turing: la nascita dei computer e la scoperta dei limiti della matematica