Post on 09-Jan-2017
transcript
Da Leibniz a TuringLa nascita dei computer
e la scoperta dei limiti della matematica
Marco Montali montali@inf.unibz.it
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
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!
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 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
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? Prodotto!
• Ma… se x rappresenta una classe:
xx = ?(immaginate x = “pecore”)
Algebra per la logica• A cosa assomiglia xy? Prodotto!
• Ma… se x rappresenta una classe:
xx = x(immaginate x = “pecore”)
• L’algebra parla di quantità… per quali numeri è vero xx = x?
Algebra per la logica• A cosa assomiglia xy? Prodotto!
• Ma… se x rappresenta una classe:
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
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
“Per ogni” vs “Esiste”• Frege capisce che l’approccio di Boole è troppo
grossolano
• Differenza tra: Tutti i cavalli sono mammiferiAlcuni cavalli sono purosangue
Se x è un cavallo, allora x è un mammifero
x è un cavallo e x è un purosangue
“Per ogni” vs “Esiste”• Frege capisce che l’approccio di Boole è troppo
grossolano
• Differenza tra: Tutti i cavalli sono mammiferiAlcuni cavalli sono purosangue
Se x è un cavallo, allora x è un mammifero
x è un cavallo e x è un purosangue
Per ogni x
Esiste x
“Per ogni” vs “Esiste”• Frege capisce che l’approccio di Boole è troppo
grossolano
• Differenza tra: Tutti i cavalli sono mammiferiAlcuni cavalli sono purosangue
∀x. Cavallo(x) ⊃ Mammifero(x)
∃x. Cavallo(x)⋀Purosangue(x)
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.
La circolarità è pericolosa• Io mi ciamo Marco.
La frase precedente contiene un errore.
• 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
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
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 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à”)
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
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
“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”
“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”
“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
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
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
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
Input 12 it will bounce back and forth while on input 13 it will halt
“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
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
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
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
Input 12 it will bounce back and forth while on input 13 it will halt
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.
Coding a Turing machine as a natural number
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
Coding a Turing machine as a natural number
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