On reversibility in cellular automata

摘要

The notion of reversibility, or backward determinism, for cellular automata is investigated. Various intuitively different definitions are offered which coalesce in three inequivalent properties. Two of these are the well-known injectivity and surjectivity properties of the global transition function of a cellular automaton. We complete the investigation for one-dimensional cellular automata giving effective conditions for the third property. We end with some examples and comments on the relations between local and global phaenomena in cellular automata.