Macchina di Turing minimale

Sia $T$ una macchina di Turing e sia $<x_i,q_i,q_o,x_o,m>$ una sua quintupla.
Mostriamo che è possibile costruire una macchina di Turing $T_{triple}$ per la quale esista un insieme di triple che, per ogni singola quintupla di $T$, ne simula il comportamento (ovvero dati $x_i$ e $q_i$, stamperà $x_o$ e farà passare la macchina nello stato $q_o$, muovendo la testina in accordo a $m$); tali triple sono della forma $<x,q,y>$ dove $y$ è

1. il simbolo da scrivere al posto di $x$, se $y$ appartiene all'alfabeato;
2. il nuovo stato cui la macchina passa, lasciando lo stato $q$, se $y$ appartiene all'insieme degli stati;
3. il movimento da compiere, se $y$ appartiene all'insieme dei movimenti (destra oppure sinistra).

Per maggiore chiarezza, consideriamo un numero di triple maggiore del necessario.
Riportiamo tali triple e successivamente le discutiamo.

1.  $<x_i,q_i,(q_o^m,x_o^m)>$ per ogni input e stato privi di apice, dove $(q_o^m,x_o^m)$  appartiene all'insieme degli stati di $T_{triple}$;
2.  $<x_i,(q_o^m,x_o^m),x_o^m>$ per ogni input letto diverso dal simbolo $x$ contenuto in $(q,x)$;
3.  $<x_o^m,(q_o^m,x_o^m),q_o^m>$ se l'input letto eguaglia il simbolo $x$ contenuto in $(q,x)$;
4.  $<x_o^m,q_o^m,m>$ se gli apici $m$ dell'input e dello stato sono uguali.
5.  $<x^m,q^{m'},(q,x)>$ \textbf{se gli apici dell'input e dello stato sono diversi.}
6.  $<x,q^{m},(q,x)>$ \textbf{se l'input non ha apice e lo stato sì.}

Studiamo la correttezza della precedente costruzione.
L'alfabeto di $T$ è stato esteso in modo che tutti i simboli contengano due copie di sé , date dal medesimo simbolo con in apice uno dei due movimenti.
L'insieme degli stati di $T$ è stato esteso come quello dell'alfabeto e, inoltre, aggiungendo tutte le
triple date dagli ultimi tre simboli di ogni quintupla nell'insieme delle quintuple di $T$.
Ragioniamo ora, senza perdere di generalità, nel caso in cui $T$ sia deterministica, e dunque l'insieme delle quintuple definisca, a partire dalla coppia input-statoAttuale, la tripla nuovoStato-output-movimento in maniera univoca (in accordo alla formalizzazione data da Ullman e Hopcroft).

1.  Letto il simbolo $x_i$ nello stato $q_i$ pertanto si passerà ad un univocamente identificato stato del tipo $(q_o^m,x_o^m)$;
2. a questo punto la seconda tripla imporrà che l'output su nastro sia quello originariamente voluto dalla macchina $T$ (con l'aggiunta del simbolo del movimento da effettuare in apice);
3. successivamente la terza tripla imporrà che anche il nuovo stato sia quello originariamente voluto dalla macchina $T$ (con l'aggiunta, anche qui, del simbolo del movimento da effettuare in apice);
4. nel momento in cui la macchina legge un input che ha in apice lo stesso simbolo di movimento in apice al proprio stato, compie tale movimento;
5. \textbf{notiamo che sarebbe desiderabile, a scanso di errori, che andandosene dalla cella del nastro in esame la macchina abbia esattamente lo stesso stato e lasci scritto esattamente lo stesso simbolo previsti dalla originaria quintupla. Questo obiettivo viene raggiunto qualora la testina ritorni su tale cella, poiché, nel tornare, lo stato della macchina avrà in apice un simbolo di movimento opposto a quello del simbolo che la testina leggerà} (se "se n'è andata" verso destra, dovrà tornare da sinistra, e viceversa) ; in tal caso la tripla numero 5, assieme alla tripla 2 e 3, riscriverà in maniera ben definita l'input e cambierà lo stato privandoli dell'apice di movimento, e la tripla 1 potrà avere luogo secondo quanto già descritto;
6. nella quintupla la testina si muove dopo che la macchina è passata nello stato $q_o$; pertanto quest'ultima tripla, assieme alla precedente, assicura che spostarsi essendo nello stato $q_o^m$ non creerà problemi.