# Parallel turing machines with one-head control units and cellular automata

Worsch, Thomas

##### Abstract:

Parallel Turing machines (PTM) can be viewed as a generalization of
cellular automata (CA) where an additional measure called processor
complexity can be defined which indicates the amount of
parallelism'' used. In this paper PTM are investigated with respect to
their power as recognizers of formal languages. A combinatorial
approach as well as diagonalization are used to obtain hierarchies of
complexity classes for PTM and CA. In some cases it is possible to
keep the space complexity of PTM fixed. Thus for the first time it is
possible to find hierarchies of complexity classes (though not CA
classes) which are completely contained in the class of languages
recognizable by CA with space complexity n and in polynomial time. A
possible collapse of the time hierarchy for these CA would therefore
also imply some unexpected properties of PTM.

 Zugehörige Institution(en) am KIT Fakultät für Informatik – Informatik für Ingenieure und Naturwissenschaftler (Inf. für Ing. u. Naturwiss.) Publikationstyp Buch Publikationsjahr 1997 Sprache Englisch Identifikator urn:nbn:de:swb:90-AAA42970 KITopen-ID: 4297 Erscheinungsvermerk Karlsruhe 1997. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1997,3.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page