Ti piacciono le riviste di
meccanica?
Settant’anni di macchine di Turing
Francesco Belardinelli
Cortona - 30 Agosto 2005
Menù del giorno





Gli algoritmi: cosa sono e perchè sono importanti.
Le macchine di Turing: come sono fatte e come
funzionano.
La tesi di Church-Turing.
Le applicazioni delle MT: la macchina di Turing
universale e il problema della fermata.
Alcuni sviluppi: calcolabilità e complessità –
intelligenza artificiale.
Che cos’è un algoritmo?

Algoritmo o
procedura effettiva:
Regola meccanica o
metodo automatico o
programma per
eseguire una qualche
operazione
(matematica).
Abu Abdullah Muhammad bin Musa al-Khwarizmi
Alcuni esempi di algoritmi:





Preparare un piatto seguendo una ricetta.
Prenotare un volo in aereo su internet.
Dato n, trovare l’n-esimo numero primo (crivello
di Eratostene).
Trovare il MCD di due numeri naturali
(algoritmo di Euclide).
Sommare due numeri naturali x e y.
Sommare due numeri naturali x e y
INIZIO
si
y = 0?
no
x := x+1
y := y-1
no
y = 0?
si
Scrivi x
FINE
La struttura dell’algoritmo




Ha un inizio ed una fine.
Presenta un numero finito di passaggi.
Ogni passaggio è eseguibile in un tempo finito.
Ogni passaggio è determinato in modo univoco
dal passaggio precedente
L’algoritmo termina e il risultato appare dopo un
tempo finito.
Perchè sono importanti gli algoritmi?


Sono alla base della teoria dei calcolatori:
i computer lavorano attraverso algoritmi, ciò che
un calcolatore può o non può fare in linea di
principio è determinato dalla possibilità - o
impossibilità - di trovare algoritmi atti al nostro
scopo.
Si può ricavare un modello per il
comportamento intelligente.
Aspetto filosofico della questione:
 Chiarire
concettualmente che cosa sia
un procedimento effettivo e quali siano i
suoi caratteri formali.
Alan Mathison Turing (1912-54)


Durante la II GM, lavora
per il governo britannico
alla decodificazione del
codice E.N.I.G.M.A. usato
dalla Germania nazista.
Nell'articolo On computable
numbers, with an application to
the Entscheidungsproblem del
'37, introduce un
dispositivo – la Macchina
di Turing - per definire
rigorosamente la nozione
di procedimento effettivo.
Com’è fatta una macchina di Turing?


Una MT è composta da:
- Una nastro infinito verso destra, diviso in caselle. Ciascuna
casella contiene uno e un solo simbolo dall'alfabeto 0, 1.
- Un cursore che si sposta da una casella all'altra del nastro.
Ad ogni momento della computazione, la MT è in uno stato
qi. Gli stati della computazione sono in numero finito.
qi
01110111001110011111100
Com’è fatta una macchina di Turing?

Una MT può compiere tre tipi di operazioni:
- Cancellare il simbolo nella casella che il cursore
sta leggendo e rimpiazzarlo con un altro.
- Spostare il cursore una casella a destra della
casella che sta leggendo.
- Spostare il cursore una casella a sinistra della
casella che sta leggendo.
Com’è fatta una macchina di Turing?

Una MT contiene un programma, cioè una successione di
istruzioni del tipo qk, n, α, qj , dove:
- qk, qj sono stati della computazione,
- n può essere uguale a 0 o a 1,
- α può essere uguale a 0, a 1, allo spostamento a destra D, o allo
spostamento a sinistra S.

Esempio: l’istruzione q1, 0, D, q2 corrisponde al comando:
se ti trovi nello stato q1 e la casella che stai leggendo contiene il
simbolo 0, allora spostati una casella a destra e mettiti nello stato
q2.
Cosa calcola una macchina di Turing?

Esiste una MT per sommare due numeri naturali x e y:
- Le caselle contengono x+1 occorrenze di 1, seguite da uno 0 e
da altre y+1 occorrenze di 1. Le altre caselle contengono 0.
- MT contiene il seguente programma:
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q1
111011110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q1
111011110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q1
111011110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q1
111011110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q2
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q3
111111110
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q4
111111100
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q5
111111100
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
La somma di 2 e 3
q6
111111000
q1, 1, D, q1
q1, 0, 1, q2
q2, 1, D, q2
q2, 0, S, q3
q3, 1, 0, q4
q4, 0, S, q5
q5, 1, 0, q6
Diversi tipi di macchina di Turing

Il nastro è infinito nelle due direzioni destra/sinistra.
Il nastro è infinito in due dimensioni.
Il cursore può compiere spostamenti di più caselle.
La macchina di Turing ha più cursori.
L'alfabeto contiene un numero arbitrario finito di
simboli.
La macchina di Turing può essere non deterministica.

Tutti questi diversi modelli sono equivalenti!





Tesi di Church-Turing

Una funzione è computabile in senso informale
sse è computabile da una macchina di Turing.

Vi sono due motivi per ritenere vera la precedente affermazione:
- Non è stata ancora trovata una funzione, computabile in senso
informale, che non sia computabile da una MT.
- Precisazioni formali indipendenti della nozione di funzione
computabile individuano la medesima classe di funzioni:
funzioni ricorsive di Gödel (1936);
funzioni λ-definibili di Church (1936);
sistemi di Post (1943);
algoritmi di Markov (1951);
macchine universali a registri di Shepherdson e Sturgis (1963).
Lo studio delle macchine di Turing

Le macchine di Turing sono un'idealizzazione del funzionamento
di un calcolatore: se qualcosa è computabile da una MT, allora
possiamo sperare che prima o poi si costruisca un calcolatore in
grado di eseguire la medesima operazione.

Ma se non esiste alcuna MT in grado svolgere un determinato
compito, allora - per la tesi di Church-Turing - non vi è
possibilità di progettare un computer capace di risolvere il
problema in questione.

Lo studio delle MT ci fornisce i limiti di ciò che è - e sarà mai effettivamente calcolabile da un computer.
La codifica delle macchine di Turing

Possiamo associare ad ogni una macchina di Turing MT un
numero naturale nMT.

Assegniamo ai simboli 0, 1, D, S, i numeri 8558, 8018, 616, 626;
agli stati q1, . . . , qn, i numeri 919, . . . , 9n9.

All'istruzione q1, 1, D, q1 verrà assegnato il numero
9198018626919.

Al programma per sommare due numeri verrà assegnato il
codice
91980186269197791985588018929779298018626929779298558
62693977939801885589497794985586269597795980188558969.
La macchina di Turing Universale



Si possono usare le codifiche delle MT come
input per altre MT.
Nei moderni calcolatori i programmi e i dati
vengono inseriti nella macchina in un stesso
linguaggio binario.
Si dimostra che esiste una MT - la macchina di
Turing universale - che può svolgere qualsiasi
operazione eseguibile da una MT.
Come funziona una MTU?




Facciamo sommare alla MTU i numeri 2 e 3.
Inseriamo come input nella MTU il codice della MT per
sommare due numeri - cioè
9198018626919779198558801892977929801862692977
9298558626939779398018855894977949855862695977
95980188558969 - e i numeri 2 e 3.
La MTU decodifica il codice e ricava il programma per
sommare due numeri.
La MTU applica il programma agli input 2 e 3.
Il problema della fermata

Si può stabilire se dato un certo input n, a una
MT Mk, la computazione termina?

La risposta è negativa.
Il problema della fermata



Supponiamo che abbiamo un algoritmo per risolvere il
problema della fermata, definiamo la seguente funzione f:
f(k,n) =
0, se la computazione di Mk con input n non
termina
indefinita, altrimenti.
Per la TCT, se f è computabile in senso informale, allora esiste
una MT Mq che calcola f.
La computazione di Mq con input q termina?
- Se si, allora Mq(q) = j = f(q,q). Ma per def. f(q,q) è indefinita.
- Se no, allora Mq(q) = f(q,q) è indefinita. Ma per def. f(q,q) = 0.
La MTU e il problema della fermata

“Si può costruire un'automa
che può fare qualunque cosa
fa un altro automa, ma non si
può costruire un'automa che
predica il comportamento di
un automa arbitrario. In altre
parole, si può costruire un
organo che fa qualsiasi cosa
che può essere fatta, ma non
uno che dica se può essere
fatta.” - J. Von Neumann,
1949
Altri problemi irrisolvibili



Non vi è un metodo generale per stabilire se una MT
computa la funzione zero, cioè se per ogni n, MT(n) =
0.
Non vi è un metodo generale per stabilire se due
macchine di Turing MT e MT’ computano la stessa
funzione, cioè se per ogni n, MT(n) = MT’(n).
Non vi è un metodo generale per stabilire se una
formula del calcolo dei predicati è valida (lo
Entscheidungsproblem non è risolvibile).
Calcolabilità e complessità

Per le applicazioni ai calcolatori, non interessa solo che
esista un algoritmo per eseguire una certa operazione,
ma che l'algoritmo sia implementabili in tempo e spazio
ragionevoli.

Per eseguire una stessa operazione possono esistere
procedure più o meno efficienti.

Esempio: la MT per sommare due numeri x e y,
impiega x+y+7 passi di computazione.
Il comportamento delle api

Le api indicano alle compagne la posizione e la distanza
del cibo con una ‘danza’.

Possiamo attribuire alle api desideri e credenze?

Le MT ci forniscono un modello per spiegare il
comportamento delle api senza tirare in ballo
l’intenzionalità.

Pensare e calcolare sono una medesima cosa.
Intelligenza artificiale

Tesi forte dell'intelligenza artificiale: la mente
funziona come una macchina di Turing.

1950: Computing Machinery and Intelligence
Turing ritiene le operazioni computabili
sufficienti ad includere tutte le funzioni mentali
eseguite dal cervello.
Ramon Lull e l’Ars Magna



1235: nasce a Palma di
Majorca, impara l’arabo
dai mori e scrive in
latino.
1305-1307: "Ars
generalis ultima" (Ars
Magna).
1315: lapidato dai
saraceni a Tunisi.
Leibniz e la MathesisUniversalis



1666: De arte combinatoria
Progetto di una Characteristica
Universalis e di un Calculus
Ratiocinator.
“Se sorgessero delle
controversie, non ci sarebbe
maggior bisogno di
discussione tra due filosofi
rispetto a quanta ce ne sia tra
due ragionieri. Basterebbe
che prendessero le penne in
mano e si dicessero:
Calculemus!”
Bibliografia e risorse internet











Barker-Plummer D., Turing Machines, The Stanford Encyclopedia of Philosophy,
http://plato.stanford.edu/entries/turing-machine/, 2004.
Cutland N., Computability: An introduction to recursive function theory, Cambridge
University Press, Cambridge, 1980.
Davis M., The Universal Computer: the Road from Leibniz to Turing, W. W. Norton and
Company, New York, 2000.
Hodges A., Alan Turing: the Enigma, Walker, New York, 2000.
Hodges A., Alan Turing, The Stanford Encyclopedia of Philosophy,
http://plato.stanford.edu/entries/turing/, 2002.
Tamburrini G., I matematici e le macchine intelligenti, Bruno Mondadori, Milano, 2002
Turing A. M., On computables numbers, with an application to the Entscheidungsproblem,
Proceedings of the London Mathematical Society, 42, pp. 230-264, 1936.
Turing A. M., Computing machinery and intelligence, Mind, 50, pp. 433-460 1950.
Turing Digital Archive
Alan Turing Home Page
The Turing's World Homepage