eCommons

 

On Parallelism in Turing Machines

dc.contributor.authorKozen, Dexteren_US
dc.date.accessioned2007-04-23T17:54:02Z
dc.date.available2007-04-23T17:54:02Z
dc.date.issued1976-06en_US
dc.description.abstractA 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.extent1305342 bytes
dc.format.extent359142 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR76-282en_US
dc.identifier.urihttps://hdl.handle.net/1813/7056
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleOn Parallelism in Turing Machinesen_US
dc.typetechnical reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
76-282.pdf
Size:
1.24 MB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
76-282.ps
Size:
350.72 KB
Format:
Postscript Files