Macchine di Turing deterministiche

Una macchina di Turing è sostanzialmente un automa a stati finiti arricchito di una memoria esterna che — a differenza della memoria dei PDA — ha una politica di accesso estremamente liberale (equivalente all’accesso casuale). Più nel dettaglio, una macchina di Turing può essere vista come un controllo a stati finiti che comanda una testina di lettura e scrittura, la quale scorre su un nastro bi-infinito (infinito sia verso sinistra che verso destra). Tale nastro è diviso in celle, ciascuna delle quali contiene un simbolo, e il simbolo presente sotto alla testina contribuisce a determinare le mosse della macchina, insieme allo stato interno del controllo a stati finiti.

Formalmente, una macchina di Turing (MdT) deterministica è una settupla

$$ M = \lang Q, \Sigma, \Gamma, \delta, q_0, B, F\rang $$

in cui:

• $Q$ è l’insieme finito e non vuoto degli stati
• $\Sigma$ è l’alfabeto di input
• $\Gamma$ è l’alfabeto di lavoro, l’insieme dei simboli che possono comparire nel nastro che deve includere propriamente l’alfabeto di input, $\Sigma \subset \Gamma$ (perchè l’input verrà dato alla macchina scrivendolo sul nastro)
• $q_0\in Q$ è lo stato iniziale della macchina
• $B\in \Gamma \setminus \Sigma$ è il simbolo blank, un simbolo appartenente all’alfabeto di lavoro ma non a quello di input (ragion per cui si ha $\Sigma \subset \Gamma$ e non $\Sigma \subseteq \Gamma$) che verrà messo nelle celle del nastro in cui non sono presenti simboli significativi (le celle “vuote”)
• $F\subseteq Q$ è l’insieme degli stati finali (o accettanti)
• $\delta$ è la funzione di transizione, che:
  • è definita su un sottoinsieme di $Q \times \Gamma$, ovvero è una funzione parziale (questo semplifica la descrizione delle macchine)
  • laddove è definita, associa a un elemento di $Q\times \Gamma$ un elemento di $Q\times \Gamma \times \{L, R\}$.

Per semplificare il modello, si assume che la funzione di transizione sia indefinita sugli stati accettanti. Come si vedrà dopo, ciò farà sì che la computazione della macchina si arresti quando questa arriva in uno stato finale.

Interpretazione della funzione di transizione

La funzione di transizione $\delta$ determina l’evoluzione della macchina in base allo stato interno attuale $q\in Q$ e al simbolo $X \in \Gamma$ letto dalla testina (quello presente nela cella del nastro attualmente visitata dalla testina):

• Se $\delta(q, X)$ è indefinita, allora, la macchina è bloccata, cioè la computazione della macchina si arresta.
• Se invece $\delta(q, X)$ è definita, e in particolare $\delta(q, X)=(p, Y, D)$, allora la macchina esegue la seguente mossa:
  • passa dallo stato interno $q$ a $p$ (si osservi che può essere $p = q$, dunque lo stato può non cambiare)
  • scrive il simbolo $Y$ nella cella attualmente visitata, al posto di $X$ (ma può essere $Y=X$)
  • sposta la testina a sinistra se $D = L$, o a destra se $D = R$ (in questa formalizzazione, la testina non può restare ferma).

Osservazione: Esistono tante diverse varianti delle macchine di Turing, che non comportano un cambiamento nella classe di linguaggi riconosciuti. Ad esempio, ci sono formalizzazioni in cui la testina può rimanere ferma, o può spostarsi di più di una posizione alla volta, o ancora ci possono essere più nastri di lavoro, ecc.

Esempio di descrizione