Hard Asymptotic Sets for One-Dimensional Cellular Automata
classification
💻 cs.CC
cs.FLmath.DS
keywords
asymptoticcellularhardone-dimensionalautomataautomatonconstructionsdetail
read the original abstract
We prove that the (language of the) asymptotic set (and the nonwandering set) of a one-dimensional cellular automaton can be $\SIGMA^1_1$-hard. We do not go into much detail, since the constructions are relatively standard.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.