2024/09/30 by Lairez, Pierre, Storozhenko, Aleksandr · 1 voice
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2409.20341
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.