In letteratura sono stati proposti molti modelli di macchine diverse dalle macchine Turing a nastro multiplo standard, ad esempio macchine ad accesso casuale. Forse sorprendentemente, ognuno di questi modelli può essere convertito in un altro senza fornire alcuna potenza computazionale supplementare. Il tempo e il consumo di memoria di questi modelli alternativi possono variare. Tutti questi modelli hanno in comune il fatto che le macchine funzionano in modo deterministico.
Nel considerare le Turing machine e le variabili alternative, quale misura non è stata influenzata dalla conversione tra i modelli di macchine?
potenza computazionale potenza computazionale potenza computazionale