On Parallelism in Turing Machines
dc.contributor.author | Kozen, Dexter | en_US |
dc.date.accessioned | 2007-04-23T17:54:02Z | |
dc.date.available | 2007-04-23T17:54:02Z | |
dc.date.issued | 1976-06 | en_US |
dc.description.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. | en_US |
dc.format.extent | 1305342 bytes | |
dc.format.extent | 359142 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | application/postscript | |
dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-282 | en_US |
dc.identifier.uri | https://hdl.handle.net/1813/7056 | |
dc.language.iso | en_US | en_US |
dc.publisher | Cornell University | en_US |
dc.subject | computer science | en_US |
dc.subject | technical report | en_US |
dc.title | On Parallelism in Turing Machines | en_US |
dc.type | technical report | en_US |