Funzionamento

Che cosa è una macchina di Turing?

jvn1.jpg

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 e in accordo al suo stato interno corrente:

1.decide il suo prossimo stato interno, e

2.scrive un simbolo sul nastro e decide se spostare o meno la testina a sinistra o a destra di una posizione.

Una MdT può avere solo un numero finito di stati.

Funzionamento

Il comportamento di una MdT può essere programmato definendo un insieme di regole, o quintuple, del tipo:

(stato-interno-corrente, simbolo-letto, prossimo-stato-interno, simbolo-scritto, direzione).

Per esempio la quintupla (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, scrive B sul nastro e non sposta la testina di lettura.
La quintupla (1, B, 0, A, >) 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, scrive A sul nastro e si sposta di una posizione a destra. Se ci si vuole spostare senza modificare il contenuto del nastro si può scrivere il simbolo appena letto utilizzando una quintupla analoga alla seguente: (1, B, 0, B, >).
Si noti che la scrittura del simbolo speciale "-" corrisponde a cancellare il contenuto di una cella. Ad esempio la quintupla (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 non spostando la testina di lettura. Il simbolo "-" viene quindi utilizzato sia per rappresentare la cella vuota che per denotare il mancato movimento della testina.
Una MdT cambia stato quando un’operazione viene svolta una sola volta, mentre resta nello stesso stato quando l’operazione si ripete più volte.
Una MdT può compiere un'azione anche quando incontra la cella vuota. Ad esempio la quintupla (2, -, 2, -, <) indica che se la macchina si trova nello stato 2 e legge una cella vuota allora lascia invariato il contenuto della cella e si sposta di una posizione a sinistra rimanendo nello stesso stato.
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 quintupla per la coppia:

stato-interno-corrente, simbolo-letto

allora la MdT si ferma.

ESEMPIO. Consideriamo ad esempio una MdT che modifica una sequenza di A rimpiazzando ogni A in posizione dispari con una B (la prima A ha posizione pari uguale a 0). Una tale MdT può essere definita dal seguente insieme di regole:

0 A 1 A >
1 A 0 B >
0 - FINE - -
1 - FINE - -

La prima quintupla stabilisce l'azione che la macchina deve eseguire quando si trova nello stato interno 0 e il simbolo in lettura è A. Tale situazione corrisponde ad una A in posizione pari.
Ad esempio consideriamo la situazione iniziale in cui la sequenza di ingresso è AA:

mimage001.gif

La macchina si trova nello stato interno iniziale 0 ed il simbolo in lettura è A.
La prima quintupla stabilisce che la macchina deve cambiare il proprio stato interno in 1, scrivere il simbolo A sul nastro e spostarsi di una casella verso destra. Tale situazione corrisponde ad una A in posizione dispari, ottenendo:

mimage002.gif

Dopo aver effettuato la prima mossa, la macchina si trova nello stato 1 ed il simbolo in lettura è B. In questo caso la seconda regola stabilisce che la macchina torna nello stato 0, scrivendo il simbolo A spostando la testina a destra di una cella, ottenendo così la nuova configurazione:

mimage003.gif

Secondo quanto stabilito dalla terza regola, la macchina trova la casella bianca e si muove nello stato etichettato come FINE:

mimage004.gif

A questo punto la macchina si trova nello stato FINE e la cella in lettura è vuota. La macchina quindi si ferma, terminando la sua computazione.

Salvo diversa indicazione, il contenuto di questa pagina è sotto licenza Creative Commons Attribution-ShareAlike 3.0 License