Ieri sono riuscito ad introdurre la Macchina di Turing Universale, ma non ho finito di caratterizzarla completamente. Sappiamo che esiste per il teorema dell’enunciazione, ma abbiamo bisogno di codificare le MdT in modo da poterle rappresentare su un nastro della MdT universale, insieme alla stringa di input.

Riprendiamo con la definizione di una codifica di una macchina di Turing M e rivediamo alcune definzioni:

$$ k:Q_\star \cup \{h\} \cup \Sigma_\star \cup \{L,R,-\} \mapsto \{|\}^\star $$
$$ \begin{align} h &\mapsto \> | \\ q_i &\mapsto \> |^{i+2} \\ L &\mapsto \> | \\ R &\mapsto || \\ - &\mapsto ||| \\ \sigma_i &\mapsto \> |^{i+4} \end{align} $$
$$ \begin{align} &S_{q,p} = c\>κ(q_{ip})\>c\>κ(q)\>c\>κ(σ)\>c\>κ(D)\>c &\text{ se } δ(q_{ip}, σ_{jq}) = (q,σ,D) \\ &S_{q,p} = c\>κ(q_{ip})\>c\>κ(σ_{jq})\>c\>d\>c\>d\>c\>d\>c &\text{ se } δ(q_{ip}, σ_{jq}) \text{ non è definita} \end{align} $$

Rimettiamo insieme tutti i pezzi per ottenere la funzione di codifica ρ:

$$ \rho(M) = c\>\kappa(s)\>c\>S_{1,1}S_{1,2}...S_{1,l}S_{2,1}...S_{k,1}S_{k,2}...S_{k,l}\>c $$

Esempio: vogliamo codificare una MdT \(M = (\{q_0\}, \{σ_1,σ_3,σ_5\}, δ, h)\) , dove

$$ \begin{align} &δ(q_0, σ_1) &= (h, σ_5, -) &\mapsto S_{1,1} \\ &δ(q_0, σ_3) &= (q_0, σ_1, R) &\mapsto S_{1,2} \\ &δ(q_0, σ_5) &= \text{ non definito} &\mapsto S_{1,3} \end{align} $$

Siccome \(k=1,i_1=0, l=3 \; (j_1=1, j_2=3, j3 = 5)\) allora:

$$ \begin{align} &S_{1,1} = c \> |^2 \> c \> |^5 \> c \> | \> c \> |^9 \> c \> |^3 \> c\\ &S_{1,2} = c \> |^2 \> c \> |^7 \> c \> |^4 \> c \> |^5 \> c \> |^2 \> c \\ &S_{1,3} = c \> |^2 \> c \> |^9 \> c \> d \> c \> d \> c \> d \> c \end{align} $$

Diamo tutto in pasto a ρ:

$$ \rho(M) = c\>|^2\>c\>c\>|^2 \> c \> |^5 \> c \> | \> c \> |^9 \> c \> |^3 \> c\> c \> |^2 \> c \> |^7 \> c \> |^4 \> c \> |^5 \> c \> |^2 \> c \>c \> |^2 \> c \> |^9 \> c \> d \> c \> d \> c \> d \> c\>c $$

La codifica che ci restituisce ρ non è sufficiente perché manca ancora la codifica del dato iniziale \(w = \sigma'_0...\sigma'_n\) . A questo ci pensa la funzione τ:

$$ \tau(\sigma'_0...\sigma'_n) = c \> \kappa(\sigma'_0) \> c \> \kappa(\sigma'_1) \> c ... \kappa(\sigma'_n) \> c $$

Quindi una codifica completa di M sarà data da:

$$ \rho(M)\tau(w) $$

La MdT universale \(U=(Q_U,\Sigma_U,\delta_U,h_U)\) dovrebbe essere in grado di eseguire ogni \(M=(Q,Σ,δ,h)\) applicata ad ogni \(w \in \Sigma^\star\) , cioè:

  1. se \((s,\underline{▷}w) \rightarrow_M^\star (h,u\underline{a}v) \Rightarrow (s_U, ▷\rho(M)\tau(w)) \rightarrow_U^\star (h, \tau(uav) \underline{\#})\) . Il che significa che se M si ferma su w con risultato uav, allora U si ferma su \(\rho(M)\tau(w)\) .
  2. se \((s_U, \underline{▷}\rho(M)\tau(w)) \rightarrow_U^\star (h, u'\underline{a'}v') \Rightarrow a'=\#, v' = \epsilon, u' = \tau(uav)\) per qualche u, a e v tali che \((s,\underline{▷}w) \rightarrow_M^\star (h, u\underline{a} v)\) . Il contario del punto 1: se U si ferma su w con risultato \(\epsilon\underline{\#}\tau(uav)\) , allora M si ferma su uav.

Una volta che la macchina U riceve in input la codifica \(\rho(M)\tau(w)\) esegue una fase di inizializzazione. Alla fine la macchina si trova in questo stato:

  1. Nel primo nastro di U resta solo la codifica di \(\tau(w)\) (nastro dei dati di input).
  2. Nel secondo nastro di U resta solo la codifica \(\rho(M)\) (nastro del programma da eseguire).
  3. Nel terzo nastro resta \(\kappa(q_0)\) , la codifica dello stato di partenza di M (nastro del contatore istruzioni)

A questo punto andiamo a definire un “interprete”: la parte del programma di U che preleva un’istruzione, la decodifica, la esegue e registra il risultato.

Ecco com’è fatto il programma:

  1. (leggo il program counter) decodifico la stringa sul terzo nastro e ottengo lo stato corrente \(q_{h_i}\) della mcchina M
  2. (prelevo istruzione corrente) sposto la testina 2 sul primo simbolo di \(S_{i,1}...S_{i,l}\) .
  3. (lettura input) Decodifico il dato di input dal nastro 1 che contiene \(\kappa(\sigma_{k_j})\) .
  4. (decodifica e esecuzione istruzione corrente) Se \(S_{i,j} = c\>|^{l_1}\>c\>|^{l_2}\>c|>|^{l_3}\>c|>|^{l_4}\>c|>|^{l_5}\>c\)
    • (aggiorna PC) scrivi sul terzo nastro \(|^{l_3}\) al posto di \(\kappa(q_{h_i})\)
    • (esecuzione) scrivi sul primo nastro \(|^{l_4}\) al posto di \(\kappa(\sigma_{k_j})\)
    • (esecuzione) sposta la testina 1 al precedente o successivo gruppo \(c|^vc\) o lasciala dov’è a seconda di \(l_5\).
    • (condizione d’errore) ferma tutto se \(S_{i,j} = c\>|^{l_1}\>c\>|^{l_2}\>c\>d\>c\>d\>c\>d\>c\)
    • (successo) ferma tutto se \(S_{i,j} = c\>|^{l_1}\>c\>|^{l_2}\>c\>|\>c\>|^{l_4}\>c\>|^{l_5}\>c\)