Conway's cosmological theorem and automata theory
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_ | 1866915628845105152 |
|---|---|
| author | Lairez, Pierre Storozhenko, Aleksandr |
| author_facet | Lairez, Pierre Storozhenko, Aleksandr |
| contents | John Conway proved that every audioactive sequence (a.k.a. look-and-say) decays into a compound of 94~elements, a statement he termed the cosmological theorem. The underlying audioactive process can be modeled by a finite-state machine, mapping one sequence of integers to another. Leveraging automata theory, we propose a new proof of Conway's theorem based on a few simple machines, using a computer to compose and minimize them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20341 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conway's cosmological theorem and automata theory Lairez, Pierre Storozhenko, Aleksandr Formal Languages and Automata Theory John Conway proved that every audioactive sequence (a.k.a. look-and-say) decays into a compound of 94~elements, a statement he termed the cosmological theorem. The underlying audioactive process can be modeled by a finite-state machine, mapping one sequence of integers to another. Leveraging automata theory, we propose a new proof of Conway's theorem based on a few simple machines, using a computer to compose and minimize them. |
| title | Conway's cosmological theorem and automata theory |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2409.20341 |