Stable cellular-automaton limit sets

Definitions and mathematical statement

Let $A$ be a finite nonempty alphabet. A one-dimensional cellular automaton is a continuous map $F:A^{\mathbb Z}\to A^{\mathbb Z}$ commuting with the left shift. Equivalently, some radius $r\ge0$ and local rule $\varphi:A^{2r+1}\to A$ satisfy $(Fx)_j=\varphi(x_{j-r},\ldots,x_{j+r})$ at every site. The decreasing sequence of compact images defines its limit set \[ \Omega(F)=\bigcap_{n\ge0}F^n(A^{\mathbb Z}). \] The limit set is stable if there is a finite $k\ge0$ with $F^k(A^{\mathbb Z})=F^{k+1}(A^{\mathbb Z})$; then this common image equals $\Omega(F)$.

Characterize the subshifts which arise as stable limit sets of such automata. One formulation is to give necessary and sufficient conditions on $Y\subset A^{\mathbb Z}$ for the existence of a finite-window rule $F$ and a finite stabilization time $k$ with $F^k(A^{\mathbb Z})=Y$. The corresponding formulation up to shift conjugacy allows a finite recoding of the target alphabet.

Every finite-time image is a sofic shift, since it is a factor of a full shift; thus the problem lies within the finite labelled-graph class. The classification must identify which such spaces admit a surjective dynamics induced by a local rule on the surrounding full shift, with all configurations reaching the image in a uniform finite time. Pointwise eventual approach alone is not stability.

Short English statement

Which symbolic spaces are reached, in a uniformly bounded number of steps, as the final image of a cellular automaton?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600022 (AMR-045-0022), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Boyle - Open Problems in Symbolic Dynamics (2008), Problem/Question/Conjecture 16.1. Original source indexed by AMR-045-0022. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.