Networks of Binary Necklaces Induced by Elementary Cellular Automata Rules
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914941642997760 |
|---|---|
| author | Frati, Lapo Petak, Csenge Cheney, Nick |
| author_facet | Frati, Lapo Petak, Csenge Cheney, Nick |
| contents | Elementary cellular automata deterministically map a binary sequence to another using simple local rules. Visualizing the structure of this mapping is difficult because the number of nodes (i.e. possible binary sequences) grows exponentially. If periodic boundary conditions are used, rotation of a sequence and rule application to that sequence commute. This allows us to recover the rotational invariance property of loops and to reduce the number of nodes by only considering binary necklaces, the equivalence class of n-character strings taking all rotations as equivalent. Combining together many equivalent histories reveals the general structure of the rule, both visually and computationally. In this work, we investigate the structure of necklace-networks induced by the 256 Elementary Cellular Automata rules and show how their network structure change as the length of necklaces grow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04780 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Networks of Binary Necklaces Induced by Elementary Cellular Automata Rules Frati, Lapo Petak, Csenge Cheney, Nick Cellular Automata and Lattice Gases Elementary cellular automata deterministically map a binary sequence to another using simple local rules. Visualizing the structure of this mapping is difficult because the number of nodes (i.e. possible binary sequences) grows exponentially. If periodic boundary conditions are used, rotation of a sequence and rule application to that sequence commute. This allows us to recover the rotational invariance property of loops and to reduce the number of nodes by only considering binary necklaces, the equivalence class of n-character strings taking all rotations as equivalent. Combining together many equivalent histories reveals the general structure of the rule, both visually and computationally. In this work, we investigate the structure of necklace-networks induced by the 256 Elementary Cellular Automata rules and show how their network structure change as the length of necklaces grow. |
| title | Networks of Binary Necklaces Induced by Elementary Cellular Automata Rules |
| topic | Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2409.04780 |