Atomic Gliders and Cellular Automata as Language Generators
Dana Fisman and Noa Izsak · 2025
Read Atomic Gliders and Cellular Automata as Language Generators by Dana Fisman and Noa Izsak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12656.txt.
Description
Dana Fisman and Noa Izsak ask what languages cellular automata can generate. Cellular automata are grids of cells that update in lockstep from simple local rules, and they are famous for producing rich behavior from plain beginnings. Earlier work mostly simulated their dynamics; this paper treats them formally as language generators. The languages collect finite words read from the active parts of configurations that a one-dimensional automaton can reach from regular starting patterns.
To capture structured motion, the authors define gliders as one-cell carriers that move at a fixed velocity and interact under set rules. They then prove a surprise: even with regular starting patterns and local rules, the generated languages can be non-regular and even non-context-free. That makes these automata a richer computing model than their simple rules suggest, with possible uses in checking systems of many ordered agents.
Catalog record
| CREATOR | Dana Fisman and Noa Izsak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 203 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-12656