Configurazioni

Durante la computazione di una MdT si verificano cambiamenti di 3 tipi:

1. stato
2. contenuto del nastro
3. posizione della testina

Una configurazione è una descrizione concisa di questi tre elementi in un dato insieme della computazione

Fornisce una “fotografia” della Macchina di Turing in quel dato istante

Data una MdT $(Q, \sum, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, uno stato $q \in Q$ e $u,v \in \Gamma^*$, la configurazione $uqv$ descrive la seguente situazione:

• lo stato corrente della macchina è $q$
• il contenuto del nastro (da sinistra a destra) è $uv$
• la testina si trova sul primo (più a sinistra) simbolo di $v$ (su primo blank $\sqcup$ se $v = \epsilon$)
• dopo $v$ ci sono solo $\sqcup$

La configurazione cambia ad ogni passo della computazione: si dice che $C_1$ produce $C_2$ (indicato con $(C_1 \to C_2)$) se la MdT può andare da $C_1$ a $C_2$ in un singolo passo

Casi particolari

Siano $a,b, c \in \Gamma$, $i , v \in \Gamma^*$, $q_i, q_j \in Q$

• testina all’inizio del nastro: $q_i bv$

  se $\delta(q_i, b) = (q_j, c, L)$ allora $q_i bv \to q_j cv$

• testina all’estremità destra dell’input: $uaq_i$

  $uaq_i$ equivalente a $uaq_i \sqcup$

• configurazione iniziale su input $w$: $q_0w$, dove $q_0$ è lo stato iniziale

• configurazione di accettazione: raggiunge lo stato $q_{accept}$

• configurazione di rifiuto: raggiunge lo stato $q_{reject}$