![Complex Systems Complex Systems](https://www.complex-systems.com/wp-content/themes/complexsystems/img/ui_logo_small.png)
On Invertible Cellular Automata
Karel Culik II
Department of Computer Science, University of South Carolina,
Columbia, SC 29208, USA
Abstract
The problem of testing whether a given cellular automaton rule has an inverse was stated by Toffoli and Margolus. This problem is equivalent to the invertibility of the given CA-rule (injectivity of the global function it defines). It is decidable for one-dimensional cellular automata and open for higher dimensions. We show some related results and give automata-theoretic proofs of some known results.