Teoremi del corso

Idea: dalla macchina che decide $L$ costruiamo una macchina che si limita ad accettarlo. Basta trasformare ogni risposta "no" in un ciclo infinito.

1. Per ipotesi $L$ è ricorsivo: esiste una MdT $M$ che su ogni input $x$ si ferma, nello stato "yes" se $x \in L$ ($x$ appartiene a $L$) e nello stato "no" se $x \notin L$ ($x$ non appartiene a $L$).
2. Costruiamo $M'$ (si legge "emme primo") che si comporta esattamente come $M$, con una sola modifica: ogni volta che $M$ sta per entrare nello stato "no", $M'$ entra invece in uno stato nuovo in cui sposta il cursore a destra per sempre, senza mai fermarsi. Cambiano solo le transizioni che portano in "no", quindi $M'$ è ancora una MdT.
3. Se $x \in L$, $M$ arriva in "yes". $M'$ fa le stesse mosse di $M$ (la modifica non entra mai in gioco), quindi arriva anch'essa in "yes": $M'(x) = \text{yes}$.
4. Se $x \notin L$, $M$ arriverebbe in "no". Proprio in quel punto $M'$ comincia a muoversi a destra all'infinito, quindi $M'(x) = \nearrow$ (la computazione non termina).
5. I punti 3 e 4 dicono esattamente che $M'$ accetta $L$: "yes" sugli elementi di $L$, nessuna risposta sugli altri. Quindi $L$ è ricorsivamente enumerabile.

Siccome $L$ era un linguaggio ricorsivo qualsiasi, vale $\htmlData{term=R}{\mathrm{R}} \subseteq \htmlData{term=RE}{\mathrm{RE}}$.

Idea: scriviamo i $k$ nastri di $M$ uno dopo l'altro sull'unico nastro di $M'$, segnando dove si trovano i cursori. Ogni passo di $M$ si simula con due scansioni di questo nastro, che è lungo $O(f(n))$: quindi $O(f(n))$ passi per ogni passo di $M$ e $O(f(n)^2)$ in tutto.

1. Codifica. Sia $M = (K, \Sigma, \delta, s)$: $K$ sono gli stati, $\Sigma$ l'alfabeto, $\delta$ il programma, $s$ lo stato iniziale. L'alfabeto di $M'$ contiene $\Sigma$, una versione "marcata" $\underline{\sigma}$ di ogni simbolo $\sigma$ (indica la cella su cui sta un cursore), un simbolo $\triangleright'$ (versione dell'inizio-nastro $\triangleright$ che si può scavalcare) e un separatore $\triangleleft$ che chiude ciascun nastro. Una configurazione di $M$ con nastri $w_1 u_1, \ldots, w_k u_k$ diventa la stringa $\triangleright' w_1 u_1 \triangleleft \triangleright' w_2 u_2 \triangleleft \ldots \triangleright' w_k u_k \triangleleft \triangleleft$, dove in ogni $w_i$ l'ultimo simbolo (quello sotto il cursore) è marcato. Il doppio $\triangleleft$ finale segna la fine del nastro di $M'$.
2. Inizio. $M'$ sposta l'input $x$ di una cella a destra, scrive $\triangleright'$ davanti e aggiunge in fondo i $k-1$ nastri vuoti. Servono pochi stati in più, in numero che dipende solo da $k$ e $\Sigma$, non dall'input.
3. Prima scansione (lettura). $M'$ scorre il nastro da sinistra a destra e raccoglie i $k$ simboli marcati, cioè i simboli letti dai $k$ cursori di $M$. Li "ricorda" nello stato: $M'$ ha uno stato per ogni stato $q$ di $M$ e ogni sequenza di al più $k$ simboli. Sono in numero finito perché $K$, $\Sigma$ e $k$ sono fissati.
4. Seconda scansione (scrittura). Ora $M'$ conosce $q$ e i $k$ simboli letti, quindi sa da $\delta$ che cosa farebbe $M$. Scorre di nuovo il nastro e, a ogni simbolo marcato, scrive il nuovo simbolo e sposta la marcatura nella cella vicina, nella direzione indicata da $\delta$.
5. Caso speciale. Se un cursore di $M$ deve andare a destra oltre la fine del suo nastro (cioè su un $\triangleleft$), serve una cella nuova: $M'$ sposta di una posizione a destra tutto ciò che segue e scrive un blank $\sqcup$ al posto del vecchio $\triangleleft$.
6. Fine. Quando $M$ si ferma, $M'$ cancella i nastri simulati tranne l'ultimo, che contiene l'output, e lo riporta nel formato normale. Quindi $M'(x) = M(x)$.
7. Tempo. $M$ fa al più $f(|x|)$ passi, cioè sta nel budget di tempo $f(n)$, e a ogni passo un nastro cresce al più di una cella: ogni nastro è lungo al più $f(|x|)+1$, e il nastro di $M'$ al più $k(f(|x|)+1)+1$. Simulare un passo costa una scansione avanti e indietro per leggere, più una scansione per ciascuno dei $k$ nastri da modificare (spostamenti compresi): $O(k^2 \cdot f(|x|))$ passi. Per $f(|x|)$ passi di $M$ il totale è $O(k^2 \cdot f(|x|)^2) = O(f(n)^2)$, perché $k$ è una costante che dipende da $M$ e non dall'input.

Idea: i registri della RAM si scrivono su un nastro come coppie (indirizzo, contenuto) in binario, e ogni istruzione della RAM si simula scorrendo questo nastro. Il punto chiave è che i numeri nei registri non possono crescere troppo in fretta, quindi il nastro resta corto.

1. La RAM. Ha un programma finito di istruzioni (lettura dell'input, LOAD, STORE, ADD, SUB, HALF, salti condizionati, HALT) che lavorano su registri $r_0, r_1, \ldots$ contenenti interi grandi a piacere. Non c'è la moltiplicazione: le operazioni aritmetiche sono somma, sottrazione e dimezzamento.
2. Lemma sulla lunghezza dei numeri. Dopo $t$ passi ogni registro contiene un intero lungo in binario al più $t + \ell + b$, dove $\ell$ è la lunghezza dell'input e $b$ la lunghezza della costante più grande del programma. Perché: una somma o una sottrazione allunga un numero al più di un bit, il dimezzamento lo accorcia, e un caricamento copia un numero che c'era già. Quindi a ogni passo la lunghezza massima cresce al più di 1.
3. La MdT. Il primo nastro contiene l'input. Il secondo contiene i registri usati, come sequenza di coppie "indirizzo : contenuto" in binario. L'istruzione corrente si ricorda negli stati, perché il programma è finito. Gli altri nastri tengono l'indirizzo del registro cercato e servono da appoggio per fare somme, sottrazioni e dimezzamenti in binario, come su carta. In tutto bastano 7 nastri.
4. Costo di un'istruzione. In $f(n)$ passi la RAM scrive al più $f(n)$ registri diversi (uno per passo), e per il punto 2 ogni indirizzo e ogni contenuto è lungo $O(f(n))$ (l'input e le costanti si contano nel budget). Quindi il nastro dei registri è lungo $O(f(n)^2)$. Cercare un registro, leggerlo, fare l'operazione e riscrivere il risultato richiede un numero costante di scansioni di questo nastro: $O(f(n)^2)$ passi.
5. Totale. $f(n)$ istruzioni, ciascuna simulata in $O(f(n)^2)$ passi: tempo $O(f(n)^3)$. La MdT calcola la stessa funzione $\varphi$ (fi) perché esegue le stesse istruzioni sugli stessi valori.

Il corso enuncia il teorema senza prova (Teorema 2.5 del Papadimitriou); qui ne è dato lo schema.

Idea: $M'$ usa un solo simbolo per rappresentare un blocco di $m$ simboli di $M$ (come allungare la "parola" di un processore). Così $M'$ simula $m$ passi di $M$ con al più 6 passi propri; scegliendo $m$ abbastanza grande rispetto a $1/\varepsilon$ (epsilon) il tempo scende sotto $\varepsilon \cdot f(n)$, più il tempo lineare per comprimere l'input.

1. Macchina di partenza. Sia $M = (K, \Sigma, \delta, s)$ una MdT a $k$ nastri che decide $L$ entro il budget di tempo $f(n)$, e sia $\varepsilon \gt 0$. $M'$ ha $k$ nastri (2 se $k = 1$) e alfabeto $\Sigma' = \Sigma \cup \Sigma^m$: oltre ai simboli di $M$, tutte le $m$-uple di simboli. L'intero $m$ dipende solo da $\varepsilon$ e lo fissiamo alla fine. Alfabeto e programma di $M'$ diventano enormi, ma restano finiti.
2. Compressione dell'input. $M'$ scorre l'input $x$ ricordando nello stato i simboli già letti del blocco corrente; ogni $m$ simboli scrive sul secondo nastro il singolo simbolo $(\sigma_1 \ldots \sigma_m)$, completando l'ultimo blocco con dei $\sqcup$. Questo costa $|x| + 2$ passi. Da qui in poi il secondo nastro fa la parte del nastro di input di $M$, e tutti i nastri contengono solo blocchi.
3. Rappresentazione. Se $M$ è nello stato $q$ e il suo cursore $i$-esimo è nella cella numero $\ell_i$, allora $M'$ è nello stato $(q, \ell_1 \mathbin{\mathrm{mod}} m, \ldots, \ell_k \mathbin{\mathrm{mod}} m)$, cioè ricorda dove si trova ogni cursore dentro il suo blocco, e il cursore $i$-esimo di $M'$ sta sul blocco che contiene la cella $\ell_i$. Questi stati sono $|K| \cdot m^k$, un numero finito.
4. Una fase: lettura. Su ogni nastro $M'$ fa un passo a sinistra, due a destra e uno a sinistra (4 passi), memorizzando nello stato anche i blocchi a sinistra e a destra del cursore. Ora conosce i $3m$ simboli di $M$ intorno a ciascun cursore.
5. Una fase: scrittura. In $m$ passi un cursore di $M$ si sposta al più di $m$ celle, quindi non esce da questi $3m$ simboli. Allora l'effetto dei prossimi $m$ passi di $M$ è già determinato da ciò che $M'$ ha nello stato, e il programma $\delta'$ di $M'$ è costruito per applicarlo direttamente: cambiano solo il blocco centrale e uno dei due vicini, e bastano 2 passi. Se $M$ si ferma durante questi $m$ passi, $M'$ si ferma con la stessa risposta. Quindi $M'$ decide $L$.
6. Conto. $M'$ usa $|x| + 2$ passi per la compressione e poi al più 6 passi per ogni gruppo di $m$ passi di $M$: in tutto circa $|x| + 2 + 6 \cdot f(|x|)/m$. Scegliendo $m = \lceil 6/\varepsilon \rceil$ (il più piccolo intero $\ge 6/\varepsilon$) si ha $6/m \le \varepsilon$, quindi $M'$ lavora in tempo $\varepsilon \cdot f(n) + n + 2$.

Idea: $M'$ copia l'input su un nastro di lavoro e da lì in poi lascia il primo nastro solo in lettura; simula $M$ sui nastri centrali e alla fine copia il risultato sull'ultimo nastro scrivendo solo verso destra. Ogni fase costa $O(f(n))$.

1. Vincoli da rispettare. Una MdT con input e output deve avere: (a) il primo nastro mai modificato (sola lettura); (b) sull'ultimo nastro il cursore mai verso sinistra (sola scrittura); (c) il cursore dell'input mai oltre il primo $\sqcup$ dopo l'input.
2. Fase 1: copia dell'input. $M'$ scorre il primo nastro e copia $x$ sul secondo nastro: $O(n)$ passi, con $n = |x|$. Il primo nastro viene solo letto e il cursore si ferma al primo $\sqcup$, quindi (a) e (c) valgono; dopo questa fase il primo nastro non si usa più.
3. Fase 2: simulazione. $M'$ riporta il cursore del secondo nastro all'inizio e simula $M$ usando i nastri $2, \ldots, k+1$ al posto dei nastri $1, \ldots, k$ di $M$: ogni passo di $M$ diventa un passo di $M'$. Il primo e l'ultimo nastro non vengono toccati. Costo: al più $f(n)$ passi, perché $M$ rispetta il budget di tempo $f(n)$.
4. Fase 3: copia dell'output. Quando $M$ si ferma, il suo output sta sul suo ultimo nastro, cioè sul nastro $k+1$ di $M'$. $M'$ lo copia sul nastro $k+2$ muovendo quel cursore solo verso destra, quindi (b) vale. In $f(n)$ passi $M$ non può scrivere più di $f(n)$ celle, quindi questa copia costa $O(f(n))$ passi.
5. Correttezza e tempo. $M'$ finisce nello stesso stato di $M$ ("yes", "no" o $h$) e con lo stesso output. Il tempo totale è $O(n) + f(n) + O(f(n)) = O(f(n))$, perché un budget di tempo è sempre almeno $n$ (la macchina deve poter leggere l'input).

Idea: come nello speedup lineare, si codificano $m$ celle dei nastri di lavoro in un solo simbolo, così lo spazio occupato si divide per $m$. Qui non serve comprimere l'input, perché il nastro di input non si conta nello spazio.

1. Partenza. Sia $M$ una MdT con input e output che decide $L$ entro il budget di spazio $f(n)$, e sia $\varepsilon \gt 0$. Scegliamo un intero $m \ge 1/\varepsilon$. Per semplicità consideriamo un solo nastro di lavoro; con più nastri si ripete lo stesso trucco su ciascuno.
2. Nuovo alfabeto. $M'$ ha gli stessi nastri di $M$. Sul nastro di input lavora esattamente come $M$. Sul nastro di lavoro usa l'alfabeto $\Sigma^m$: ogni cella di $M'$ contiene un blocco di $m$ celle consecutive di $M$.
3. Stati. Lo stato di $M'$ ricorda lo stato di $M$ e in quale delle $m$ posizioni del blocco corrente si trova il cursore di $M$. Sono in numero finito, perché $K$, $\Sigma$ e $m$ sono fissati.
4. Simulazione di un passo. Dallo stato $M'$ sa quale simbolo del blocco sta leggendo $M$; riscrive il blocco con quel simbolo cambiato e aggiorna la posizione interna. Sposta il proprio cursore sul blocco vicino solo quando il cursore di $M$ esce dal blocco. Quindi $M'$ fa le stesse mosse di $M$ e dà la stessa risposta (qui il tempo non ci interessa).
5. Spazio. Il nastro di lavoro di $M$ è lungo al più $f(n)$ celle. Togliendo la cella iniziale con $\triangleright$, che $M'$ tiene a parte, il resto occupa al più $\lceil f(n)/m \rceil \le f(n)/m + 1$ celle di $M'$. In tutto al più $2 + f(n)/m \le 2 + \varepsilon \cdot f(n)$, perché $1/m \le \varepsilon$. Il "$+2$" conta la cella di $\triangleright$ e l'arrotondamento dell'ultimo blocco.

Il corso dice solo "prova simile al linear speedup" (Problema 2.8.14 del Papadimitriou); questo è lo schema standard.

Idea: una MdT deterministica è un caso particolare di MdT nondeterministica, quella in cui in ogni situazione c'è esattamente una mossa possibile.

1. Sia $L \in \htmlData{term=P}{\mathrm{P}}$: esiste una MdT deterministica $M = (K, \Sigma, \delta, s)$ che decide $L$ entro il budget di tempo $n^k$, per un $k$ fissato.
2. Definiamo $N = (K, \Sigma, \Delta, s)$, dove la relazione $\Delta$ (delta maiuscola) contiene, per ogni coppia (stato $q$, simbolo $\sigma$), solo la mossa $\delta(q, \sigma)$ prescritta da $M$. $\Delta$ è una relazione che per caso è una funzione, quindi $N$ è a tutti gli effetti una MdT nondeterministica.
3. Su ogni input $x$, $N$ ha una sola computazione possibile, perché a ogni passo ha una sola scelta: è identica alla computazione di $M$.
4. $N$ accetta $x$ se e solo se esiste una computazione che termina in "yes". L'unica computazione è quella di $M$, quindi $N$ accetta $x \iff M(x) = \text{yes} \iff x \in L$. Dunque $N$ decide $L$.
5. L'unica computazione di $N$ ha la stessa lunghezza di quella di $M$, cioè al più $|x|^k$ passi. Quindi $L \in \mathrm{NTIME}(n^k) \subseteq \htmlData{term=NP}{\mathrm{NP}}$.

Poiché $L$ era un qualsiasi problema di P, vale $\htmlData{term=P}{\mathrm{P}} \subseteq \htmlData{term=NP}{\mathrm{NP}}$.

Idea: ogni computazione di $N$ è individuata dalla sequenza delle scelte fatte a ogni passo. La macchina deterministica $M$ prova tutte le sequenze di scelte, dalle più corte alle più lunghe; sono al più circa $d^{f(n)}$, e ognuna si controlla in tempo $O(f(n))$.

1. Grado di nondeterminismo. Sia $N = (K, \Sigma, \Delta, s)$. Per ogni stato $q$ e simbolo $\sigma$, l'insieme $C_{q,\sigma}$ delle mosse possibili è finito, perché $\Delta$ è finita. Sia $d$ il massimo numero di mosse possibili, $d = \max |C_{q,\sigma}|$. Se $d = 1$, $N$ è già deterministica e non c'è nulla da fare; quindi $d \gt 1$. Numeriamo le mosse di ogni $C_{q,\sigma}$ da 1 a $d$.
2. Computazioni come sequenze. Una computazione di $t$ passi è determinata da una sequenza $(c_1, \ldots, c_t)$ di interi tra 1 e $d$: $c_i$ dice quale mossa scegliere al passo $i$.
3. La macchina $M$. Ha 3 nastri: il primo con l'input, il secondo con la sequenza corrente, il terzo per simulare $N$. Genera le sequenze in ordine di lunghezza $(1, 2, \ldots, d, 11, 12, \ldots)$; passare alla successiva è come aggiungere 1 a un numero in base $d$.
4. Prova di una sequenza. $M$ simula $N$ per $t$ passi seguendo le scelte $c_1, \ldots, c_t$ (se una scelta non esiste in quella situazione, scarta la sequenza). Se la simulazione arriva in "yes", anche $M$ si ferma in "yes".
5. Quando rifiutare. $M$ non conosce il budget $f(n)$, quindi non può fermarsi "a $f(n)$". Usa questa regola: se per una certa lunghezza $t$ tutte le sequenze portano a computazioni già ferme (in "no" o in $h$), nessuna computazione di $N$ va oltre, e nessuna ha accettato; allora $M$ si ferma in "no". Questo succede al più tardi per $t = f(n)$, perché tutte le computazioni di $N$ si fermano entro $f(n)$ passi.
6. Correttezza. $M$ risponde "yes" se e solo se qualche sequenza di scelte porta $N$ in "yes", cioè se e solo se $N$ accetta $x$, cioè se e solo se $x \in L$.
7. Tempo. Le sequenze lunghe al più $f(n)$ sono $d + d^2 + \ldots + d^{f(n)} = O(d^{f(n)})$ (somma geometrica). Generarne una e simulare al più $f(n)$ passi costa $O(n + f(n)) = O(f(n))$. Il totale $O(f(n) \cdot d^{f(n)})$ è $O(c^{f(n)})$ con una costante $c \gt d$, per esempio $c = 2d$, perché $f(n) \le 2^{f(n)}$. La costante $c$ dipende solo da $N$.

Idea: la macchina "indovina" il cammino un nodo alla volta e ricorda solo il nodo corrente e il prossimo. Sono due numeri tra 1 e $n$, che in binario occupano $O(\log n)$ celle.

1. Il problema. L'input è un grafo con nodi $1, \ldots, n$ dato con la matrice di adiacenza; la domanda è se c'è un cammino dal nodo 1 al nodo $n$. (Se $1 = n$ la risposta è subito "yes".)
2. La macchina $N$, a 3 nastri. Il primo nastro contiene la matrice ed è in sola lettura. Il secondo contiene il nodo corrente $i$, all'inizio 1. Il terzo contiene il prossimo nodo $j$ del cammino.
3. Un passo. $N$ sceglie nondeterministicamente $j$ tra 1 e $n$ e lo scrive in binario sul terzo nastro. Poi legge nella matrice il bit in posizione $(i, j)$. Se è 0 (non c'è l'arco da $i$ a $j$) si ferma in "no". Se è 1 e $j = n$ si ferma in "yes". Altrimenti copia $j$ sul secondo nastro, al posto di $i$, e ripete.
4. Se c'è un cammino, $N$ accetta. Sia $1, v_1, \ldots, v_k = n$ un cammino. La computazione che sceglie proprio $v_1, v_2, \ldots$ trova sempre il bit 1 e arriva in "yes". Per accettare basta una computazione.
5. Se $N$ accetta, c'è un cammino. Una computazione che arriva in "yes" ha controllato che ogni arco tra due nodi scelti consecutivi esiste davvero, quindi i nodi scelti formano un cammino da 1 a $n$. Se il cammino non esiste, nessuna computazione accetta: $N$ decide REACHABILITY.
6. Spazio. Il nastro di input non si conta. Il secondo e il terzo nastro contengono sempre un numero tra 1 e $n$ in binario, cioè circa $\log n$ celle ciascuno: $O(\log n)$ in tutto. L'input è lungo circa $n^2$, ma $\log(n^2) = 2 \log n$, quindi lo spazio è logaritmico anche rispetto alla lunghezza dell'input.
7. Computazioni infinite. Alcune computazioni possono girare per sempre in un ciclo del grafo. La definizione di decisione nondeterministica lo permette. Volendo, si aggiunge un contatore fino a $n$, anch'esso di $O(\log n)$ celle, che fa rifiutare dopo $n$ passi: un cammino senza ripetizioni ha meno di $n$ archi.

Idea: costruiamo il budget $f$ in modo che, per ogni lunghezza $n$, nessuna delle "prime" $n+1$ macchine si fermi su input lunghi $n$ dopo un numero di passi compreso tra $f(n)$ e $2^{f(n)}$. Allora tutto ciò che si fa entro $2^{f(n)}$ passi si fa già entro $f(n)$ passi.

1. Enumerazione. Elenchiamo tutte le MdT: $M_0, M_1, M_2, \ldots$
2. Intervalli. Fissato $n$, definiamo $k_1 = 2n$ e $k_{j+1} = 2^{k_j} + 1$. Gli intervalli $[k_j, 2^{k_j}]$ sono disgiunti, uno dopo l'altro.
3. Un intervallo libero. Consideriamo le macchine $M_0, \ldots, M_n$ su tutti gli input di lunghezza $n$: è un numero finito, diciamo $N$, di computazioni. Una computazione che si ferma lo fa dopo un numero preciso di passi, quindi "cade" in al più un intervallo. Con $N$ computazioni e $N+1$ intervalli, almeno un intervallo è libero: nessuna computazione si ferma lì dentro. Poniamo $f(n) = k_j$, dove $j$ è il primo intervallo libero.
4. $f$ è ricorsiva. Per controllare se l'intervallo $j$ è libero basta simulare ogni computazione per al più $2^{k_j}$ passi, un numero finito; provando $j = 1, 2, \ldots$ in ordine si trova il primo libero.
5. Il gap. Sia $L \in \mathrm{TIME}(2^{f(n)})$, deciso da una macchina $M_i$. Per ogni $n \ge i$, $M_i$ è tra le macchine considerate per $n$. Su un input lungo $n$ si ferma entro $2^{f(n)}$ passi, ma non dentro $[f(n), 2^{f(n)}]$, perché quell'intervallo è libero: quindi si ferma in meno di $f(n)$ passi.
6. Input corti. Restano gli input con $n \lt i$: sono un numero finito, e una macchina può dare la risposta su di essi con una tabella scritta negli stati, in pochissimi passi. Quindi $L \in \mathrm{TIME}(f(n))$. L'altra inclusione, $\mathrm{TIME}(f(n)) \subseteq \mathrm{TIME}(2^{f(n)})$, è ovvia.

La $f$ costruita è ricorsiva ma non propria: per questo i teoremi di gerarchia richiedono funzioni proprie. Il corso non dà la prova (e la segna come non richiesta): questo è lo schema del Teorema 7.3 del Papadimitriou.

Idea: $M'$ prima calcola, con la macchina $M_f$ della funzione propria, un "metro" di esattamente $f(|x|)$ simboli; poi lo usa come sveglia (budget di tempo) o come recinto di memoria (budget di spazio). Così tempo e spazio di $M'$ dipendono solo da $|x|$, cioè $M'$ è precisa.

1. Funzione propria. $f$ è non decrescente ed esiste una MdT $M_f$ che, su ogni input $x$, scrive sul suo ultimo nastro esattamente $f(|x|)$ quasi-blank $\sqcap$, in tempo $O(|x| + f(|x|))$ e spazio $O(f(|x|))$; passi e spazio di $M_f$ dipendono solo da $|x|$.
2. Prima fase (uguale in tutti i casi). $M'$ esegue $M_f$ su $x$ usando nastri propri. Questa fase è deterministica e la sua durata dipende solo da $|x|$. Il risultato è il metro di lunghezza $f(|x|)$.
3. Budget di tempo. $M'$ simula $M$ su altri nastri e, dopo ogni passo simulato, sposta di una cella a destra il cursore sul metro. Se $M$ si ferma prima della fine del metro, $M'$ ricorda la risposta e continua a scorrere il metro fino al primo vero blank $\sqcup$. Siccome $M$ si ferma entro $f(|x|)$ passi, la simulazione arriva sempre in fondo e la risposta è quella di $M$. I passi totali sono quelli di $M_f$ più $f(|x|)$, più una costante: dipendono solo da $|x|$, quindi $M'$ è precisa. Il tempo è $O(n + 2f(n)) = O(f(n))$, perché un budget di tempo è almeno $n$.
4. Budget di spazio. $M'$ fa una copia del metro per ogni nastro di lavoro di $M$ e simula $M$ scrivendo sui quasi-blank, che tratta come blank. $M$ usa al più $f(|x|)$ celle per nastro, quindi non esce mai dal metro. Alla fine ogni nastro di lavoro è lungo esattamente $f(|x|)$, perché le celle non usate restano $\sqcap$: la lunghezza dipende solo da $|x|$, quindi $M'$ è precisa. Lo spazio è $O(f(n))$ per $M_f$ più $k \cdot f(n)$ per i $k$ nastri: $O(f(n))$.
5. Caso nondeterministico. Se $M$ è nondeterministica, anche la simulazione lo è, ma i ragionamenti dei punti 3 e 4 valgono per ogni computazione: la durata o lo spazio dipendono solo dalla fase deterministica di $M_f$ e dalla lunghezza del metro, uguali per tutte le computazioni.

Idea: con un budget di spazio $f(n)$ la macchina ha solo un numero finito $c$ di configurazioni diverse. Se fa più di $c$ passi ne ha ripetuta una, quindi è in un ciclo e la si può fermare in "no". Un contatore fino a $c$ sta in $O(f(n))$ celle.

1. Contare le configurazioni. Una configurazione è data da stato, contenuto del nastro e posizione del cursore. Come nella dispensa, consideriamo un nastro di lavoro lungo al più $f(n)$: gli stati sono $|K|$, i contenuti possibili al più $|\Sigma|^{f(n)}$, le posizioni del cursore al più $f(n)+1$. Quindi le configurazioni sono al più $c = |K| \cdot |\Sigma|^{f(n)} \cdot (f(n)+1)$. Con più nastri, e con la posizione del cursore di input, si aggiungono fattori dello stesso tipo e il ragionamento non cambia.
2. Oltre $c$ passi c'è un ciclo. Una computazione di più di $c$ passi attraversa più di $c$ configurazioni, quindi (principio dei cassetti) ne ripete una. Se $M$ è deterministica, da quel punto ripete lo stesso tratto per sempre e non risponderà mai. Se $M$ è nondeterministica, una computazione che accetta si può accorciare togliendo il tratto tra le due ripetizioni; quindi, se $x \in L$, c'è una computazione che accetta entro $c$ passi.
3. La macchina $M'$. Simula $M$ contando i passi; se il contatore arriva a $c$ e $M$ non si è fermata, $M'$ si ferma in "no". Per il punto 2 le computazioni troncate non servono per accettare, quindi $M'$ decide lo stesso linguaggio $L$, e ogni sua computazione termina.
4. Il contatore. $f$ è propria, quindi $M'$ può prima eseguire $M_f$ e ottenere un metro di $f(n)$ celle. Il contatore è fatto così: una cella con $|K|$ simboli possibili, $f(n)$ celle con simboli di $\Sigma$ (un numero in base $|\Sigma|$), e $f(n)+1$ celle usate in unario. Il suo valore massimo è proprio $c$. A ogni passo simulato $M'$ incrementa il contatore; quando trabocca, forza il "no".
5. Spazio. Metro e contatore occupano $O(f(n))$ celle, la simulazione di $M$ al più $f(n)$: in tutto $O(f(n))$.

Idea: in una macchina deterministica basta scambiare gli stati "yes" e "no": la computazione è la stessa, cambia solo la risposta finale.

1. Sia $C = \mathrm{TIME}(f(n))$ oppure $\mathrm{SPACE}(f(n))$, e sia $L \in C$: esiste una MdT deterministica $M$ che decide $L$ entro il budget $f(n)$. "Decide" vuol dire che su ogni input $x$ si ferma, in "yes" se $x \in L$ e in "no" se $x \notin L$.
2. Sia $M'$ la macchina ottenuta da $M$ scambiando nel programma $\delta$ gli stati "yes" e "no": ogni transizione che portava in "yes" ora porta in "no", e viceversa.
3. Su ogni input $M'$ fa esattamente le stesse mosse di $M$, perché la macchina è deterministica e ha una sola computazione. Quindi usa lo stesso tempo e lo stesso spazio, e si ferma nello stato opposto.
4. Perciò $x \in \overline{L}$ (il complemento di $L$) $\iff x \notin L \iff M(x) = \text{no} \iff M'(x) = \text{yes}$. Cioè $M'$ decide $\overline{L}$ entro lo stesso budget: $\overline{L} \in C$.
5. Da qui le due inclusioni. Se $L \in \mathrm{co}C$, allora $L$ è il complemento di un linguaggio di $C$, e per il punto 4 sta in $C$: $\mathrm{co}C \subseteq C$. Se $L \in C$, per il punto 4 $\overline{L} \in C$, quindi $L$, che è il complemento di $\overline{L}$, sta in $\mathrm{co}C$: $C \subseteq \mathrm{co}C$. Dunque $C = \mathrm{co}C$.
6. P è l'unione delle classi $\mathrm{TIME}(n^k)$, ognuna chiusa per complemento, quindi $\htmlData{term=P}{\mathrm{P}} = \mathrm{coP}$.

Con una macchina nondeterministica il trucco non funziona: scambiando "yes" e "no" si accetterebbe quando esiste una computazione che rifiuta, mentre per il complemento servirebbe che tutte rifiutino.

Idea: una macchina universale $U_f$ simula $M$ su $x$ passo per passo, con una "sveglia" lunga $f(|x|)$ che le dice quando smettere. Ogni passo simulato costa $O(f(n)^2)$ e i passi sono al più $f(n)$, quindi il totale è $O(f(n)^3)$; lo speedup lineare toglie la costante.

1. Ingredienti. $U_f$ ha 4 nastri e combina macchine già viste: la MdT universale $U$, la simulazione di $k$ nastri su uno solo, lo speedup lineare e la macchina $M_f$ della funzione propria $f$. Sia $n$ la lunghezza dell'input $M;x$.
2. Sveglia. $U_f$ esegue $M_f$ su $x$ e scrive sul quarto nastro $f(|x|)$ simboli, che faranno da sveglia. Costa $O(|x| + f(|x|)) = O(f(n))$ passi, perché $|x| \le n$ e $f$ non decresce.
3. Preparazione. $U_f$ copia la descrizione di $M$ sul terzo nastro, lascia sul primo nastro la codifica di $\triangleright x$ e scrive sul secondo la codifica dello stato iniziale. Controlla anche che $M$ sia la descrizione corretta di una MdT, e se non lo è rifiuta. Tutto in $O(n + f(n)) = O(f(n))$ passi, perché $f(n) \ge n$.
4. Simulazione di un passo. I nastri di $M$ sono scritti uno dopo l'altro sul primo nastro di $U_f$, come nella simulazione multinastro. Con una prima scansione $U_f$ raccoglie i simboli letti dai cursori di $M$ e li scrive sul secondo nastro, dopo lo stato. Poi cerca sul terzo nastro la transizione di $M$ che corrisponde, e con una seconda scansione applica le modifiche sul primo nastro. Infine sposta di una cella il cursore della sveglia.
5. Costo di un passo. $M$ ha $k_M$ nastri, ciascuno lungo al più $f(|x|)$ celle, e ogni stato o simbolo di $M$ è codificato con $\ell_M$ bit. Il primo nastro è lungo $O(k_M \cdot \ell_M \cdot f(|x|))$ e un passo costa $O(\ell_M \cdot k_M^2 \cdot f(|x|))$, più $O(n)$ per la ricerca sul terzo nastro. Sia $\ell_M$ sia $k_M$ sono al più $\log n$: la codifica di uno stato o simbolo ha circa $\log(|\Sigma|+|K|+6)$ bit, e il programma ha almeno una riga per ogni combinazione di $k_M$ simboli, quindi la descrizione di $M$ è lunga almeno $2^{k_M}$. Allora $\ell_M \cdot k_M^2 \le \log^3 n = O(n) = O(f(n))$, e un passo costa $O(f(n)^2)$, con una costante che non dipende da $M$.
6. Risposta. Se la simulazione arriva in "yes" prima che la sveglia finisca, $U_f$ accetta; se $M$ rifiuta, o se la sveglia arriva in fondo (sono passati $f(|x|)$ passi), $U_f$ rifiuta. Questo è esattamente il test "$M$ accetta $x$ in al più $f(|x|)$ passi", quindi $U_f$ decide $H_f$.
7. Tempo totale. Al più $f(|x|) \le f(n)$ passi simulati, ciascuno in $O(f(n)^2)$, più $O(f(n))$ di preparazione: $O(f(n)^3)$. Con lo speedup lineare (trattare più simboli come uno solo) si scende ad al più $f(n)^3$ passi: $H_f \in \mathrm{TIME}(f(n)^3)$.