Sparse Initial Conditions and the Trace Space of Langton's Ant
How many different observations can an ant with at most m initially black cells produce in its first n updates, when the cell coordinates are unrestricted? We prove that the number of anchored turn prefixes is Θ_m(n^m) for every fixed m. The upper bound encodes a history by the times of its first black reads. The matching lower exponent is realized by a protected single-cell scattering channel, repeated with complete history retained. Every input in this lower-bound family ultimately follows the standard highway. For infinite streams, the countable compact trace spaces obey the exact derived-set identity Tr_m′ = Tr_(m−1): their Cantor–Bendixson rank is m + 1. An explicit compact subfamily of eventually standard streams has the same rank and prefix exponent. We also determine the optimal passive prediction mistake budget to be m. These results classify sparse-source observation complexity uniformly over unrestricted initial coordinates, transient times and future geometries.
Authors
- Ke Hao (ORCID: https://orcid.org/0009-0001-2818-4986)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-31
- DOI
- https://doi.org/10.5281/zenodo.23838432
- Primary Topic
- Cellular Automata and Applications
- Type
- preprint