Corollario

Esistono linguaggi che non sono Turing riconoscibili

Macchina di Turing universale

Una MdT universale $U$ simula la computazione di una qualsiasi MdT $M$

$U$ riceve in input una rappresentazione $\langle M, w\rangle$ di $M$ e di un possibile input $w$ di $M$

$\langle M, w \rangle \to \text{ Macchina Universale } U \to \begin{cases} \text{accetta } \space \text{ se } M \text{ accetta } w \\ \text{rifiuta} \space \text{ se } M \text{ rifiuta } w \end{cases}$

Teorema

Il linguaggio $A_{TM}= \{ \langle M,w \rangle | M \text{ è una MdT che accetta la parola } w\}$ è Turing riconoscibile

• Dimostrazione

Simulazione di MdT input

Simulare una MdT con un’altra MdT

1. marca stato iniziale di $M$ (stato corrente) e primo simbolo su nastro (posizione corrente testina)
2. cerca prossima transizione (nella parte che descrive la funzione di transizione), sia $(q,x) \to (q',x',D)$
3. esegui la transizione
4. aggiorna lo stato corrente (marca $q'$) e la posizione corrente della testina (marca simbolo a $D$)
5. se lo stato corrente risulta $q_{accept}/q_{reject}$ decidi di conseguenza, altrimenti ripeti da 2

Note

1. $U$ è detta MdT universale
2. $U$ riconosce $A_{TM}$: accetta ogni coppia $\langle M, w \rangle \in A_{TM}$
3. $U$ cicla su $\langle M, w\rangle$ se e solo se $M$ cicla su $w$, quindi $U$ non decide $A_{TM}$