LANGUAGE CLASSES DEFINED BY TIME-BOUNDED RELATIVIZED CELLULAR-AUTOMATA

Some of the fundamental problems concerning cellular automata (CA) are as follows: Are linear-time CA (l CA) more powerful than real-time CA (r CA)? Are nonlinear-time CA more powerful than linear-time CA ? Does one-way communication reduce the power of a CA ? These question have been open for a long time. In this paper, we address these questions with respect to tally languages in relativised worlds, interpreting timevarying CA (TVCA) as oracle machines. We construct oracles which separate r CA from l CA and l CA from CA, oracle classes under which the CA classes coincide, and oracles which leave the CA classes unchanged. Further, with r CA and l CA at the base, we build a hierarchy of relativised CA complexity classes between r CA and CA, and study the dependencies between the classes in this hierarchy.