La Macchina di Turing

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.

Che cosa è una macchina di Turing?

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:

• decide il suo prossimo stato interno, e
• scrive un simbolo sul nastro e decide se spostare o meno la testina a sinistra o a destra di una posizione.

Come per uno stato della mente di un essere umano, lo stato interno di una MdT definisce l’ambiente in cui una decisione viene presa. Una MdT può avere solo un numero finito di stati.

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.

Si noti infine che un insieme di quintuple associa ad ogni coppia:

stato-interno-corrente, simbolo-letto

prossimo-stato-interno, 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.

stato-interno-corrente, simbolo-letto

allora la MdT si ferma e termina la sua computazione.

Esempi

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

  AA

  AB

  AB

  0 A 1 A >
  1 A 0 A <

Dato un numero intero positivo $n$, n div 2 è il quoziente della divisione di $n$ per f2$. Ad esempio, 6 div 2 = 3, mentre 9 div 2 = 4.

Consideriamo il problema di programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza composta da $n$ A consecutive (con $n > 1$), termina la sua esecuzione lasciando sul nastro la sequenza composta da n div 2 A consecutive.

Ad esempio:

Nastro iniziale	Nastro finale
AAAA	AA
AAAAA	AA
AAA	A
AA	A

Una MdT che risolva il problema in esame può ad esempio adottare la seguente strategia:

1. scorre la sequenza di ingresso, partendo dalla A più a sinistra;
2. se la sequenza di ingresso contiene una sola A, la cancella e si ferma;
3. se invece la sequenza di ingresso contiene almeno due A, le cancella entrambe e va ad aggiungere una A alla sequenza “di uscita”, nella parte del nastro che si trova a destra della sequenza di ingresso. Quindi torna sulla cella più a sinistra di ciò che rimane della sequenza di ingresso e riparte da (1).

Una MdT che si comporti nel modo appena descritto può essere definita dal seguente insieme di quintuple:

  0 A 1 - >
  1 A 2 - >
  2 A 2 A >
  2 - 3 - >
  3 - 4 A <
  3 A 3 A >
  4 A 4 A <
  4 - 5 - <
  5 A 5 A <
  5 - 0 - >
  0 - F - -

Lo stato 0 è utilizzato dalla macchina per cancellare la prima A dalla sequenza di ingresso, mentre lo stato 1 permette 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 1 sulla cella vuota. Lo stato 2 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 3 per andare a scrivere una A a destra della sequenza “di uscita”. Lo stato 4 serve quindi per ripercorre verso sinistra la sequenza di uscita, e lo stato 5 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 F.

Ad esempio per la sequenza di ingresso AAAA la MdT appena descritta esegue la seguente computazione:

La macchina si ferma quindi nello stato F.

Funzioni avanzate

Il Simulatore usato negli anni precedenti includeva già una forma di abbreviazione sintattica, consistente nel specificare una sequenza di caratteri anziché un carattere singolo nei campi della quintupla che indicano il carattere letto da nastro e quello scritto su nastro. Tale abbreviazione veniva poi espansa in un numero di regole pari alla lunghezza della sequenza di caratteri, come nell’esempio seguente:

Regola con abbreviazione. ( stato1, ABCD, stato2, EFGH, > )

La versione 2006 del Simulatore generalizza questo meccanismo, introducendo i concetti di classe di simboli e di espansione parallela.

Classi di simboli

Una classe di simboli è una abbreviazione sintattica che denota una sequenza di simboli compresi nell’alfabeto della macchina (con lo spazio primo elemento dell’alfabeto):

!\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^-{|}

La denotazione è costituita da una coppia di parentesi quadre [] o graffe {}, contenenti uno o più simboli appartenenti alla sequenza, o il simbolo di intervallo (due volte punto) s1..s2, che indica tutti i simboli compresi fra s1 e s2 nell’alfabeto della macchina. Inoltre, se il primo carattere all’interno delle parentesi è un accento circonflesso ^ (in Inglese caret), si intende che la sequenza denotata è data dall’insieme complementare di quello indicato, ovvero comprende tutti i simboli non elencati all’interno delle parentesi. In questo caso, l’ordine della sequenza è quello naturale dell’alfabeto usato. Infine, il simbolo di barra inversa \ (in Inglese backslash) indica che il successivo carattere deve essere inteso letteralmente: per esempio, \] denota il simbolo ], non l’eventuale parentesi di chiusura di una sequenza; \- denota il simbolo - e non lo spazio, ecc. Allo stesso modo, \\ denota il simbolo \, che altrimenti non sarebbe esprimibile.

NOTA: se si specificano pida quelle con parentesi. Questo fatto è importante per quanto riguarda l’espansione parallela discussa in seguito. La classe di caratteri senza parentesi è stata mantenuta per compatibilità con l’estensione precedente della macchina, ed è limitata solo alle componenti della regola differenti da uno stato.

Gli esempi seguenti chiariscono la notazione usata per le classi di simboli:

Le classi di simboli possono essere usate nei seguenti contesti:

• per indicare uno stato iniziale o finale, nel qual caso può essere usato un prefisso e/o un postfisso che, unito a ciascuno dei simboli indicati dalla classe, genera il nome effettivo dello stato. Per esempio, lo stato indicato in maniera abbreviata con letto[0..9]r viene espanso nella sequenza di stati { letto0r, letto1r, letto2r, letto3r, letto4r, letto5r, letto6r, letto7r, letto8r, letto9r }.
• per indicare un simbolo letto o da scrivere, nel qual caso la classe fornisce direttamente la sequenza dei simboli indicati. Per esempio, [0..9] viene espanso nella lista di simboli { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } (analogamente a quanto possibile con la precedente notazione 0123456789, che comunque rimane disponibile).
• per indicare una direzione di movimento, nel qual caso la classe deve denotare una sequenza composta esclusivamente di simboli > e <. Per esempio, [>>><] viene espanso nella lista di direzioni { >, >, >, < }.

Espansione parallela

Abbiamo visto sopra che le classi di simboli possono essere delimitate da parentesi quadre [] o da parentesi graffe {}. In aggiunta, è possibile usare classi senza delimitatori, come per le vecchie sequenze del tipo 0123456789 (ora esprimibili anche con la sintassi abbreviata 0..9). Al momento dell’espansione di una regola abbreviata in un insieme di regole base, i tre diversi gruppi di classi di simboli vengono espansi parallelamente: tutte le classi delimitate con lo stesso tipo di parentesi vengono espanse, per ogni regola, nei simboli che occupano la stessa posizione nella sequenza; classi delimitate da parentesi diverse vengono invece espanse indipendentemente (e in combinazione fra loro).

Ciò consente di esprimere sinteticamente un grande numero di regole basate su prodotti cartesiani delle corrispondenti sequenze, come illustrato nei seguenti esempi:

Alcuni esempi

Mostriamo ora alcuni esempi di utilizzo dei nuovi costrutti. Per ciascun esempio, sono indicate il testo del problema che viene risolto, una versione della soluzione usando la sintassi tradizionale, una versione con la nuova sintassi, e l’espansione delle regole con la nuova sintassi.

Odometro. Scrivere un programma per macchina di Turing che, ricevuto sul nastro una stringa di cifre decimali, lasci sul nastro al termine dell’esecuzione la stringa di cifre corrispondente al numero iniziale, incrementato di uno. Se il risultato supera il numero di cifre inizialmente presenti, il programma deve lasciare sul nastro una stringa di soli 0 (comportamento simile a quello dei normali contachilometri).

Palindrome. Scrivere un programma per macchina di Turing che, ricevuta sul nastro una stringa sull’alfabeto a-z, lasci il nastro vuoto alla fine della computazione se e solo se la stringa originale era palindroma (si dicono palindrome le stringhe che si leggono identicamente da sinistra a destra o da destra verso sinistra, per esempio “ailatiditalia” o “satorrotas”).

Simulatore di macchine di Turing

Disponibile su turingsimulator.net.