An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
type: Item
instance of: scholarly article
title: An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
zbMATH Open document ID: 0653.68040
DOI: 10.1016/0020-0190(87)90112-8
author: Ian Parberry
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: 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'.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4066334
zbMATH Keywords: NC
zbMATH Keywords: extended parallel computation thesis
zbMATH Keywords: reduction to sorting
zbMATH Keywords: simultaneous resource bounds
zbMATH Keywords: reversal
zbMATH Keywords: deterministic k-tape Turing machine
zbMATH Keywords: uniform circuit
zbMATH Keywords: shared-memory machine
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90112-8
OpenAlex ID: W2149100697
cites work: Q4773298
cites work: Sorting in \(c \log n\) parallel steps
cites work: On the Number of Stable States in a NOR Network
cites work: On Relating Time and Space to Size and Depth
cites work: Q3730022
cites work: Parallelism in random access machines
cites work: An Efficient General-Purpose Parallel Computer
cites work: A universal interconnection pattern for parallel computers
cites work: Parallel permutation and sorting algorithms and a new generalized connection network
cites work: Q3484350
cites work: Q3677183
cites work: Some practical simulations of impractical parallel computers
cites work: On uniform circuit complexity
cites work: Ultracomputers
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Implementation of simultaneous memory address access in models that forbid it
cites work: A parallel-design distributed-implementation (PDDI) general-purpose computer
Recommended article: Q3719832
Recommended article: On efficient deterministic simulation of turing machine computations below logaspace
Recommended article: Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines
Recommended article: Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
Recommended article: Improved Simulation of Nondeterministic Turing Machines
Recommended article: Improved simulation of nondeterministic Turing machines
Recommended article: Deterministic simulation of non-deterministic turing machines (Detailed Abstract)
Recommended article: Reversible simulation of space-bounded computations
Recommended article: Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
Recommended article: On reversal bounded alternating Turing machines
description: scientific article; zbMATH DE number 4066334