On Gottschalk's surjunctivity conjecture for non-uniform cellular automata
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910052101652480 |
|---|---|
| author | Phung, Xuan Kien |
| author_facet | Phung, Xuan Kien |
| contents | Gottschalk's surjunctivity conjecture for a group $G$ states that it is impossible for cellular automata (CA) over the universe $G$ with finite alphabet to produce strict embeddings of the full shift into itself. A group universe $G$ satisfying Gottschalk's surjunctivity conjecture is called a surjunctive group. The surjunctivity theorem of Gromov and Weiss shows that every sofic group is surjunctive. In this paper, we study the surjunctivity of local perturbations of CA and more generally of non-uniform cellular automata (NUCA) with finite memory and uniformly bounded singularity over surjunctive group universes. In particular, we show that such a NUCA must be invertible whenever it is reversible. We also obtain similar results which extend to the class of NUCA a certain dual-surjunctivity theorem of Capobianco, Kari, and Taati for CA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23435 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Gottschalk's surjunctivity conjecture for non-uniform cellular automata Phung, Xuan Kien Dynamical Systems Discrete Mathematics Group Theory Cellular Automata and Lattice Gases Gottschalk's surjunctivity conjecture for a group $G$ states that it is impossible for cellular automata (CA) over the universe $G$ with finite alphabet to produce strict embeddings of the full shift into itself. A group universe $G$ satisfying Gottschalk's surjunctivity conjecture is called a surjunctive group. The surjunctivity theorem of Gromov and Weiss shows that every sofic group is surjunctive. In this paper, we study the surjunctivity of local perturbations of CA and more generally of non-uniform cellular automata (NUCA) with finite memory and uniformly bounded singularity over surjunctive group universes. In particular, we show that such a NUCA must be invertible whenever it is reversible. We also obtain similar results which extend to the class of NUCA a certain dual-surjunctivity theorem of Capobianco, Kari, and Taati for CA. |
| title | On Gottschalk's surjunctivity conjecture for non-uniform cellular automata |
| topic | Dynamical Systems Discrete Mathematics Group Theory Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2503.23435 |