Measuring the Computational Power of Finite Patches of Cellular Automata
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917413745852416 |
|---|---|
| author | Egri-Nagy, Attila Nehaniv, Chrystopher L. |
| author_facet | Egri-Nagy, Attila Nehaniv, Chrystopher L. |
| contents | Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation semigroup. The conversion captures not only time evolution but also interactive operations. In this way, the cellular automaton becomes directly programmable. Once this measurement is made, we apply hierarchical decompositions to the resulting algebraic object as a way of understanding it. These decompositions are based on a macro/micro-state division inspired by statistical mechanics. However, cellular automata have a large number of global states. Therefore, we focus on partitioning the state space and creating morphic images approximations that can serve as macro-level descriptions. The methods developed here are not limited to cellular automata; they apply more generally to discrete dynamical systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14966 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Measuring the Computational Power of Finite Patches of Cellular Automata Egri-Nagy, Attila Nehaniv, Chrystopher L. Cellular Automata and Lattice Gases Formal Languages and Automata Theory 20M20, 20M35 Computational power can be measured by assigning an algebraic structure to a computational device. Here, we convert a small patch of Conway's Game of Life into a transformation semigroup. The conversion captures not only time evolution but also interactive operations. In this way, the cellular automaton becomes directly programmable. Once this measurement is made, we apply hierarchical decompositions to the resulting algebraic object as a way of understanding it. These decompositions are based on a macro/micro-state division inspired by statistical mechanics. However, cellular automata have a large number of global states. Therefore, we focus on partitioning the state space and creating morphic images approximations that can serve as macro-level descriptions. The methods developed here are not limited to cellular automata; they apply more generally to discrete dynamical systems. |
| title | Measuring the Computational Power of Finite Patches of Cellular Automata |
| topic | Cellular Automata and Lattice Gases Formal Languages and Automata Theory 20M20, 20M35 |
| url | https://arxiv.org/abs/2604.14966 |