On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata
Katariina Paturi, Jarkko Kari · 2025
Read On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata by Katariina Paturi, Jarkko Kari (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-2507-06987.txt.
Description
Katariina Paturi and Jarkko Kari prove a Garden of Eden theorem for uneven cellular automata in a 2025 paper. Classic automata apply one rule everywhere. Non uniform versions let different cells follow different rules, which raises basic questions about when unreachable patterns must exist.
The answer turns on how the rule pattern repeats. If the layout of rules is uniformly recurrent, or simply recurrent on a line, the theorem holds: some configurations can never be reached. For any non recurrent layout, the authors construct a rule choice that breaks the theorem. Layouts that merely approach a recurrent one still give surjunctive automata, which cannot compress their state space. The results map exactly where the classic guarantees survive uneven rules.
Catalog record
| CREATOR | Katariina Paturi, Jarkko Kari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-06987