Simulation Limitations of Affine Cellular Automata
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914791302365184 |
|---|---|
| author | Hudcová, Barbora Krásenský, Jakub |
| author_facet | Hudcová, Barbora Krásenský, Jakub |
| contents | Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA relative simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B.
We study affine automata - i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of additive automata. The main result of this paper shows that (almost) every automaton affine over a finite field F_p can only simulate affine automata over F_p. We discuss how this general result implies, and widely surpasses, limitations of additive automata previously proved in the literature.
We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_14477 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Simulation Limitations of Affine Cellular Automata Hudcová, Barbora Krásenský, Jakub Formal Languages and Automata Theory Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA relative simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B. We study affine automata - i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of additive automata. The main result of this paper shows that (almost) every automaton affine over a finite field F_p can only simulate affine automata over F_p. We discuss how this general result implies, and widely surpasses, limitations of additive automata previously proved in the literature. We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems. |
| title | Simulation Limitations of Affine Cellular Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2311.14477 |