Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata

Solène J. Esnay, Alonso Núñez, Ilkka Törmä

correctmedium confidence

Category: Not specified
Journal tier: Strong Field
Processed: Sep 28, 2025, 12:56 AM
arXiv Links: Abstract ↗PDF ↗

Audit review

The candidate solution reproduces Theorem 7.1 of Esnay–Núñez–Törmä using the same walls-and-counters segmentation, computable mixing SFT scaffolding (Z_m, and when needed Y_m), enabling/forcing characterizations, conveyor-belt periodic words, and computable gluing in mixing SFTs. The paper states and proves exactly this realization for chain-mixing subshifts in the two effective cases and ensures f|_X = σ|_X (Theorem 7.1; auxiliary Lemmas 3.1–3.3, 7.2–7.3, 7.6) . Minor phrasing differences (e.g., claiming the empty cylinder enables all s ∈ L(X)) do not change the substance.

Referee report (LaTeX)

\textbf{Recommendation:} minor revisions

\textbf{Journal Tier:} strong field

\textbf{Justification:}

Technically solid adaptation of walls-and-counters to the generic-limit setting with clear effective scaffolding for the two key arithmetical cases. The work meaningfully advances realizability/complexity frontiers for generic limit sets under strong dynamical constraints. Minor improvements in exposition (layer diagrams, explicit algorithm boxes, and some cross-referencing) would further enhance readability.