Generically Nilpotent Cellular Automata

Abstract

We study the generic limit sets of one-dimensional cellular automata, which intuitively capture their asymptotic dynamics while discarding transient phenomena. As our main results, we characterize the automata whose generic limit set is a singleton, and show that this class is ${\Sigma }_2^0$-complete. We also prove that given a CA whose generic limit set is guaranteed to be a singleton, the sole configuration it contains cannot be algorithmically determined.

14 pages, 2 figures

References in corpus (2)

• On Nilpotency and Asymptotic Nilpotency of Cellular Automata
• Construction of $\mu$-Limit Sets