Descriptional Complexity of Cellular Automata and Decidability Questions

We study the descriptional complexity of cellular automata (CA) which are a parallel model of computation. We show that between one of the simplest cellular models, the realtime one-way CA (realtime-OCA), and "classical" models like deterministic finite automata or pushdown automata, there will be savings concerning the size of description not bounded by any recursive function, so-called nonrecursive trade-offs. Furthermore, nonrecursive trade-offs are shown to exist between certain restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtime-OCA. This implies that many decidability questions are not even semidecidable for cellular automata. There is no pumping lemma and no minimization algorithm for cellular automata. Finally, we prove that the language class accepted by realtime-OCA is incomparable to many known and well-investigated language classes.