On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913934161739776 |
|---|---|
| author | Paturi, Katariina Kari, Jarkko |
| author_facet | Paturi, Katariina Kari, Jarkko |
| contents | Non-uniform cellular automata (NUCA) are an extension of cellular automata with multiple local rules in different cells. We show that if the distribution of local rules is uniformly recurrent, or recurrent in the one-dimensional case, the Garden of Eden theorem holds. We also show that for any non-recurrent distribution, there is a substitution of local rules that defines a NUCA which does not satisfy the Garden of Eden theorem. Finally, we show that a rule distribution asymptotic to recurrent distribution defines a surjunctive NUCA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06987 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata Paturi, Katariina Kari, Jarkko Dynamical Systems Non-uniform cellular automata (NUCA) are an extension of cellular automata with multiple local rules in different cells. We show that if the distribution of local rules is uniformly recurrent, or recurrent in the one-dimensional case, the Garden of Eden theorem holds. We also show that for any non-recurrent distribution, there is a substitution of local rules that defines a NUCA which does not satisfy the Garden of Eden theorem. Finally, we show that a rule distribution asymptotic to recurrent distribution defines a surjunctive NUCA. |
| title | On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata |
| topic | Dynamical Systems |
| url | https://arxiv.org/abs/2507.06987 |