3 ms·
Turing machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes lik
by tromp 2y ago
Turing machines are still quite prevalent in complexity theory. Of course, robust classes like P and NP are invariant under various models, but also classes like DTIME and NTIME are defined for (single- or multi-tape) Turing machines [1].
[1] https://en.wikipedia.org/wiki/DTIME https://en.wikipedia.org/wiki/DTIME