Ti piacciono le riviste di meccanica? Settant’anni di macchine di Turing

Ti piacciono le Ti piacciono le riviste di riviste di

meccanica?meccanica? Settant’anni di macchine di Settant’anni di macchine di

TuringTuringFrancesco BelardinelliFrancesco Belardinelli

Cortona - 30 Agosto 2005Cortona - 30 Agosto 2005

Menù del giornoMenù del giorno

Gli algoritmiGli algoritmi: cosa sono e perchè sono : cosa sono e perchè sono importanti.importanti.

Le macchine di TuringLe macchine di Turing: come sono fatte e : come sono fatte e come funzionano.come funzionano.

La tesi di Church-TuringLa tesi di Church-Turing.. Le applicazioni delle MT: Le applicazioni delle MT: la macchina di la macchina di

Turing universaleTuring universale e e il problema della il problema della fermatafermata..

Alcuni sviluppi: Alcuni sviluppi: calcolabilità e calcolabilità e complessitàcomplessità – – intelligenza artificialeintelligenza artificiale..

Che cos’è un algoritmo?Che cos’è un algoritmo?

Algoritmo o Algoritmo o procedura effettiva:procedura effettiva:

Regola meccanica o Regola meccanica o metodo automatico metodo automatico o programma per o programma per eseguire una eseguire una qualche operazione qualche operazione (matematica).(matematica).

Abu Abdullah Muhammad bin Musa al-Abu Abdullah Muhammad bin Musa al-

KhwarizmiKhwarizmi

Alcuni esempi di Alcuni esempi di algoritmi:algoritmi:

Preparare un piatto seguendo una Preparare un piatto seguendo una ricetta.ricetta.

Prenotare un volo in aereo su Prenotare un volo in aereo su internet.internet.

Dato Dato nn, trovare l’, trovare l’nn-esimo numero -esimo numero primo (crivello di Eratostene).primo (crivello di Eratostene).

Trovare il MCD di due numeri naturali Trovare il MCD di due numeri naturali (algoritmo di Euclide).(algoritmo di Euclide).

Sommare due numeri naturali Sommare due numeri naturali xx e e yy..

Sommare due numeri Sommare due numeri naturali naturali xx e e yyINIZIOINIZIO

sisiyy = 0? = 0?

nonoxx := := xx+1+1

yy := := yy-1-1nono

yy = 0? = 0?sisi

Scrivi Scrivi xx

FINEFINE

La struttura La struttura dell’algoritmodell’algoritmo

Ha un inizio ed una fine.Ha un inizio ed una fine. Presenta un numero finito di passaggi.Presenta un numero finito di passaggi. Ogni passaggio è eseguibile in un tempo Ogni passaggio è eseguibile in un tempo

finito.finito. Ogni passaggio è determinato in modo Ogni passaggio è determinato in modo

univoco dal passaggio precedenteunivoco dal passaggio precedente

L’algoritmo termina e il risultato appare L’algoritmo termina e il risultato appare dopo un tempo finito.dopo un tempo finito.

Perchè sono importanti gli Perchè sono importanti gli algoritmi?algoritmi?

Sono alla base della teoria dei Sono alla base della teoria dei calcolatori: calcolatori:

i computer lavorano attraverso algoritmi, i computer lavorano attraverso algoritmi, ciò che un calcolatore può o ciò che un calcolatore può o nonnon può fare può fare in linea di principio è determinato dalla in linea di principio è determinato dalla possibilità - o impossibilità - di trovare possibilità - o impossibilità - di trovare algoritmi atti al nostro scopo.algoritmi atti al nostro scopo.

Si può ricavare un modello per il Si può ricavare un modello per il comportamento intelligente.comportamento intelligente.

Aspetto filosofico della Aspetto filosofico della questione:questione:

Chiarire concettualmente che Chiarire concettualmente che cosa sia un cosa sia un procedimento procedimento effettivoeffettivo e quali siano i suoi e quali siano i suoi caratteri formali.caratteri formali.

Alan Mathison Turing Alan Mathison Turing (1912-54)(1912-54)

Durante la II GM, lavora Durante la II GM, lavora per il governo britannico per il governo britannico alla decodificazione del alla decodificazione del codice E.N.I.G.M.A. usato codice E.N.I.G.M.A. usato dalla Germania nazista. dalla Germania nazista.

Nell'articolo Nell'articolo On On computable numbers, computable numbers, with an application to the with an application to the EntscheidungsproblemEntscheidungsproblem del '37, introduce un del '37, introduce un dispositivo – la Macchina dispositivo – la Macchina di Turing - per definire di Turing - per definire rigorosamente la nozione rigorosamente la nozione di di procedimento effettivoprocedimento effettivo..

Com’è fatta una macchina Com’è fatta una macchina di Turing?di Turing?

Una MT è composta da:Una MT è composta da:

- Una nastro infinito verso destra, diviso in caselle. - Una nastro infinito verso destra, diviso in caselle. Ciascuna casella contiene uno e un solo simbolo Ciascuna casella contiene uno e un solo simbolo dall'alfabeto 0, 1.dall'alfabeto 0, 1.

- Un cursore che si sposta da una casella all'altra del - Un cursore che si sposta da una casella all'altra del nastro.nastro.

Ad ogni momento della computazione, la MT è in uno stato Ad ogni momento della computazione, la MT è in uno stato qqii. Gli stati della computazione sono in numero finito.. Gli stati della computazione sono in numero finito.

qqii

0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0


Una MT può compiere tre tipi di Una MT può compiere tre tipi di operazioni:operazioni:

- Cancellare il simbolo nella casella che - Cancellare il simbolo nella casella che il cursore sta leggendo e rimpiazzarlo il cursore sta leggendo e rimpiazzarlo con un altro.con un altro.

- Spostare il cursore una casella a - Spostare il cursore una casella a destra della casella che sta leggendo.destra della casella che sta leggendo.

- Spostare il cursore una casella a - Spostare il cursore una casella a sinistra della casella che sta leggendo.sinistra della casella che sta leggendo.


Una MT contiene un programma, cioè una Una MT contiene un programma, cioè una successione di istruzioni del tipo successione di istruzioni del tipo qqkk, n, , n, αα, q, qj j , dove:, dove:

- - qqkk,, qqjj sono stati della computazione, sono stati della computazione,- - nn può essere uguale a 0 o a 1, può essere uguale a 0 o a 1,- - αα può essere uguale a 0, a 1, allo spostamento a può essere uguale a 0, a 1, allo spostamento a destra destra DD, o allo spostamento a sinistra , o allo spostamento a sinistra SS..

Esempio: l’istruzione Esempio: l’istruzione qq11, 0, , 0, DD, , qq22 corrisponde al corrisponde al comando:comando:

se ti trovi nello stato se ti trovi nello stato qq11 e la casella che stai e la casella che stai leggendo contiene il simbolo 0, allora spostati una leggendo contiene il simbolo 0, allora spostati una casella a destra e mettiti nello stato casella a destra e mettiti nello stato qq22..

Cosa calcola una macchina di Cosa calcola una macchina di Turing?Turing?

Esiste una MT per sommare due numeri naturali Esiste una MT per sommare due numeri naturali xx e e yy::- Le caselle contengono - Le caselle contengono xx+1 occorrenze di 1, seguite +1 occorrenze di 1, seguite da uno 0 e da altre da uno 0 e da altre yy+1 occorrenze di 1. Le altre +1 occorrenze di 1. Le altre caselle contengono 0.caselle contengono 0.- MT contiene il seguente programma:- MT contiene il seguente programma:

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66

La somma di 2 e 3La somma di 2 e 3

qq11

1 1 1 0 1 1 1 1 1 0 1 1 1 1 01 1 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq22

1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 1 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq22

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq33

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 01 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq44

1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 00 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq55

1 1 1 1 1 1 1 1 1 1 1 1 1 0 01 0 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66


qq66

1 1 1 1 1 1 1 1 1 1 1 1 0 0 00 0 0

qq11, 1, , 1, DD, , qq11

qq11, 0, 1, , 0, 1, qq22

qq22, 1, , 1, DD, , qq22

qq22, 0, , 0, SS, , qq33

qq33, 1, 0, , 1, 0, qq44

qq44, 0, , 0, SS, , qq55

qq55, 1, 0, , 1, 0, qq66

Diversi tipi di macchina di Diversi tipi di macchina di TuringTuring

Il nastro è infinito nelle due direzioni Il nastro è infinito nelle due direzioni destra/sinistra.destra/sinistra.

Il nastro è infinito in due dimensioni.Il nastro è infinito in due dimensioni. Il cursore può compiere spostamenti di più Il cursore può compiere spostamenti di più

caselle.caselle. La macchina di Turing ha più cursori.La macchina di Turing ha più cursori. L'alfabeto contiene un numero arbitrario finito di L'alfabeto contiene un numero arbitrario finito di

simboli.simboli. La macchina di Turing può essere non La macchina di Turing può essere non

deterministica.deterministica.

Tutti questi diversi modelli sono equivalenti!Tutti questi diversi modelli sono equivalenti!

Tesi di Church-TuringTesi di Church-Turing Una funzione è computabile in senso Una funzione è computabile in senso

informale sse è computabile da una informale sse è computabile da una macchina di Turing.macchina di Turing.

Vi sono due motivi per ritenere vera la precedente Vi sono due motivi per ritenere vera la precedente affermazione:affermazione:- Non è stata ancora trovata una funzione, computabile in - Non è stata ancora trovata una funzione, computabile in senso informale, che non sia computabile da una MT.senso informale, che non sia computabile da una MT.- Precisazioni formali indipendenti della nozione di - Precisazioni formali indipendenti della nozione di funzione computabile individuano la medesima classe di funzione computabile individuano la medesima classe di funzioni:funzioni:funzioni ricorsive di Gfunzioni ricorsive di Göödel (1936);del (1936);funzioni funzioni λλ-definibili di Church (1936); -definibili di Church (1936); sistemi di Post (1943); sistemi di Post (1943); algoritmi di Markov (1951); algoritmi di Markov (1951); macchine universali a registri di Shepherdson e Sturgis (1963).macchine universali a registri di Shepherdson e Sturgis (1963).

Lo studio delle macchine di Lo studio delle macchine di TuringTuring

Le macchine di Turing sono un'idealizzazione del Le macchine di Turing sono un'idealizzazione del funzionamento di un calcolatore: se qualcosa è funzionamento di un calcolatore: se qualcosa è computabile da una MT, allora possiamo sperare che computabile da una MT, allora possiamo sperare che prima o poi si costruisca un calcolatore in grado di prima o poi si costruisca un calcolatore in grado di eseguire la medesima operazione.eseguire la medesima operazione.

Ma se non esiste alcuna MT in grado svolgere un Ma se non esiste alcuna MT in grado svolgere un determinato compito, allora - per la tesi di Church-determinato compito, allora - per la tesi di Church-Turing - non vi è possibilità di progettare un Turing - non vi è possibilità di progettare un computer capace di risolvere il problema in computer capace di risolvere il problema in questione.questione.

Lo studio delle MT ci fornisce i limiti di ciò che è - e Lo studio delle MT ci fornisce i limiti di ciò che è - e sarà mai - effettivamente calcolabile da un computer.sarà mai - effettivamente calcolabile da un computer.

La codifica delle macchine La codifica delle macchine di Turingdi Turing

Possiamo associare ad ogni una macchina di Turing MT Possiamo associare ad ogni una macchina di Turing MT un numero naturale un numero naturale nnMTMT..

Assegniamo ai simboli 0, 1, Assegniamo ai simboli 0, 1, DD, , SS, i numeri 8558, 8018, , i numeri 8558, 8018, 616, 626; agli stati 616, 626; agli stati qq11, . . . , , . . . , qqnn, i numeri 919, . . . , 9, i numeri 919, . . . , 9n9n9..

All'istruzione All'istruzione qq11, 1, , 1, DD, , qq11 verrà assegnato il numero verrà assegnato il numero 9198018626919.9198018626919.

Al programma per sommare due numeri verrà assegnato Al programma per sommare due numeri verrà assegnato il codice il codice 919801862691991980186269197777919855880189299198558801892977779298018626929929801862692977779298558626939929855862693977779398018855894993980188558949777794985586269949855862695959777795980188558969.95980188558969.

La macchina di Turing La macchina di Turing UniversaleUniversale

Si possono usare le codifiche delle MT Si possono usare le codifiche delle MT come input per altre MT.come input per altre MT.

Nei moderni calcolatori i programmi e Nei moderni calcolatori i programmi e i dati vengono inseriti nella macchina i dati vengono inseriti nella macchina in un stesso linguaggio binario.in un stesso linguaggio binario.

Si dimostra che esiste una MT - la Si dimostra che esiste una MT - la macchina di Turing universale - che macchina di Turing universale - che può svolgere qualsiasi operazione può svolgere qualsiasi operazione eseguibile da una MT.eseguibile da una MT.

Come funziona una Come funziona una MTU?MTU?

Facciamo sommare alla MTU i numeri 2 e 3.Facciamo sommare alla MTU i numeri 2 e 3. Inseriamo come input nella MTU il codice Inseriamo come input nella MTU il codice

della MT per sommare due numeri - cioè della MT per sommare due numeri - cioè 919801862691991980186269197777919855880189299198558801892977779298092980186269291862692977779298558626939929855862693977779398018855893980188558949949777794985586269599498558626959777795980188558969 - e 95980188558969 - e i numeri 2 e 3.i numeri 2 e 3.

La MTU decodifica il codice e ricava il La MTU decodifica il codice e ricava il programma per sommare due numeri. programma per sommare due numeri.

La MTU applica il programma agli input 2 e 3.La MTU applica il programma agli input 2 e 3.

Il problema della fermataIl problema della fermata

Si può stabilire se dato un certo Si può stabilire se dato un certo input input nn, a una MT M, a una MT Mkk, la , la computazione termina?computazione termina?

La risposta è negativa.La risposta è negativa.

Il problema della fermataIl problema della fermata Supponiamo che abbiamo un algoritmo per risolvere il Supponiamo che abbiamo un algoritmo per risolvere il

problema della fermata, definiamo la seguente problema della fermata, definiamo la seguente funzione funzione ff::

ff((kk,,nn) =) = 0, se la computazione di M0, se la computazione di Mkk con input con input nn non non termina termina

indefinita, altrimenti.indefinita, altrimenti. Per la TCT, se Per la TCT, se f f è computabile in senso informale, è computabile in senso informale,

allora esiste una MT Mallora esiste una MT Mqq che calcola che calcola f.f. La computazione di MLa computazione di Mqq con input con input qq termina? termina?

- Se si, allora M- Se si, allora Mqq((qq) = ) = jj = = ff((qq,,qq). Ma per def. ). Ma per def. ff((qq,,qq) è ) è indefinita.indefinita.

- Se no, allora M- Se no, allora Mqq((qq) = ) = ff((qq,,qq) è indefinita. Ma per def. ) è indefinita. Ma per def. ff((qq,,qq) = 0.) = 0.

La MTU e il problema della La MTU e il problema della fermatafermata

““Si può costruire Si può costruire un'automa che può fare un'automa che può fare qualunque cosa fa un qualunque cosa fa un altro automa, ma non si altro automa, ma non si può costruire un'automa può costruire un'automa che predica il che predica il comportamento di un comportamento di un automa arbitrario. In altre automa arbitrario. In altre parole, si può costruire un parole, si può costruire un organo che fa qualsiasi organo che fa qualsiasi cosa che può essere fatta, cosa che può essere fatta, ma non uno che dica se ma non uno che dica se può essere fatta.” - J. Von può essere fatta.” - J. Von Neumann, 1949Neumann, 1949

Altri problemi Altri problemi irrisolvibiliirrisolvibili

Non vi è un metodo generale per stabilire se Non vi è un metodo generale per stabilire se una MT computa la funzione zero, cioè se una MT computa la funzione zero, cioè se per ogni per ogni nn, MT(, MT(nn) = 0.) = 0.

Non vi è un metodo generale per stabilire se Non vi è un metodo generale per stabilire se due macchine di Turing MT e MT’ due macchine di Turing MT e MT’ computano la stessa funzione, cioè se per computano la stessa funzione, cioè se per ogni ogni nn, MT(, MT(nn) = MT’() = MT’(nn).).

Non vi è un metodo generale per stabilire se Non vi è un metodo generale per stabilire se una formula del calcolo dei predicati è valida una formula del calcolo dei predicati è valida (lo (lo EntscheidungsproblemEntscheidungsproblem non è risolvibile). non è risolvibile).

Calcolabilità e Calcolabilità e complessitàcomplessità

Per le applicazioni ai calcolatori, non Per le applicazioni ai calcolatori, non interessa solo che esista un algoritmo per interessa solo che esista un algoritmo per eseguire una certa operazione, ma che eseguire una certa operazione, ma che l'algoritmo sia implementabili in tempo e l'algoritmo sia implementabili in tempo e spazio ragionevoli. spazio ragionevoli.

Per eseguire una stessa operazione possono Per eseguire una stessa operazione possono esistere procedure più o meno efficienti.esistere procedure più o meno efficienti.

Esempio: la MT per sommare due numeri Esempio: la MT per sommare due numeri xx e e yy, impiega , impiega xx++yy+7 passi di computazione.+7 passi di computazione.

Il comportamento delle Il comportamento delle apiapi

Le api indicano alle compagne la posizione e Le api indicano alle compagne la posizione e la distanza del cibo con una ‘danza’.la distanza del cibo con una ‘danza’.

Possiamo attribuire alle api desideri e Possiamo attribuire alle api desideri e credenze?credenze?

Le MT ci forniscono un modello per spiegare Le MT ci forniscono un modello per spiegare il comportamento delle api senza tirare in il comportamento delle api senza tirare in ballo l’intenzionalità.ballo l’intenzionalità.

Pensare e calcolare sono una medesima cosa.Pensare e calcolare sono una medesima cosa.

Intelligenza artificialeIntelligenza artificiale

Tesi forte dell'intelligenza artificiale: la Tesi forte dell'intelligenza artificiale: la mente funziona come una macchina di mente funziona come una macchina di Turing.Turing.

1950: 1950: Computing Machinery and Computing Machinery and IntelligenceIntelligence

Turing ritiene le operazioni computabili Turing ritiene le operazioni computabili sufficienti ad includere tutte le sufficienti ad includere tutte le funzioni mentali eseguite dal cervello.funzioni mentali eseguite dal cervello.

Ramon Lull e l’Ramon Lull e l’Ars Ars MagnaMagna

1235: nasce a 1235: nasce a Palma di Majorca, Palma di Majorca, impara l’arabo dai impara l’arabo dai mori e scrive in mori e scrive in latino.latino.

1305-1307: "Ars 1305-1307: "Ars generalis ultima" generalis ultima" ((Ars MagnaArs Magna). ).

1315: lapidato dai 1315: lapidato dai saraceni a Tunisi.saraceni a Tunisi.

Leibniz e la Leibniz e la MathesisUniversalisMathesisUniversalis

1666: 1666: De arte combinatoriaDe arte combinatoria Progetto di una Progetto di una

Characteristica UniversalisCharacteristica Universalis e di un e di un Calculus Calculus RatiocinatorRatiocinator..

““Se sorgessero delle Se sorgessero delle controversie, non ci controversie, non ci sarebbe maggior bisogno sarebbe maggior bisogno di discussione tra due di discussione tra due filosofi rispetto a quanta ce filosofi rispetto a quanta ce ne sia tra due ragionieri. ne sia tra due ragionieri. Basterebbe che Basterebbe che prendessero le penne in prendessero le penne in mano e si dicessero: mano e si dicessero: Calculemus!”Calculemus!”

Bibliografia e risorse Bibliografia e risorse internetinternet

Barker-Plummer DBarker-Plummer D., ., Turing MachinesTuring Machines, The Stanford Encyclopedia of , The Stanford Encyclopedia of Philosophy, Philosophy, http://http://plato.stanford.edu/entries/turing-machine/plato.stanford.edu/entries/turing-machine/, 2004., 2004.

Cutland NCutland N., ., Computability: An introduction to recursive function Computability: An introduction to recursive function theorytheory, Cambridge University Press, Cambridge, 1980., Cambridge University Press, Cambridge, 1980.

Davis MDavis M., ., The Universal Computer: the Road from Leibniz to TuringThe Universal Computer: the Road from Leibniz to Turing, , W. W. Norton and Company, New York, 2000.W. W. Norton and Company, New York, 2000.

Hodges AHodges A., ., Alan Turing: the EnigmaAlan Turing: the Enigma, Walker, New York, 2000., Walker, New York, 2000. Hodges AHodges A., ., Alan TuringAlan Turing, The Stanford Encyclopedia of Philosophy, , The Stanford Encyclopedia of Philosophy,

http://http://plato.stanford.edu/entries/turing/plato.stanford.edu/entries/turing/, 2002., 2002. Tamburrini GTamburrini G., ., I matematici e le macchine intelligentiI matematici e le macchine intelligenti, Bruno , Bruno

Mondadori, Milano, 2002Mondadori, Milano, 2002 Turing A. MTuring A. M., ., On computables numbers, with an application to the On computables numbers, with an application to the

EntscheidungsproblemEntscheidungsproblem, Proceedings of the London Mathematical , Proceedings of the London Mathematical Society, 42, pp. 230-264, 1936.Society, 42, pp. 230-264, 1936.

Turing A. MTuring A. M., ., Computing machinery and intelligenceComputing machinery and intelligence, Mind, 50, pp. , Mind, 50, pp. 433-460 1950.433-460 1950.

Turing Digital ArchiveTuring Digital Archive Alan Turing Home PageAlan Turing Home Page The Turing's World HomepageThe Turing's World Homepage

Ti piacciono le riviste di meccanica? Settant’anni di macchine di Turing

Documents

Transcript of Ti piacciono le riviste di meccanica? Settant’anni di macchine di Turing