Cenni sulla
Macchina di Turing
c.bonfanti - 2007
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
(TM: Turing Machine)
Stazione di
lettura/scrittura
(CC)
Casella
Nastro
Nastro: è suddiviso in caselle e lo si suppone illimitato (ovvero prolungabile a
piacere tanto a destra quanto a sinistra.
Ogni casella contiene un solo carattere tra quelli ammessi, compresi
nell’alfabeto C = {c*,c1,c2, … cn}.
C è definito in relazione al compito che la macchina deve assolvere ma
contiene comunque il carattere c* che si conviene rappresenti il contenuto della
casella vuota.
Il nastro, dietro apposito comando, può scorrere da una casella a una delle due
adiacenti.
Stazione di lettura/scrittura: finestra che individua una casella del nastro
detta casella corrente e denominata CC.
La notazione (CC) significa: contenuto di CC.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
(TM: Turing Machine)
Area di
Controllo
Stazione di
lettura/scrittura
(CC)
(AC)
Casella
Nastro
Controllo: una zona (p.e. un rettangolo disegnato su un foglio di carta)
denominata AC (Area di Controllo), destinata a contenere uno dei simboli
dell’insieme S = {s1,s2, … sk}, detti convenzionalmente stati della TM.
La notazione (AC) significa: contenuto di AC.
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
(TM: Turing Machine)
Area di
Controllo
Stazione di
lettura/scrittura
(CC)
(AC)
Casella
Alfabeto dei caratteri
C = {c*,c1,c2, … cn}
Stati
S = {s1,s2, … sk}
S* = {s*,s1,s2, … sk}
Movimenti
M = {de,si,fe}
Insiemi dei simboli
Nastro
ELEMENTI COSTITUTIVI DI UNA MACCHINA DI TURING
(TM: Turing Machine)
Area di
Controllo
Stazione di
lettura/scrittura
(AC)
(CC)
Casella
Nastro
Programma
Alfabeto dei caratteri
C = {c*,c1,c2, … cn}
s1
s2
s3
...
sk
c*
Stati
S = {s1,s2, … sk}
S* = {s*,s1,s2, … sk}
c1
c2
c,m,s
...
Movimenti
M = {de,si,fe}
cn
Istruzione
(c  C; m  M; s  S*)
Programma: tabella a doppia entrata (matrice) in cui
- Le colonne sono intestate con tutti i simboli di stato compresi in
S = {s1,s2, … sk}; il numero degli stati dipende dal compito che la
macchina deve assolvere. Lo speciale stato designato come s* (stop)
non figura come intestazione di colonna.
- Le righe sono intestate con tutti i caratteri dell’alfabeto C = {c*,c1,c2, …
cn}.
Istruzioni: sono gli elementi della tabella, costituiti da una terna ordinata
di simboli c,m,s in cui:
c è un carattere dell’alfabeto C;
m è il comando di movimento che può assumere uno dei valori in
M = {de,si,fe} che stanno per destra, sinistra, fermo;
s è uno degli stati presenti in S*, incluso quindi lo stop s*.
Le coordinate ci e sj dell’elemento della tabella si chiamano indirizzo
dell’istruzione in esso contenuta.
Funzionamento
della TM
AC
c3
c2
c2
c3
c2
L’istruzione da eseguire (istruzione corrente) è quella
che sta scritta all’indirizzo c2 = (CC) e s2 = (AC) e
l’esecuzione consta di tre passi:
c1
s1
s2
s2
c*
c1
c2
...
c1,si, s5
...
Funzionamento
della 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 c2 = (CC) e s2 = (AC) e
l’esecuzione consta di tre passi:
1 - Si trascrive c1 (primo simbolo dell’istruzione
corrente) in CC.
s1
s2
c*
c1
c2
...
c1,si, s5
...
AC
Funzionamento
della TM
passo 1
c3
c2
c2
c3
c2
c1
s2
c3
c2
c1
c3
c2
c1
s2
c2
c1
c3
c2
passo 2
c3
c1
L’istruzione da eseguire (istruzione corrente) è quella
che sta scritta all’indirizzo c2 = (CC) e s2 = (AC) e
l’esecuzione consta di tre passi:
1 - Si trascrive c1 (primo simbolo dell’istruzione
corrente) in CC.
2 - Si sposta il nastro di una casella verso sinistra,
come indicato dal secondo simbolo dell’istruzione
corrente.
s1
s2
s2
c*
c1
c2
...
c1,si, s5
...
AC
Funzionamento
della TM
passo 1
c3
c2
c2
c3
c2
c1
s2
c3
c2
c1
c3
c2
c1
s2
c2
c1
c3
c2
passo 2
passo 3
c3
c1
L’istruzione da eseguire (istruzione corrente) è quella
che sta scritta all’indirizzo c2 = (CC) e s2 = (AC) e
l’esecuzione consta di tre passi:
1 - Si trascrive c1 (primo simbolo dell’istruzione
corrente) in CC.
2 - Si sposta il nastro di una casella verso sinistra,
come indicato dal secondo simbolo dell’istruzione
corrente.
3 - Se il terzo simbolo dell’istruzione corrente è s*
allora la macchina si arresta, altrimenti si trascrive s5
in AC.
s1
s5
s2
c*
c1
c2
...
c1,si, s5
...
AC
Funzionamento
della TM
passo 1
c3
c2
c2
c3
c2
c1
s2
c3
c2
c1
c3
c2
c1
s2
c2
c1
c3
c2
passo 2
passo 3
c3
c1
L’istruzione da eseguire (istruzione corrente) è quella
che sta scritta all’indirizzo c2 = (CC) e s2 = (AC) e
l’esecuzione consta di tre passi:
1 - Si trascrive c1 (primo simbolo dell’istruzione
corrente) in CC.
2 - Si sposta il nastro di una casella verso sinistra,
come indicato dal secondo simbolo dell’istruzione
corrente.
3 - Si trascrive s5 (terzo simbolo dell’istruzione
corrente) in AC. Se il terzo simbolo fosse stato s*,
allora la macchina si sarebbe arrestata.
Si ripete il ciclo: la prossima istruzione è perciò quella
all’indirizzo (CC),(AC) ovvero c3,s5.
s1
s5
s2
c*
c1
c2
...
c1,si, s5
...
ESEMPIO: La Macchina “+ 1”
Adottiamo l’alfabeto
C = {c*,0,1,2,3,4,5,6,7,8,9}
e programmiamo la MT in modo che essa
fornisca in output x+1, essendo x  0 il
numero intero scritto inizialmente sul nastro
e delimitato da almeno una casella vuota a
destra e a sinistra (input); il tutto nella
normale notazione decimale, con partenza
e arresto sulla casella che contiene le
unità.
Il programma qui a fianco, dove S = {s1, s2},
risolve il problema per qualsiasi valore di x,
ponendo inizialmente (AC) = s1.
Si veda qui appresso lo sviluppo completo
del caso in cui x = 299.
Questo esempio è tratto, con adattamenti del docente, da:
M.Italiani, G.Serazzi Elementi di informatica; Etas Kompass,
1973, pp.115-117.
s1
s2
c*
1,fe,s2
c*,de,s*
0
1,fe,s2
0,si,s2
1
2,fe,s2
1,si,s2
2
3,fe,s2
2,si,s2
3
4,fe,s2
3,si,s2
4
5,fe,s2
4,si,s2
5
6,fe,s2
5,si,s2
6
7,fe,s2
6,si,s2
7
8,fe,s2
7,si,s2
8
9,fe,s2
8,si,s2
9
0,de,s1
9,si,s2
indirizzo
(CC),(AC)
CC
istruzione
2
9,s1
9
9
AC
inizio
s1
indirizzo
(CC),(AC)
CC
istruzione
2
9,s1
0,de,s1
9
9
AC
inizio
s1
indirizzo
(CC),(AC)
CC
istruzione
2
9,s1
9
9
2
9
AC
inizio
s1
0,de,s1
0
s1
indirizzo
(CC),(AC)
CC
istruzione
2
9,s1
9,s1
9
9
2
9
AC
inizio
s1
0,de,s1
0
s1
indirizzo
(CC),(AC)
CC
istruzione
2
9,s1
9,s1
2,s1
3,s2
s1
9
2
9
0
2
0
0
s1
3
0
0
s2
0
0
0,de,s1
s1
0,de,s1
3,fe,s2
3,si,s2
s2
0,si,s2
3
c*,s2
inizio
9
3
0,s2
AC
0
0
3
0
s2
c*,de,s*
0
fine
s2
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.
In tal modo, Turing ha fornito per la prima volta una definizione soddisfacente del
concetto di algoritmo.
Si noti che la descrizione della MT che abbiamo dato nelle slide precedenti (come pure
la macchina “+1” usata quale 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 alcuni errori formali che
gli erano stati segnalati da P. Bernays (nota apparsa 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 MT come una quintupla ordinata[2] 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.
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, che equivale grosso modo al nostro alfabeto C, è composto dai
soli caratteri 0 e 1, fatto che peraltro non ha alcuna attinenza con l’uso dell’aritmetica
binaria.
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 MT e le logiche hardware / software del computer a programma
registrato.
[2]
Alcuni autori riducono la quintupla a una quadrupla in virtù del fatto che Turing raggruppa i comandi di scrittura
e di spostamento (terzo e quarto simbolo) sotto l’unica denominazione di “operations”.
Macchina Universale di Turing (UTM)
input per UTM
output di UTM
programma particolare P
& dati di input per P
output di (P applicato ai
dati di input per P)
UTM
La UTM stabilisce il paradigma concettuale del calcolatore a programma
registrato; concetto che sarà ripreso da von Neumann nella sua “architettura”
e quindi implementato sotto forma di “macchina fisica”.
La seconda idea fondamentale, 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[3]) produce lo stesso output che sarebbe stato prodotto da quel programma
particolare applicato a quei dati di input.
L’obiettivo dell’articolo di Turing (esposto nel paragrafo finale) era peraltro di natura
esclusivamente logica: risolvere il problema della decisione (l’entscheidungsproblem,
proposto da Hilbert) con un teorema analogo ai teoremi “negativi” che Kurt Gödel aveva
pubblicato nel 1933 (incompletezza; non-decidibilità).
Turing infatti definì e risolse negativamente il problema che chiamò problema
dell’arresto (halting problem) che è sostanzialmente isomorfo al problema di Hilbert e
alla non-decidibilità di Gödel.
[3]
La UTM è descritta nei paragrafi 6 e 7 dell’articolo citato.