Some Results on Invertible Cellular Automata
A. Clementi
Department of Computer Science, Università di Roma "La Sapienza'', Italy
P. Mentrasti
Department of Mathematics, Università di Roma "La Sapienza'', Italy
P. Pierini
MIT Laboratory for Computer Science, Cambridge, MA, USA
Abstract
We address certain questions concerning invertible cellular automata (ICA), and present new results in this area. Specifically, we explicitly construct a cellular automaton (CA) in a class (residual class) previously known not to be empty only via a nonconstructive existence proof. This class contains CAs that are invertible on every finite support but not on an infinite lattice. Moreover, we show a class that contains ICAs having bounded neighborhood, but whose inverses constitute a class of CAs for which there is no recursive function bounding all the neighborhoods.
