Calcolabilità e Complessità: optional delle TM

Oggi parliamo delle macchine del nostro caro signor Turing, in particolare: macchine multitraccia e macchine multinastro.
Sul perché si chiamino multitraccia e multinastro dovremmo esserci tutti, quindi non ve lo racconto!

Quello che più bisogna considerare e che è più richiesto sapere è vedere il costo in termini di tempo e spazio rispetto ad una mononastro monotraccia.
Data una multitraccia, realizziamo una monotraccia per vedere quanto ci costa.
Costruiamo una TM M con k tracce, e poniamo k = 3. La testina leggerà quindi il valore su ogni nastro nella stessa celletta di memoria contemporaneamente. Visto che non posso disegnare, guardatela dagli appunti o dal libro, così ci capiamo meglio.
Supponiamo che la testina legga a-b-a rispettivamente sul primo, secondo e terzo nastro, questi caratteri verranno copiati sulla mononastro e, grazie alla memoria nello stato, memorizzerà i caratteri letti, di modo che sa quando ha letto una sequenza di caratteri per passare alla successiva. Sulla mononastro ci sarà quindi una sequenza di blocchi di k caratteri e, con la memoria nello stato, li legge e fa le opportune modifiche secondo ciò che prevede la funzione di transizione di M.
Quale sarà il costo?
Nel caso peggiore sarà 3k passi di cui k per il controllo, k per la modifica (nel caso peggiore deve tornare all'inizio per modificare) e k di riscorrimento per superare il blocco.
Se la multitraccia ha una complessità O(m), cioè impiega m passi, la monotraccia ci impiegherà m*3k passi. Ma 3k indica che questo è un accrescimento costante, che dipende dal numero di tracce. Asintoticamente parlando, sappiamo che la costante 3k può essere non considerata, quindi nel complesso anche la monotraccia ha una complessità O(m).

Provo ora a spiegarvi la simulazione di una multinastro con una mononastro multitraccia. Se avete il disegnino davanti è meglio.
Sia M la macchina di Turing multinastro con k nastri, ipotizziamo di nuovo k=3. La simuleremo su una mononastro multitraccia con 2k tracce dove su k tracce saranno memorizzati i k nastri della multinastro e sui rimanenti k viene posto un marcatore che rappresenta la posizione delle testine di M sui nastri.
Se M impiega m passi per accettare, 2m sarà la massima distanza dopo m passi tra i marcatori. Partendo dai marcatori a sinistra, andiamo verso destra per trovarne altri e, una volta trovati, si implementano le modifiche che si devono fare secondo gli stati. Dopo di questo si ritorna a sinistra e si ripete.
Quanto ci costa tutto questo?
Abbiamo quindi 2m passi che è la distanza massima tra i marcatori, altri 2m passi devono essere fatti per tornare indietro e, in più, ci saranno altri 2k passi da sommare, che rappresentano i passi necessari per mettere un nuovo marcatore.
Supponiamo che M impieghi t(n) passi per accettare, per la mononastro sarà la sommatoria per i che va da 1 a t(n) di 4i+2k.
2k è una costante, che può essere portata al di fuori della sommatoria, moltiplicata per t(n). Resta dunque 4i: il 4, essendo costante, possiamo portarlo al di fuori del simbolo di sommatoria, rimanendo così la sommatoria fino a t(n) di i.
E guarda caso esce fuori Gauss, perché ne sentivamo la mancanza. Quella sommatoria di i si risolve con la classica formula n(n+1)/2....
eliminando tutti i numeretti per avere la solita complessità asintotica, esce O(t(n)^2). Niente paura, questo significa che sia la multinastro che la mononastro sono polinomiali!