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

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.