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.
