In questa lezione dimostro alcuni teoremi che ci portano alla costruzione della macchina delle macchine: la Macchina di Turing Universale, capace di simulare qualsiasi altra macchina di Turing.

Si tratta di un concetto molto interessante, anche perché ci avvicina ai computer programmabili a cui siamo abituati ai giorni d’oggi. È affascinante constatare che un’invenzione così importante sia stata realizzata solo dopo lo sforzo e l’inventiva di matematici che ne hanno teorizzato e dimostrato l’esistenza teorica. Soltanto con le successive scoperte e miglioramenti tecnologici è stato possibile concretizzare questo modello astratto nel nostro mondo fisico.

Macchina di Turing Universale

Il teorema di enumerazione garantisce l’esistenza della macchina di Turing Universale \(M_z\) che è in grado di ricevere in input i e x e di simulare la macchina \(M_i\) applicata a x.

A differenza da quanto previsto da Alan Turing, ovvero un esecutore umano delle MdT, grazie al teorema di enumerazione abbiamo una macchina in grado di eseguire qualsiasi algoritmo.

Per comodità descriveremo una Macchina di Turing Universale usando una MdT con 3 nastri semi-infiniti a destra. Vedremo che la macchina a n nastri è del tutto equivalente a una MdT a 1 nastro.

Aggiungiamo inoltre un altro insieme di stati ausiliario \(Q_\star\) e un altro alfabeto ausiliario \(\Sigma_\star\). Questi insiemi sono gli insiemi che verranno utilizzati dalle macchine simulate. Rappresentiamo tutti gli elementi degli insiemi ausiliari come stringhe del monoide \(\{|\}^\star\) mediante una funzione di codifica \(\mathcal{k}\):

Notiamo che k non è biunivoca, ma lo è quando sappiamo se la stringa che dobbiamo decodificare è uno stato o un simbolo o una direzione. Possiamo ovviare a questo inconveniente separando sul nastro la codifica degli stati, simboli e direzioni con un apposito simbolo c separatore.

A questo punto vogliamo codificare una macchina \(M = (Q,\Sigma,\delta,h)\) . Prima di codificare la macchina definiamo un ordinamento totale degli stati \(Q = \{q_{i1},...,q_{ik}\}\) e i simboli \(\Sigma = \{\sigma_{j1},...,\sigma_{jl}\}\) in modo che \(p \leq p' \implies i_p \leq i_{p'} \wedge j_p \leq j_{p'}\) .

Consideriamo l’alfabeto \(\{|,c,d,\#,\triangleright\}\) , ipotizzando che \(\{|,c,d\} \cap (\Sigma_\star \cup Q_\star) = \emptyset\) (i simboli |, c e d non sono inclusi nell’alfabeto della macchine simulabili) e ricordando che c è un separatore e codifichiamo ogni quintupla di M così:

Infine andiamo a codificare anche i casi in cui δ non è definita, ponendo:

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

Esempio: vogliamo codificare una MdT \(M = (\{q_0\}, \{\sigma_1,\sigma_3,\sigma_5\}, \delta, h)\) , dove

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

Diamo tutto in pasto a ρ:

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 τ:

Quindi una codifica completa di M sarà data da:

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

1. se \((s,\underline{\triangleright}w) \rightarrow_M^\star (h,u\underline{a}v) \implies (s_U, \triangleright\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{\triangleright}\rho(M)\tau(w)) \rightarrow_U^\star (h, u'\underline{a'}v') \implies a'=\#, v' = \epsilon, u' = \tau(uav)\) per qualche u, a e v tali che \((s,\underline{\triangleright}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\)