Complete symmetry in d2l systems and cellular automata

Abstract

We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding classes of symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.

Keywords:

• D2L system
• cellular automaton
• symmetry
• r.e. language
• space-bounded complexity class

C.R. Categories:

• F.4.3
• F.1.1
• F.1.3