Dipartimento di Informatica
Università di Pisa
Molti testi di informatica contengono una descrizione delle macchine di Turing, inserita di solito nel contesto della teoria della calcolabilità, della complessità o della teoria degli automi. Da un punto di vista didattico, le macchine di Turing non vengono di solito utilizzate come primo formalismo per introdurre la scienza dei calcolatori. Infatti se da un lato le macchine di Turing possono essere utilizzate per codificare tecniche sofisticate di programmazione (come ad esempio la definizione di un interprete), dall'altro lato risolvere problemi non banali con le macchine di Turing può essere difficile. Inoltre le teorie associate con le macchine di Turing introducono concetti non banali, come ad esempio le nozioni di decidibilità o semi-decidibilità nella teoria della calcolabilità.
Nonostante tutto questo, il comportamento delle macchine di Turing può essere spiegato in modo semplice a chi non possiede conoscenze di informatica. Abbiamo per questo deciso di preparare un'introduzione alla macchine di Turing che fosse breve ed al tempo stesso auto-contenuta.
Nel 1936 il matematico inglese Alan Turing propose l'idea di una macchina immaginaria che fosse capace di eseguire ogni tipo di calcolo su numeri e simboli.
Una macchina di Turing (MdT) è definita da un insieme di regole che definiscono il comportamento della macchina su un nastro di input-output (lettura e scrittura). Il nastro può essere immaginato come un nastro di carta di lunghezza infinita, diviso in quadratini dette celle. Ogni cella contiene un simbolo oppure è vuota. Una MdT ha una testina che si sposta lungo il nastro leggendo, scrivendo oppure cancellando simboli nelle celle del nastro. La macchina analizza il nastro, una cella alla volta, iniziando dalla cella che contiene il simbolo più a sinistra nel nastro.
Ad ogni passo, la macchina legge un simbolo sul nastro ed in accordo al suo stato interno:
Il comportamento di una MdT può essere programmato definendo un insieme di regole, o quadruple, del tipo:
(stato-corrente, simbolo-letto, nuovo-stato, simbolo-scritto/direzione).
Per esempio la quadrupla (0, A, 1, B) indica che se la macchina si trova nello stato interno 0 e legge sul nastro il simbolo A, allora passa nello stato interno 1 e scrive B sul nastro.
La quadrupla (1, B, 0, >) indica invece che se la macchina si trova nello stato interno 1 e legge sul nastro il simbolo B, allora passa nello stato interno 0 e si sposta di una posizione a destra (senza modificare il nastro).
Si noti che la scrittura del simbolo speciale ``-'' corrisponde a cancellare il contenuto di una cella. Ad esempio la quadrupla (1, A, 2, -) indica che se la macchina si trova nello stato 1 e legge il simbolo A, allora passa nello stato 2 e cancella il simbolo A dal nastro. Il simbolo ``-'' viene quindi utilizzato per rappresentare la cella vuota.
Si noti che una MdT può compiere un'azione anche quando incontra la cella vuota. Ad esempio la quadrupla (2, -, 2, <) indica che se la macchina si trova nello stato 2 e legge una cella vuota allora si sposta di una posizione a sinistra rimanendo nello stesso stato.
Si noti infine che un insieme di quadruple associa ad ogni coppia:
stato-corrente, simbolo-letto
al più una coppia:
nuovo-stato, simbolo-scritto/direzione.
Vediamo adesso come una MdT effettua i suoi calcoli. Inizialmente il nastro contiene una sequenza finita di simboli, detta sequenza di ingresso. La MdT è nel suo stato interno iniziale 0 con la testina posizionata sul simbolo più a sinistra nel nastro. A partire da questa configurazione iniziale, la MdT effettua una serie di azioni seguendo rigorosamente il suo insieme di regole. Se la macchina raggiunge uno stato interno per cui non esiste nessuna quadrupla per la coppia:
stato-corrente, simbolo-letto
allora la MdT si ferma e termina la sua computazione.
ESEMPIO 1. Consideriamo ad esempio una MdT che
modifica una sequenza di A e di B rimpiazzando ogni A
con una B e viceversa. Una tale MdT può essere definita
dal seguente insieme di regole:
| 0 | A | 1 | B |
| 0 | B | 1 | A |
| A | - | 2 | - |
| 1 | A | 0 | > |
| 1 | B | 0 | > |
La prima quadrupla stabilisce l'azione che la macchina deve eseguire quando si trova nello stato interno 0 e il simbolo in lettura è A. Ad esempio consideriamo la situazione iniziale in cui la sequenza di ingresso è AB:
La macchina si trova nello stato interno iniziale 0 ed il simbolo in lettura è A. (Graficamente rappresentiamo questa situazione indicando lo stato interno della macchina sopra la cella in lettura.)
La prima quadrupla stabilisce che la macchina deve cambiare il proprio stato interno in 1 e scrivere il simbolo B sul nastro, ottenendo:
Dopo aver effettuato la prima mossa, la macchina si trova nello stato 1 ed in simbolo in lettura è B. In questo caso la quinta regola stabilisce che la macchina torna nello stato 0 spostando la testina a destra di una cella, ottenendo così la nuova configurazione:
Secondo quanto stabilito dalla seconda e dalla quarta regola, la macchina effettua quindi le seguenti mosse:
A questo punto la terza regola stablisce che quando la macchina si trova nello stato 0 e la cella in lettura è vuota, allora la macchina passa nello stato 2 senza modificare il nastro nè spostare la testina:
A questo punto la macchina si trova nello stato 2 e la cella
in lettura è vuota. La macchina quindi si ferma, terminando la sua
computazione, dato che non ha nessuna quadrupla che associ un'azione alla
coppia (2, -). 
ESEMPIO 2. Si noti che una MdT può non terminare la sua computazione su certe sequenze di ingresso. Ad esempio la MdT definita dalle quadruple:
non si fermerà mai per qualunque sequenza di ingresso di A
e B, perchè continuerà a sostituire A con
B
e viceversa nella cella non vuota più a sinistra del nastro.
ESEMPIO 3. Dato un numero intero positivo n, 
è il numero se n è pari, se n è dispari.
Ad esempio, 
, mentre 
.
Consideriamo il problema di programmare una macchina di Turing che,
dato un nastro iniziale contenente una sequenza composta da n
consecutive (con n > 1), termina la sua esecuzione lasciando sul
nastro la sequenza composta da
consecutive. Ad esempio:
Una MdT che risolva il problema in esame può ad esempio adottare la seguente strategia:
| 0 | A | 1 | - |
| 1 | - | 2 | > |
| 2 | A | 3 | - |
| 3 | - | 4 | > |
| 4 | A | 4 | > |
| 4 | - | 5 | > |
| 5 | A | 5 | > |
| 5 | - | 6 | A |
| 6 | A | 6 | < |
| 6 | - | 7 | < |
| 7 | A | 8 | < |
| 8 | A | 8 | < |
| 8 | - | 0 | > |
Gli stati 0 e 1 sono utilizzati dalla macchina per cancellare la prima A dalla sequenza di ingresso, mentre gli stati 2 e 3 permettono di cancellare la seconda A della sequenza, se esiste. Si noti che se la sequenza contiene soltanto una A allora la macchina si ferma nello stato 2 sulla cella vuota. Lo stato 4 permette di scorrere la parte rimanente della sequenza di ingresso, ovvero fino a quando non si incontra la cella vuota. A questo punto la macchina utilizza lo stato 5 per andare a scivere una A a destra della sequenza ``di uscita''. Lo stato 6 serve quindi per ripercorre verso sinistra la sequenza di uscita, e lo stato 7 permette di controllare se la sequenza di ingresso contiene ancora qualche A. Se così è allora la macchina riporta la testina sul simbolo più a sinistra della sequenza di ingresso (stato 8) e riparte dallo stato 0, altrimenti la macchina si ferma nello stato 7.
Ad esempio per la sequenza di ingresso AAAA la MdT appena descritta esegue la seguente computazione:
La macchina si ferma quindi nello stato 7.
Esistono molti programmi ``simulatori'' di macchine di Turing, ovvero programmi capaci di simulare il comportamento di una macchina di Turing mostrandone il comportamento sullo schermo di un calcolatore.
I partecipanti alla gara di informatica per studenti delle scuole superiori utilizzano un simulatore di macchine di Turing di facile utilizzo anche per chi non ha dimestichezza con l'uso dei calcolatori.
Il simulatore è stato messo a punto presso il Dipartimento di Informatica dell'Università di Pisa estendendo il simulatore realizzato dalla ``Buena Vista University'' statunitense e cercando di semplificarne l'utilizzo.
Molto brevemente, questo simulatore mostra sullo schermo una macchina di Turing (raffigurata come una specie di macchina a vapore) che corre su un nastro. Il simulatore inoltre mostra: