(Proof: The $p$-periodic points form a subshift of finite type. In the case of rule 90, there is a simple algebraic description of temporally periodic points.įirst, rule 90 is positively expansive, so it can have only finitely many temporally periodic points for each period. 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 Comments
Leave a Reply. |