Quasilinear Emulation of Turing Machines by S-machines

Bogdan Chornomaz, Francis Wagner

We prove that for any $\epsilon >0$, a non-deterministic Turing machine $\mathcal{T}$ with time complexity $T(n)$ can be emulated by an $S$-machine with time and space complexiti…