Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant

Hao Ke

Preprint ·

Abstract

Fix a number of initially black cells and a target number of departures from the standard Langton highway. Which placements of those cells make the ant reach that target? We count a departure whenever ten consecutive turns form a word absent from the standard 104-turn cycle. For each supplied pair of integers m, N, we prove that the placements of exactly m black cells producing at least N such departures form an effectively computable semilinear set: a finite union of integer translates of finitely generated additive monoids. Initial coordinates are unrestricted. The construction also describes the exact time, pose and entire black field just after the Nth departure. The key reduction represents the intervening legal motion by a finite collection of words with variable repetition counts. Consecutive visits to each cell enforce the ant’s read-and-flip rule throughout these compressed traces. This yields decidable synthesis under integer-linear coordinate constraints and piecewise rational-affine resource formulas for supplied word families. Positive instances have polynomial-bit witnesses when m, N are written in unary. A restricted quantifier-free encoding makes the spatial read/write tests polynomial in the supplied description size. Together these results turn finite departure targets into exact arithmetic questions about complete ant states.

Citation

Hao Ke (2026). Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant. Zenodo. 10.5281/zenodo.23675966

@misc{ke2026langtonsantdefectsynthesis,
  author = {Hao Ke},
  title = {{Counting Defects: Semilinear Reachability and Resource Bounds for Langton's Ant}},
  year = {2026},
  doi = {10.5281/zenodo.23675966},
  url = {https://doi.org/10.5281/zenodo.23675966},
  note = {Preprint, version 0.1.1}
}

CC BY 4.0.