Per la definizione delle classi di complessità vengono utilizzati molti tipi di Turing, come le macchine deterministiche per il Turing, le macchine probabilistiche, le macchine per il Turing non-deterministiche, le macchine per il Turing quantistiche, le macchine per il Turing simmetriche e le Turing alternate. Sono tutti ugualmente potenti in linea di principio, ma quando le risorse (come il tempo o lo spazio) sono limitate, alcune di esse possono essere più potenti di altre.
Le macchine di rullatura sono comunemente utilizzate per definire cosa?
classi di complessità classi di complessità classi di complessità