An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits (Q1108006)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits |
scientific article |
Statements
An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits (English)
0 references
1987
0 references
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'.
0 references
NC
0 references
extended parallel computation thesis
0 references
reduction to sorting
0 references
simultaneous resource bounds
0 references
reversal
0 references
deterministic k-tape Turing machine
0 references
uniform circuit
0 references
shared-memory machine
0 references