I do not know the details of rule 110 well-enough to know to say how hard the set of words that appear in periodic points (or the set of periodic points itself) is.
However, I think that here, "periodicity" refers to "eventual periodicity". Lead to periodicity in Rule 110’s behavior. Something quite similar is stated by Matthew Cook in his paper about its universality, let me quote his paper:Īs discussed in Section 2.3, given a fixed repeating pattern to the leftĪnd right, it is undecidable whether a given finite initial condition will Rule 110 is well-known to be Turing-complete, so it would not be surprising if it has this property. This can be shown by a pigeonhole argument. The set of words appearing in a temporally periodic configuration is recursively enumerable, since every word that appears in a temporally periodic point appears in a point that is temporally periodic and spatially eventually periodic in both directions. Hardness can be proved by simulating a universal Turing machine. I would guess that for rule 110 there is no simple description of the temporally periodic points, in a precise sense.įirst, there is no description of the periodic points for cellular automata in general: There exists a cellular automaton such that given a finite word, it is undecidable (more precisely $\Sigma^0_1$-complete) whether it appears in a temporally periodic configuration. Let me refer to your property as (temporal) periodicity, and to shift-periodicity as spatial periodicity.
0 kommentar(er)
