An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits (Q1108006): Difference between revisions

We present an improved simulation of space and reversal bounded Turing machines by width and depth bounded uniform circuits. (All resource bounds hold simultaneously.) An S(n) space, R(n) reversal bounded deterministic k-tape Turing machine can be simulated by a uniform circuit of \(O(R(n)\log^ 2 S(n))\) depth and \(O(S(n)^ k)\) width. Our proof is cleaner, and has slightly better resource bounds than the original proof due to \textit{N. Pippenger} [Proc. 20th Ann. IEEE Symp. Found. Comput. Sci., 307-311 (1979)]. The improvement in resource bounds comes primarily from the use of a shared-memory machine instead of an oblivious Turing machine, and the concept of a `special situation'.