Cenni sulle
Macchine di Turing
corrado bonfanti - 2010
MACCHINA DI TURING
AS *
nastro
cella
finestra
area programma *
( * su un foglio di carta )
matita
gomma
MACCHINA DI TURING
AS *
nastro
cella
finestra
area programma *
?
( * su un foglio di carta )
matita
gomma
MACCHINA DI TURING
AS *
nastro
cella
finestra
area programma *
?
( * su un foglio di carta )
matita
gomma
Sembra opportuno qualche approfondimento, per il quale adotteremo un
approccio elementare, senza chiamare in causa strumenti più sofisticati quali
ad esempio le funzioni ricorsive primitive.
In quello che segue, l’Esempio, gli Esercizi proposti e le relative Soluzioni
possono essere fruiti anche come una sorta di introduzione alla
programmazione delle macchine (o automi) a stati finiti.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
(TM: Turing Machine)
Cella
Nastro
Nastro: è suddiviso in celle e lo si suppone illimitato (ovvero prolungabile a
piacere tanto a destra quanto a sinistra).
Ogni cella contiene un solo carattere tra quelli ammessi, compresi nell’alfabeto
dei caratteri C = {c*,c1,c2, … cn} (vedi appresso).
Il nastro, dietro apposito comando (vedi appresso), può rimanere fermo oppure
scorrere di una cella verso destra o verso sinistra.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
Finestra di
lettura/scrittura
(CC)
CC
Cella
Nastro
Finestra di lettura/scrittura: individua una cella del nastro detta cella
corrente e designata come CC.
La finestra è in posizione fissa e il nastro può scorrere sotto di essa.
La notazione (CC) designa il simbolo contenuto in CC.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
Area di
Controllo
Finestra di
lettura/scrittura
(CC)
(AC)
Cella
Nastro
Area di Controllo: una zona, designata come AC, destinata a contenere (uno
alla volta) i simboli dell’insieme S = {s*,s1,s2, … sk}, che designano i cosiddetti
stati della TM (vedi appresso).
La notazione (AC) designa il simbolo contenuto di AC.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
Area di
Controllo
Finestra di
lettura/scrittura
(CC)
(AC)
Cella
Nastro
Insiemi dei simboli
Simboli
Alfabeto dei caratteri
C = {c*,c1,c2, … cn}
Stati
S = {s*,s1,s2, … sk}
Movimenti
M = {D,S,F}
C ed S sono l’insieme dei simboli che, uno alla volta,
possono comparire rispettivamente in una cella del
nastro e nell’area di controllo.
C ed S sono definiti in relazione al compito che una
specifica MT deve assolvere, ma devono contenere
rispettivamente il simbolo c* (uno “pseudosimbolo”
per la cella vuota) ed s* (stop), o loro equivalenti.
I tre simboli di M comandano l’eventuale scorrimento
del nastro: di una cella verso Destra; di una cella
verso Sinistra; nastro Fermo.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
Area di
Controllo
Finestra di
lettura/scrittura
(AC)
(CC)
Cella
Nastro
Programma
Simboli
Alfabeto dei caratteri
C = {c*,c1,c2, … cn}
s1
s2
s3
...
c*
c1
Stati
S = {s*,s1,s2, … sk}
c2
c,m,s
...
Movimenti
M = {D,S,F}
cn
Istruzione con indirizzo c2, s2
sk
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
Programma: tabella a doppia entrata (matrice) in cui
- Le colonne sono intestate con tutti i simboli di stato compresi in
S = {s*,s1,s2, … sk}, con l’esclusione di s*.
- Le righe sono intestate con tutti i caratteri dell’alfabeto C = {c*,c1,c2, … cn}.
Istruzione: è il contenuto di un elemento della tabella, costituito da una
terna ordinata di simboli c,m,s in cui
- c è un carattere dell’alfabeto C = {c*,c1,c2, … cn}.
- m è uno dei tre comandi di movimento compresi in M = {D,S,F}.
- s è uno degli stati presenti in S = {s*,s1,s2, … sk}.
Le coordinate
dell’elemento della tabella
(c2 e s2 nella figura)
c*
definiscono l’indirizzo
c1
dell’istruzione in esso
contenuta.
c2
Programma
s1
s2
s3
...
c,m,s
...
cn
Istruzione con indirizzo c2,s2
sk
FUNZIONAMENTO
DI UNA TM
AC
c3
c2
c2
c3
c2
L’istruzione da eseguire (istruzione corrente) è
quella che sta scritta all’indirizzo (CC),(AC)
ovvero c2,s2. L’esecuzione consta di tre passi: c*
c1
s1
s2
s2
c1
c2
...
c1,S,s5
...
FUNZIONAMENTO
DI UNA TM
passo 1
AC
c3
c2
c2
c3
c2
c1
s2
c3
c2
c1
c3
c2
c1
s2
L’istruzione da eseguire (istruzione corrente) è
quella che sta scritta all’indirizzo (CC),(AC)
ovvero c2,s2. L’esecuzione consta di tre passi:
1 - Si cancella (CC) e si trascrive c1 (primo
simbolo dell’istruzione corrente) in CC.
s1
s2
c*
c1
c2
...
c1,S,s5
...
AC
FUNZIONAMENTO
DI UNA TM
c3
c2
c2
c3
c2
c1
s2
passo 1
c3
c2
c1
c3
c2
c1
s2
c2
c1
c3
c2
passo 2
c3
L’istruzione da eseguire (istruzione corrente) è
quella che sta scritta all’indirizzo (CC),(AC)
ovvero c2,s2. L’esecuzione consta di tre passi:
c1
s1
s2
s2
c*
1 - Si cancella (CC) e si trascrive c1 (primo
simbolo dell’istruzione corrente) in CC.
c1
2 - Si sposta il nastro di una cella verso
Sinistra, come indicato dal secondo simbolo
dell’istruzione corrente.
...
c2
c1,S,s5
...
AC
FUNZIONAMENTO
DI UNA TM
c3
c2
c2
c3
c2
c1
s2
passo 1
c3
c2
c1
c3
c2
c1
s2
c2
c1
c3
c2
passo 2
passo 3
c3
L’istruzione da eseguire (istruzione corrente) è
quella che sta scritta all’indirizzo (CC),(AC)
ovvero c2,s2. L’esecuzione consta di tre passi:
c1
s1
s5
s2
...
c*
1 - Si cancella (CC) e si trascrive c1 (primo
simbolo dell’istruzione corrente) in CC.
c1
2 - Si sposta il nastro di una cella verso
Sinistra, come indicato dal secondo simbolo
dell’istruzione corrente.
...
c2
c1,S,s5
3 - Si cancella (AC) e si trascrive il terzo simbolo s5 in AC.
La prossima istruzione da eseguire è pertanto quella all’indirizzo (CC),(AC)
ovvero c3,s5 (non presente nella figura).
N.b. Se il terzo simbolo fosse stato s*, la TM si sarebbe arrestata.
ESEMPIO: la Macchina “+ 1”
Adottiamo l’alfabeto
C = {c*,0,1,2,3,4,5,6,7,8,9}
e programmiamo la TM in modo che essa
fornisca in output il numero n+1,
essendo n  0 il numero intero (input)
scritto inizialmente sul nastro e delimitato
da almeno una cella vuota a destra e a
sinistra. Il tutto nella normale notazione
decimale, con partenza e arresto sulla cella
che contiene la cifra delle unità.
Questo esempio è tratto, con adattamenti del docente, da:
M.Italiani, G.Serazzi Elementi di informatica; Etas Kompass,
1973, pp.115-117.
ESEMPIO: la Macchina “+ 1”
Adottiamo l’alfabeto
C = {c*,0,1,2,3,4,5,6,7,8,9}
e programmiamo la TM in modo che essa
fornisca in output il numero n+1,
essendo n  0 il numero intero (input)
scritto inizialmente sul nastro e delimitato
da almeno una cella vuota a destra e a
sinistra. Il tutto nella normale notazione
decimale, con partenza e arresto sulla cella
che contiene la cifra delle unità.
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
Il programma qui a fianco risolve il
problema con S = {s1,s2} e ponendo
inizialmente (AC) = s1.
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
Si veda qui appresso lo sviluppo completo
del caso in cui n = 299.
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
9,s1 //
2
9
CC
AC
9
s1
inizio
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
9,s1 //
2
9
CC
AC
9
s1
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
9,s1 // 0,D,s1
2
9
CC
AC
9
s1
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
2
CC
AC
9
9
s1
2
9
9,s1 // 0,D,s1
0
s1
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
2
CC
AC
9
9
s1
2
9
9,s1 // 0,D,s1
9,s1 //
0
s1
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
2
CC
AC
9
9
s1
2
9
9,s1 // 0,D,s1
0
9,s1 //
… e così avanti,
istruzione per istruzione ...
s1
ESEMPIO: la Macchina “+ 1”
programma per la
Macchina “+1”
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
2,S,s2 1,S,s2
2
3,S,s2 2,S,s2
3
4,S,s2 3,S,s2
4
5,S,s2 4,S,s2
esecuzione del programma “+1”; inizio con n = 299 e (AC) iniziale = s1
sequenza delle
istruzioni da eseguire
(indirizzo // istruzione)
CC
AC
9
9
s1
2
9
0
2
0
3
0
0
3
0
0
0
0
3
0
2
9,s1 // 0,D,s1
s1
9,s1 // 0,D,s1
0
s1
2,s1 // 3,S,s2
s2
0,s2 // 0,S,s2
5
6,S,s2 5,S,s2
6
7,S,s2 6,S,s2
7
8,S,s2 7,S,s2
8
9,S,s2 8,S,s2
9
0,D,s1 9,S,s2
s2
0,s2 // 0,S,s2
3
s2
c*,s2 // c*,D,s*
0
s*
fine
Esercizi proposti
1 - Sviluppare l’esecuzione della Macchina “+1”, ponendo come input numeri
non negativi di vostra scelta.
2 - Costruire l’algoritmo “+12” per numeri in notazione binaria, ovvero
ponendo C = {c*,0,1} e lasciando invariate le altre condizioni date per “+1”.
(Oltre a risultare più compatto, questo algoritmo avrà il pregio di rendere più
evidente la logica ad esso sottostante.)
3 - Costruire la Macchina “RdS” (Riconoscitore di Sequenze):
- RdS opera sull’alfabeto C = {c*,a,b}
- sul nastro è impressa, in celle contigue, una stringa disordinata, non nulla e
finita, di simboli “a” e “b”, preceduta e seguita da (almeno) una cella vuota;
- la CC iniziale è la prima cella di sinistra della stringa;
- il compito di RdS consiste nell’individuare, se esiste, la prima occorrenza,
entro la stringa, della sequenza di simboli “abba” in quattro celle contigue;
- se tale sequenza viene individuata, RdS si arresta sulla cella di destra della
sequenza; se essa non si presenta mai entro la stringa, RdS si arresta sulla
prima cella vuota a destra della stringa.
Una possibile soluzione di 2 e 3 è data nell’Appendice.
Commenti
La prima idea fondamentale in base alla quale Turing ha concepito la sua “macchina”
consiste nello scomporre l’algoritmo di calcolo nei passi più elementari, si potrebbe dire
“atomici”, a cui si può ridurre il modo di procedere di un calcolatore umano. Questi,
reciprocamente, può eseguire il “programma-algoritmo” senza esplicare alcuna
decisione o ragionamento “intelligente”.
Infatti gli si chiede soltanto di armarsi di carta, matita e gomma da cancellare e di
attenersi acriticamente alle istruzioni del programma e alle regole di funzionamento.
Si tratta quindi di un procedimento puramente meccanico che, in linea di principio, può
essere eseguito da una macchina dotata degli opportuni automatismi.
Si noti che la descrizione della TM che abbiamo dato nelle slide precedenti (come pure
la macchina “+1” usata come esempio) è alquanto differente dall’impostazione
originaria che Turing ha esposto nei paragrafi 1-5 del suo celebre articolo On
Computable Numbers, with an Application to the Entscheidungsproblem.[1]
[1] L’articolo
(pubblicato nei Proceedings of the London Mathematical Society, vol.42, 1936-7, pp.230-265) si
conclude con un’appendice in cui Turing dimostra l’equivalenza tra la sua nozione di computabilità e il
λ-calcolo che Alonzo Church aveva introdotto in un articolo di poco precedente. Da un lato quindi Turing si
metteva all’altezza del già rinomato Church e, dall’atro, rivendicava la differenza e l’originalità del proprio
approccio. Questa appendice Turing la scrisse durante il suo lungo soggiorno a Princeton (1936-8) durante il
quale fu a contatto diretto con lo stesso Church e con altri personaggi dell’università e dello IAS (p.e. Kleene e
von Neumann). Subito dopo, sempre a Princeton, scrisse una breve nota per correggere alcune inesattezze
formali che gli erano state segnalate da P. Bernays (la nota è nello stesso volume dei Proceedings, pp.544-546).
La più appariscente delle differenze che abbiamo introdotto consiste nel fatto che Turing
presenta l’istruzione della TM come una quintupla ordinata, i cui primi due simboli
sono quelli che noi abbiamo scorporato dal formato dell’istruzione (ridotto quindi a una
terna) per usarli come “indirizzo” dell’istruzione stessa. Altri autori propongono varianti
ancora diverse; nella moderna teoria della computabilità si usano poi TM configurate
con più di un nastro.
Turing inoltre non introduce esplicitamente il comando s* (stop) né fa uso della nostra
AC (Area di Controllo).
Nella concezione originaria, infine, si fa distinzione tra l’insieme dei simboli ausiliari (tra i
quali il “blank” della cella vuota) e quello dei simboli “significativi” (chiamati “figures”);
quest’ultimo insieme è composto dai soli caratteri “0” e “1” (fatto che peraltro non ha
alcuna attinenza con l’uso dell’aritmetica binaria: un intero non negativo n viene infatti
rappresentato sul nastro da una stringa di n+1 simboli “1” contigui, delimitata da almeno
una cella vuota a destra e a sinistra).
In ogni caso si tratta di varianti che non ledono la sostanza delle idee di Turing e che si è
ritenuto utile adottare a scopo didattico, anche per dare più immediato risalto alla stretta
analogia tra la TM e le logiche hardware / software dei computer “reali” a programma
registrato.
La seconda idea fondamentale, il cui sviluppo non esaminiamo in questa sede,
consiste nell’aver dimostrato che esiste un programma universale che opera su un
nastro su cui siano stati scritti (con una apposita codificazione) sia le istruzioni di un
programma particolare, del tipo visto nell’esempio, e sia i dati di input su cui tale
programma deve operare.
Il programma universale (che altro non è se non la Macchina Universale di Turing UTM) produce lo stesso output che sarebbe stato prodotto da quel programma
particolare applicato a quei dati di input. In simboli:
input per UTM
programma particolare P
& dati di input per P
UTM
output di UTM
output di (P applicato ai
dati di input per P)
L’obiettivo dell’articolo di Turing (esposto nel paragrafo finale) era peraltro di natura
esclusivamente logica: risolvere (negativamente) il problema dell’arresto (Halting
Problem) per le TM, che è strettamente analogo al problema della decisione
(l’entscheidungsproblem, proposto da Hilbert all’inizio del Novecento).
Sotto questo aspetto, Turing si muoveva sulla stessa linea di pensiero seguita da
Kurt Gödel per i suoi teoremi “negativi” pubblicati nel 1933 (incompletezza;
non-decidibilità).
APPENDICE
Soluzione proposta per la Macchina “+12”
s1
s2
Si assuma (AC) iniziale = s1
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
0,D,s1 1,S,s2
s1
s2
c* 1,S,s2 c*,D,s*
0
1,S,s2 0,S,s2
1
0,D,s1 1,S,s2
Domanda
In quale situazione
viene eseguita
l’istruzione evidenziata
in giallo?
Soluzioni proposte per la Macchina “RdS”
s1
s2
s3
s4
a
a,S,s2
a,S,s1
a,S,s1
a,F,s*
b
b,S,s1
b,S,s3
b,S,s4
b,S,s1
Si assuma (AC) iniziale = s1
c* c*,F,s* c*,F,s1 c*,F,s1 c*,F,s1
Si osservi che le istruzioni agli indirizzi c*,s2, c*,s3 e c*,s4 sono forse
“eleganti” ma certamente ridondanti; il seguente algoritmo risulta infatti
più efficiente
s1
s2
s3
s4
a
a,S,s2
a,S,s1
a,S,s1
a,F,s*
b
b,S,s1
b,S,s3
b,S,s4
b,S,s1
c* c*,F,s* c*,F, s* c*,F, s* c*,F, s*