Narrow Results

Fix a group G and let X be an algebraic variety over an algebraically closed field k of characteristic zero. We investigate the invertibility of algebraic cellular automata, namely, G-equivariant uniformly continuous self-maps whose local defining maps are induced by morphisms of algebraic varieties $X^M\to X$ where $M\subset G$ is a finite memory set. When G is locally embeddable into finite groups (LEF), we show that the inverses of reversible algebraic cellular automata are automatically algebraic cellular automata and thus computable in polynomial time. Generalizations are also obtained for finite product Hopfian pointed object alphabets in concrete categories. Moreover, we prove that for algebraic cellular automata, the notions of reversibility and injectivity are equivalent whenever G is surjunctive and the field k is, additionally, uncountable of arbitrary characteristic.