Fast Simulation of Turing Machines by Random Access Machines
SIAM Journal on Computing1988Vol. 17(1), pp. 77–88
Citations Over TimeTop 10% of 1988 papers
Abstract
We prove that a $T(n)$ time-bounded, $S(n)$ space-bounded and $U(n)$ output-length-bounded Turing machine can be simulated in $O(T(n) + (n + U(n))\log \log S(n))$ time by a random access machine (with no multiplication or division instructions) under the logarithmic cost criterion.