Periodicity of temporal sequences

Among the global behavioral implications of rules possessing particular deterministic structures, are those having to do with the periodicity of temporal sequences. 

Theorem 1 Let t be an elementary CA rule belonging either to deterministic structure type (1) (see table 5.1) with 100 —t 04 = 1 or type (2) with 001 ai = 1. Then, with arbitrary finite initial states, there can exist at most one periodic sequence. 

Proof First, it is easy to show that if (Ti t) and (Tj t) are two periodic sequences with i j, then the sequence ak t) must also be periodic ior i k j. In particular, aj-i t) is periodic. Suppose now that (f is of class (1). Then since aj+i t) is determined by (Tj t), aj-i t), and aj t + 1), the periodicity of (Tj t) and (7j i(t) implies the periodicity of (7j+i(t). Moreover, by induction, all sequences to the right of the j site, (7j+ (t), n 0, must also be periodic with the same T = max(T,-,Tj- i) and s =lcm [sj,Sj- ). Given that we start with finite initial conditions and the fact that 04 = 0, however, implies that there exists some N such that (i) Uj+t t) = 0 for some T t T + s and (ii) aj+i f T + m) — 1 for some m s. By contradiction, we conclude that there cannot exist two periodic temporal sequences of any period. The same conclusion is reached for rules of type 

---