The Surjunctivity Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G$ be a group and let $A$ be a nonempty finite set, called an alphabet. A configuration is a function $x:G\to A$; the set of all configurations is $A^G$. A cellular automaton is a map $\tau:A^G\to A^G$ for which there are a finite set $M\subseteq G$ and a local rule $\mu:A^M\to A$ satisfying \[ \tau(x)(g)=\mu\left((x(gm))_{m\in M}\right) \quad (x\in A^G,\ g\in G). \] Thus the same finite local rule applies at every group element. The group $G$ is surjunctive if every such injective map is surjective, for every nonempty finite alphabet.

Statement recorded in the supplied source.

Is every group $G$ surjunctive? Explicitly, for every group $G$, every nonempty finite alphabet $A$, every finite memory set $M\subseteq G$, and every local rule $\mu:A^M\to A$, is the associated map $\tau:A^G\to A^G$ surjective whenever it is injective? [S2]

Short English statement

Does every injective cellular automaton on every group, with any finite alphabet, also reach every configuration?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1196 (ALG-032). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Lewis Bowen and Michael Chapman, Surjunctivity does not characterize cosoficity of invariant random subgroups, arXiv:2511.06586 (2025), abstract and Section 1. https://arxiv.org/abs/2511.06586.