[Intractability in] systems of limited size

In the system x  Mod[x + m, n] from page 255 the repetition period n/GCD[m, n] can be computed using Euclid's algorithm in at most about Log[GoldenRatio, n] steps. In the system x  Mod[2x, n] from page 257, the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps. (But see the next note.) In a cellular automaton with n cells, the problem of finding the repetition period is in general PSPACE-complete—as follows from the possibility of universality in the underlying cellular automaton. And even in a case like rule 30 I suspect that the period cannot be found much faster than by tracing nearly 2ⁿ steps of evolution. (I know of no way for example to break the computation into parts that can be done in parallel.) With sufficiently simple behavior, a cellular automaton repetition period can readily be determined in some power of Log[n] steps. But even with an additive rule and nested behavior, the period depends on quantities like MultiplicativeOrder[2, n], which probably take more like n steps to evaluate. (But see the next note.)