MACCHINE DI TURING
Le macchine di Turing sono dispositivi astratti per la manipolazione
di simboli, ideati nel 1936 dal matematico e logico britannico Alan
Mathison Turing.
La loro descrizione si trova nel libro On the computable numbers
with an application to the Entscheidungsproblem del 1937, che ha
costituito il modello teorico del funzionamento di tutti i computer
successivi.
Sebbene il termine “macchine” faccia pensare a qualcosa di concreto,
e lo stesso Turing abbia poi messo in pratica le sue teorie
progettando - insieme a John von Neumann - il primo dispositivo
elettronico di calcolo, si deve tenere presente che le macchine di
Turing sono essenzialmente uno strumento concettuale per indagare
i limiti della computazione meccanica.
Lo studio delle loro proprietà astratte getta luce sui fondamenti
dell’informatica e sulla teoria della complessità.
Una macchina di Turing in grado di simulare tutte le altre è detta
“macchina di Turing universale”, o semplicemente “macchina”.
Una definizione di tipo più matematico, dotata anch’essa di una natura
“universale”, è stata introdotta dal matematico e logico americano
Alonzo Church, il cui lavoro sul lambda calculus si intrecciò con
quello di Turing, dando luogo a una teoria formale della
computazione nota come tesi Church-Turing.
Tale tesi stabilisce che le macchine di Turing catturano effettivamente
la nozione informale di metodo efficace in logica e matematica, e
forniscono una definizione rigorosa di “algoritmo” o “procedura
meccanica”.
La macchina di Turing è simile a una persona che esegua una
procedura ben definita, cambiando il contenuto di un nastro di carta
illimitato, suddiviso in quadrati che possono contenere un simbolo
appartenente a un insieme finito.
La persona deve ricordare uno “stato” appartenente anch’esso a un
insieme finito, e la procedura consiste in istruzioni di questo tipo:
“Se il tuo stato è 18 e il simbolo che vedi è 0, sostituisci il simbolo
con 1, cambia lo stato in 4 ed esamina il simbolo a destra”.
Quindi, una macchina di Turing consiste in:
1. un insieme finito di simboli detto alfabeto;
2. un nastro potenzialmente infinito nei due sensi e suddiviso in celle
discrete, ciascuna delle quali può contenere un simbolo
dell’alfabeto;
3. una testina mobile di lettura/scrittura;
4. una memoria capace di assumere un numero finito di stati diversi,
ciascuno dei quali corrisponde a una diversa configurazione della
macchina e determina l’esecuzione di attività diverse.
La macchina di Turing può compiere le seguenti operazioni elementari:
 scrivere o leggere un simbolo in una cella;
 variare il suo stato di memoria;
 spostare la testina a destra o a sinistra di una cella.
Attraverso queste operazioni la macchina può eseguire qualsiasi
operazione di tipo computistico di cui sia capace l’uomo.
L’attività di una macchina di Turing consiste interamente in passi
discreti e istantanei, ciascuno dei quali è determinato dalla sua
condizione iniziale; questa è costituita a sua volta dallo stato della
macchina e dal simbolo che in quell’istante occupa la cella del nastro
esaminata.
Data una certa condizione iniziale, la macchina riceve una istruzione
per il passo successivo, in cui sono indicati:
 il simbolo che la macchina deve lasciare nella cella esaminata;
 lo stato successivo della macchina;
 se la testina deve esaminare la cella a sinistra (S) o a destra (D) di
quella appena esaminata.
Ad es., un’istruzione del tipo
(1, II, D)
indica alla macchina di scrivere il simbolo 1 nell’attuale posizione
della testina, di assumere lo stato II e di spostare la testina
nella cella adiacente a destra.
Perciò le varie istruzioni che la macchina deve eseguire potrebbero
venire scritte in una tabella del tipo
È tuttavia più comodo descrivere una macchina di Turing tramite una
tabella a doppia entrata, come quella seguente, nella quale
l’istruzione da eseguire si può leggere semplicemente identificando la
condizione attuale della macchina, cioè la riga del suo stato e la
colonna del simbolo letto sul nastro.
Macchina sommatrice
Come esempio di macchina di Turing effettiva, consideriamone una
che sommi i numeri 2 e 3 e si fermi.
Supponiamo, per semplicità, che ciascun numero sia rappresentato in
notazione monadica o unaria, cioè come una “parola” costituita da
una successione di 1, delimitata a ciascuna estremità da uno 0.
Pertanto, dalla situazione iniziale del nastro nella quale sono indicati i
due addendi
dovremo giungere a una finale che presenti una successione di
cinque 1:
Ciò si otterrà cancellando lo 0 che separa le due parole nella
situazione iniziale, e facendo scorrere di una cella verso destra la
parola di sinistra, in modo che si unisca a quella di destra.
La macchina non può spostare una parola di 1 tutta in una volta,
dato che la testina si può spostare di un passo alla volta; perciò
dovrà eseguire delle istruzioni simili a quelle indicate in tabella.
Vediamone il funzionamento, supponendo che la macchina si trovi
inizialmente nello stato I con la testina sulla prima cella:
Verranno eseguite nell’ordine le seguenti istruzioni:
1a istruzione
(0, I, D)
Commento: L’istruzione lascia inalterato lo 0, lo stato I della
macchina e sposta la testina a destra; viene ripetuta finché si
incontra il primo 1.
2a istruzione
(0, II, D)
Commento: Il primo 1 viene trasformato in 0, la macchina viene
posta nello stato II e la testina si sposta a destra.
3a istruzione
(1, II, D)
Commento: Il secondo 1 rimane inalterato, la macchina rimane
nello stato II e la testina si sposta a destra
4a istruzione
(1, III, D)
Commento: Lo 0 successivo diventa 1, la macchina passa nello
stato III e la testina si sposta a destra
5a istruzione
Stop
Commento: La computazione ha termine
Naturalmente la macchina di Turing di questo esempio permette di
sommare due numeri qualsiasi, dato che la 3a istruzione viene
ripetuta fino a che non si trova la fine della prima parola, cioè lo 0
che separa i due addendi.
Macchina copiatrice
Sviluppiamo ora una macchina di Turing che permetta di copiare una
parola di 1 immediatamente a destra dello 0 che ne delimita il
termine.
Essa richiederà più istruzioni della macchina sommatrice, e potrà
essere usata a sua volta come parte di una macchina più complessa
che fornisca il prodotto di due numeri.
Non risulta conveniente risolvere il problema con una macchina che
conti gli 1 della parola da copiare, dato che essa dovrebbe
possedere tanti stati quanti sono gli 1, e ciò farebbe crescere
indefinitamente il numero degli stati.
Seguiremo invece una tecnica diversa, che illustriamo nel caso in cui
la parola da copiare sia 1 1, cioè costituita da due 1.
Ciò significa che dalla
dovremo giungere alla
La tecnica consiste nell’esaminare il nastro finché si trova il primo 1
della parola da copiare, e quindi nel ripetere i tre passi seguenti tante
volte quanti sono gli 1 della parola:
a) si cancella momentaneamente il primo 1;
b) si muove la testina fino allo 0 che delimita la parola e si
trasforma in 1 il primo 0 alla sua destra;
c) si riporta indietro la testina, riscrivendo l’1 nella cella in cui era
stato cancellato.
I tre passi precedenti sono realizzati dai blocchi di istruzioni indicate in
figura, insieme alla situazione del nastro che esse determinano.
A questo punto è stato copiato il primo 1 della parola e il
procedimento continua ripetendo i passi precedenti:
a’) si cancella momentaneamente il secondo 1;
b’) si muove la testina fino allo 0 che delimita la parola e si trasforma
in 1 il primo 0 alla sua destra;
c’) si riporta indietro la testina, riscrivendo l’1 nella cella in cui era
stato cancellato.
I tre passi precedenti sono realizzati dai blocchi di istruzioni indicate
in figura, insieme alla situazione del nastro che esse determinano.
L’elaborazione termina con le istruzioni
(1, VIII, S)
Stop
che riportano la testina alla posizione iniziale e arrestano l’elaborazione.
Le varie istruzioni che devono essere eseguite dalla macchina si
ricavano dalla tabella seguente.
Naturalmente anche ora la macchina è in grado di copiare una parola
di lunghezza qualsiasi.