Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


[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 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^n 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 next note.)


From Stephen Wolfram: A New Kind of Science [citation]