6. Le macchine di Turing

A differenza degli automi una macchina di Turing elabora attraverso un nastro sul quale legge e scrive dati, con una memoria illimitata e senza restrizioni. La macchina per leggere e scrivere i dati sul nastro utilizza una testina e continuerà ad effettuare delle operazioni fino a quando non decide di produrre un output. Prima di dare una definizione formale di una macchina di Turing, elenchiamo le principali differenze tra questa e gli automi finiti:

• Una Macchina di Turing può sia scrivere che leggere sul nastro
• La testina di lettura-scrittura può muoversi sia verso sinistra che verso destra
• Il nastro è infinito
• Gli stati speciali di accettazione e rifiuto hanno effetto immediato

Definizione formale di una macchina di Turing

Una macchina di Turing è una 7-tupla, $(Q,\sum,\Gamma,\delta,q_0,q_{accept},q_{reject}$ dove

• Q è l'insieme degli stati
• $\sum$ è l'alfabeto di input non contenente il simbolo blank $\sqcup$
• $\Gamma$ rappresenta l'alfabeto del nastro con $\sqcup \in \Gamma$ e $\sum \subseteq \Gamma$
• $\delta : Q \times \Gamma \longrightarrow Q \times \Gamma \times${L,R}
• $q_0 \in Q$ è lo stato iniziale
• $q_{accept} \in Q$ è lo stato di accettazione
• $q_{reject} \in Q$ è lo stato di rifiuto, con $q_{reject} \ne q_{accept}$

Una macchina di Turing quando riceve in input la stringa w = $w_1w_2\dots w_n \in \sum *$ sulle n celle più a sinistra del suo nastro, mentre il restante è vuoto. La testina viene posizionata nella parte più a sinistra del nastro e quando inizia la sua computazione, la testina segue le regole descritte nella funzione di transizione. Se M tenta di spostare la testina a sinistra quando si trova all'estremità sinistra del nastro, allora la testina rimane nello stesso posto per quella mossa. La computazione prosegue fino a quando la macchina raggiunge lo stato di accettazione oppure di rifiuto, a quel punto si ferma.

Durante la computazione di una macchina di Turing si verificano cambiamenti dello stato corrente, del contenuto del nastro e della posizione della testina. Queste impostazioni prendono il nome di configurazione, rappresentate in determinati modi. Nel gergo tecnico si dice che una configurazione $C_1$ produce la configurazione $C_2$ se la macchina di Turing può passare dalla prima alla seconda in un unico passo. Formalmente supponiamo di avere a, b e c in $\Gamma$, così come u e v in $\Gamma$* e gli stati $q_i$ e $q_j$. In questo caso $ua q_i bv$ e $u q_j acv$ sono due configurazioni, e diciamo che la prima produce la seconda se nella funzione di transizione $\delta (q_i,b) = (q_j,c,L)$.

La configurazione iniziale di M consiste nella testina posizionata nel lato più a sinistra del nastro e nello stato iniziale $q_0$, formalmente possiamo scriverla come $q_0 w$. Mentre quando la macchina si trova nella sua configurazione di accettazione, lo stato della configurazione si riferisce allo stato $q_{accept}$. Infine si ha la configurazione di rifiuto, rappresentata dallo stato di rifiuto$q_{reject}$. L'insieme di stringhe che M accetta rappresenta il linguaggio di M, denotato conL(M).

Diamo adesso la definizione di linguaggio Turing riconoscibile e di linguaggio Turing decidibile.

Definizione formale di un linguaggio Turing-riconoscibile

Un linguaggio si dice Turing-riconoscibile se esiste una macchina di Turing che lo riconosce.

Definizione formale di un linguaggio Turing-dedicibile

Un linguaggio si dice Turing-dedicibile se esiste una macchina di Turing che lo decide.

Esistono diverse varianti della macchina di Turing, una di queste è la macchina di Turing multinastro la quale ha due o più nastri ognuno dei quali ha una propria testina. La funzione di transizione di questa particolare macchina è definita come $\delta : Q \times \Gamma^k \longrightarrow Q \times \Gamma^k \times$ { L,R,S $\}^k$ dove k è il numero di nastri. Inoltre per ogni macchina di Turing multinastro esiste una macchina di Turing a nastro singolo equivalente.

Un altro tipo di macchina di Turing consiste nella macchina di Turing non deterministica, la quale in qualsiasi punto della computazione può procedere effettuando diverse scelte. La funzione di transizione di questo tipo di macchina è la seguente: $\delta : Q \times \Gamma \longrightarrow P ( Q \times \Gamma \times \{ L,R \} )$. La computazione di una macchina di Turing non deterministica è un albero i cui rami corrispondono alle diverse scelte possibili previste per la macchina. Se qualche ramo della computazione porta allo stato di accettazione, allora la macchina accetta l'input. Inoltre per ogni macchina di Turing non deterministica esiste una macchina di Turing deterministica equivalente.