Jarkko KARI


Jonathan MILLS

James M. NYCE


Gabriela QUEIROZ


Philip WELCH

Cellular Automata

Abstract. Cellular automata are examples of discrete complex systems where non-trivial global behavior emerges from the local interaction of trivial components. Cellular automata have been studied, among other perspectives, as models of massively parallel computation tightly connected to the microscopic physics. Physics is time reversible and satisfies various conservation laws, and by a careful design these properties can be implemented in cellular automata as well. The concept of time reversibility is important in this context, as irreversible logical operations such as AND and OR are ''wasteful'' and necessarily lead to dissipation of energy.  It is well known that simple cellular automata rules can be computationally universal, and universal cellular automata exist even under the additional constraints of reversibility and conservation laws. In this talk we discuss computational universality in (reversible) cellular automata and the connection to reversible logic. We demonstrate how any globally reversible cellular automaton can be implemented using locally reversible logical gates. We also present related undecidablity results.