Finite-Memory Prediction and Remote Feedback in Langton’s Ant

Hao Ke

Preprint ·

Abstract

A Langton ant can encounter a black cell long after it last visited that location. How far can its future be predicted from only its last D turns, and how can the prediction resume after such an encounter? We call a black read old when the cell was absent from the preceding D visits. From any complete finite initial state, we compute the next old-black read, or certify that none occurs. For fixed D, the algorithm is polynomial in the sparse binary input size. It also returns the complete resulting black field, using finite arithmetic segments to represent all skipped writes exactly. Geometric bounds make the time to n events at most quadratic in n, with constants depending on D and the initial spatial extent. They also allow queries restricted to events outside a given finite region. Any orbit that never settles into a periodically translating trace must repeatedly read back black cells created arbitrarily late, left unread arbitrarily long, and consumed arbitrarily far away; all three properties hold for the same cell lifetimes. Finally, a family of twenty-black inputs has unbounded feedback lifetimes with exactly 31 intervening old-black reads at D = 128. This explains why spatial extent is essential in uniform lifetime bounds.

Citation

Hao Ke (2026). Finite-Memory Prediction and Remote Feedback in Langton’s Ant. Zenodo. 10.5281/zenodo.23675969

@misc{ke2026langtonsantmemoryfeedback,
  author = {Hao Ke},
  title = {{Finite-Memory Prediction and Remote Feedback in Langton’s Ant}},
  year = {2026},
  doi = {10.5281/zenodo.23675969},
  url = {https://doi.org/10.5281/zenodo.23675969},
  note = {Preprint, version 0.1.1}
}

CC BY 4.0.