Computation in reversible cellular automata

Abstract

A reversible cellular automaton (RCA) is a subclass of a CA such that its global function is injective. It is considered as an abstract spatiotemporal model of a reversible physical system. In spite of the strong constraint of reversibility, an RCA has a high ability of information processing. In this survey, we overview the past studies on RCAs, and discuss how computing is performed in them. We can see even very simple RCAs have computation-universality.

Keywords:

• reversible cellular automaton
• reversible computing
• reversible Turing machine

Acknowledgements

This work was supported, in part, by JSPS Grant-in-Aid for Scientific Research (C) No. 21500015.