Complessità del calcolo

Data la computazione di , la complessità temporale di è se si ferma in un dato , altrimenti. La complessità spaziale è definita come con lunghezza del contenuto del -esimo nastro alla mossa -esima, cioè la somma delle quantità di nastro occupate, per ogni nastro.

Sotto opportune ipotesi, è possibile semplificare da e a e , dove è la lunghezza dell'input. Generalmente scegliamo, sia per che per :

• Caso pessimo:
• Caso ottimo:
• Caso medio:

Definiamo come l'insieme di funzioni con dominio in :

Definiamo come l'insieme di funzioni con dominio in : >

Definiamo come l'insieme di funzioni con dominio in : >

Spesso è necessario trovare un compromesso spazio-temporale per la risoluzione di un problema.

In generale si ha che:

• e
• e
• non potrà mai essere minore di

Si ha che:

• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con
• Se è accettato da una MT a nastri in , posso costruire una MT a nastro (non nastro singolo) con
• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con
• Se è accettato da una MT a nastri in , per ogni posso costruire una MT a nastri con

Dimostriamo il primo teorema:

Scegliamo un fattore di compressione intero tale che . Per ognuno degli nastri di , considero l'alfabeto e costruisco di creando un elemento in per ogni . Costruiamo quindi l'OC di in moto tale per cui:

• Calcoli con i nuovi simboli sui nastri emulando le mosse di spostando le testine sui nastri di ogni movimenti di
• Memorizzi la posizione della testina "all'interno" dei nuovi simboli degli alfabeti di nastro , usando gli stati.

Dimostriamo il quarto teorema:

Usiamo un approccio simile a quello precedente: codifichiamo in modo compresso i simboli dell'alfabeto e calcoliamo sui simboli compressi. Dobbiamo considerare che la compressione è fatta a runtime: il minimo costo per effettuare la compressione è lineare nel numero di simboli da comprimere.

Comprimendo simboli in uno, nel caso pessimo, possono servirmi mosse per emularne di .

La macchina RAM ha un nastro di lettura In e uno di scrittura Out come nella MT. Assumiamo il programma cablato nell'OC, così come la logica del program counter. La RAM è dotata di una memoria ad accesso a indirizzamento diretto al posto dei nastri di memoria: l'accesso non necessita di scorrimento delle celle. Le istruzioni di un programma usano come primo operando sorgente e come operando destinazione . Ogni cella contiene un intero .

Si ha che copiare/spostare/scrivere/leggere un intero costa tanto quanto il suo numero di cifre in base : .
Il costo delle operazioni aritmetico/logiche elementari dipende dall'operazione, definendo si ha che:

• Le addizioni e sottrazioni al bit costano
• Le moltiplicazioni, scolasticamente, costano
• Le divisioni, scolasticamente, costano

Le istruzioni JUMP e HALT sono a costo costante.

Risolvere lo stesso problema con macchine diverse può dare luogo a complessità diverse. In generale non esiste un modello migliore in assoluto.

Sotto "ragionevoli" ipotesi di criteri di costo, se un problema è risolvibile da in , allora è risolvibile da qualsiasi altro modello in dove è un opportuno polinomio.