On elementary cellular automata asymptotic (a)synchronism sensitivity and complexity
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_ | 1866914710425698304 |
|---|---|
| author | Leiva, Isabel Donoso Goles, Eric Ríos-Wilson, Martín Sené, Sylvain |
| author_facet | Leiva, Isabel Donoso Goles, Eric Ríos-Wilson, Martín Sené, Sylvain |
| contents | Among the fundamental questions in computer science is that of the impact of synchronism/asynchronism on computations, which has been addressed in various fields of the discipline: in programming, in networking, in concurrence theory, in artificial learning, etc. In this paper, we tackle this question from a standpoint which mixes discrete dynamical system theory and computational complexity, by highlighting that the chosen way of making local computations can have a drastic influence on the performed global computation itself. To do so, we study how distinct update schedules may fundamentally change the asymptotic behaviors of finite dynamical systems, by analyzing in particular their limit cycle maximal period. For the message itself to be general and impacting enough, we choose to focus on a ``simple'' computational model which prevents underlying systems from having too many intrinsic degrees of freedom, namely elementary cellular automata. More precisely, for elementary cellular automata rules which are neither too simple nor too complex (the problem should be meaningless for both), we show that update schedule changes can lead to significant computational complexity jumps (from constant to superpolynomial ones) in terms of their temporal asymptotes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15078 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On elementary cellular automata asymptotic (a)synchronism sensitivity and complexity Leiva, Isabel Donoso Goles, Eric Ríos-Wilson, Martín Sené, Sylvain Cellular Automata and Lattice Gases Discrete Mathematics Dynamical Systems Among the fundamental questions in computer science is that of the impact of synchronism/asynchronism on computations, which has been addressed in various fields of the discipline: in programming, in networking, in concurrence theory, in artificial learning, etc. In this paper, we tackle this question from a standpoint which mixes discrete dynamical system theory and computational complexity, by highlighting that the chosen way of making local computations can have a drastic influence on the performed global computation itself. To do so, we study how distinct update schedules may fundamentally change the asymptotic behaviors of finite dynamical systems, by analyzing in particular their limit cycle maximal period. For the message itself to be general and impacting enough, we choose to focus on a ``simple'' computational model which prevents underlying systems from having too many intrinsic degrees of freedom, namely elementary cellular automata. More precisely, for elementary cellular automata rules which are neither too simple nor too complex (the problem should be meaningless for both), we show that update schedule changes can lead to significant computational complexity jumps (from constant to superpolynomial ones) in terms of their temporal asymptotes. |
| title | On elementary cellular automata asymptotic (a)synchronism sensitivity and complexity |
| topic | Cellular Automata and Lattice Gases Discrete Mathematics Dynamical Systems |
| url | https://arxiv.org/abs/2312.15078 |