Problema di appartenenza al linguaggio di una MdT

Sulle macchine di Turing può essere definito il seguente problema di decisione LM:

Parametri: Una macchina di Turing $M = \lang Q, \{0, 1\}, \Gamma,\delta, q_1, B, F\rang$ e un suo input $w\in \{0, 1\}^*$ (per semplicità, si considerano solo le MdT con alfabeto di input binario, che sono equivalenti alle MdT con arbitrari alfabeti di input).

Domanda: $M$ accetta $w$?

Per studiare lo status computazionale di questo problema bisogna, come al solito, associare a esso un linguaggio e determinare se esista una MdT che lo riconosca. Si osservi che ciò introduce una sorta di “cortocircuito”: si vogliono usare le macchine di Turing per risolvere un problema che riguarda le macchine di Turing stesse.

Nel seguito si dimostrerà che il problema LM è ricorsivamente enumerabile ma indecidibile. Per fare ciò, bisognerà prima definire con precisione il linguaggio associato,

$$ L(\text{LM}) = \{x \in \Sigma^* \ | \ x \text{ è la codifica di una coppia }(M, w) \text{ per cui }M \text{ accetta }w\} $$

che necessita di due codifiche:

• una codifica su $\Sigma = \{0, 1\}$ delle MdT, $\#_{\text{MdT}}(M)$
• una codifica delle coppie di stringhe $(\#_{\text{MdT}}(M), w)$

Codifica delle macchine di Turing

Per semplicità, nel definire una codifica per le MdT $M = \lang Q, \{0, 1\}, \Gamma, \delta, q_1, B, F\rang$ si considerano solo le $M$ fatte in questo modo:

• l’insieme degli stati è $Q = \{q_1, q_2, ..., q_r\}$ (per un qualche $r$)
• lo stato iniziale è $q_1$
• c’è un unico stato finale, $F = \{q_2\}$
• l’insieme dei simboli di nastro è $\Gamma = \{X_1, X_2, X_3, ..., X_s\}$ (per un qualche $s$), dove $X_1 = 0, X_2 = 1$ e $X_3 = B$

Si potrebbe dimostrare che tali restrizioni, compreso in particolare il fatto di avere un singolo stato finale, non sono limitative, cioè che queste MdT sono equivalenti a quelle generali.

Una volta fissata la forma della macchina $M$, si assegnano degli interi positivi alle sue varie componenti:

• ogni stato $q_i$ è indicato dall’intero $i$
• ciascun simbolo di nastro $X_k$ è indicato dall’intero $k$
• 1 indica un movimento della testina a sinistra, $D_i = L,$ e 2 indica un movimento a destra, $D_2 = R$.

Così, una regola di transizione