Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: On Parallelism in Turing Machines
Authors: Kozen, Dexter
Keywords: computer science
technical report
Issue Date: Jun-1976
Publisher: Cornell University
Abstract: A model of parallel computation based on a generalization of nondeterminism in Turing machines is introduced. Complexity classes //T(n)-TIME, //L(n)-SPACE, //LOGSPACE, //PTIME, etc. are defined for these machines in a way analogous to T(n)-TIME, L(n)-SPACE, LOGSPACE, PTIME, etc. for deterministic machines. It is shown that, given appropriate honesty conditions, 217z L(n)-SPACE $\subseteq$ //L$(n)^{2}$-TIME T(n)-TIME $\subseteq$ //log T(n)-SPACE //L(n)-SPACE $\subseteq$ exp L(n)-TIME //T(n)-TIME $\subseteq$ T$(n)^{2}$-SPACE thus //EXPTIME = EXPSPACE //PSPACE = EXPTIME //PTIME = PSPACE //LOGSPACE = PTIME ? = LOGSPACE That is, the deterministic hierarchy LOGSPACE $\subseteq$ PTIME $\subseteq$ PSPACE $\subseteq$ EXPTIME $\subseteq \ldots$ shifts by exactly one level when parallelism is introduced. We give a natural characterization of the polynomial time hierarchy of Stockmeyer and Meyer in terms of parallel machines. Analogous space hierarchies are defined and explored, and a generalization of Savitch's result NONDET-L(n)-SPACE $\subseteq$ L$(n)^{2}$-SPACE is given. Parallel finite automata are defined, and it is shown that, although they accept only regular sets, in general, $2^{2^{k}}$ states are necessary and sufficient to simulate a k-state parallel finite automaton deterministically.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
76-282.pdf1.27 MBAdobe PDFView/Open
76-282.ps350.72 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us