Complete Symmetry in D2l Systems and Cellular Automata

摘要

Completely symmetric D2L systems and cellular automata are introduced by means of an additional restriction on the corresponding classes of symmetric devices. It is shown that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries, characterizations of the recursively enumerable languages and of space-bounded complexity classes are obtained.