Computing the configuration of any one-dimensional cellular automaton at generation n can be accelerated by constructing and running a composite rule with a radius proportional to log n. The new automaton is the original one, but with its local rule function composed with itself. Consequently, the asymptotic time complexity to compute the configuration of generation n is reduced from O(n2)-time to O(n2/logn)but with O(n2/(logn)3)-space, demonstrating a time-memory tradeoff. Experimental results are given in the case of rule 30.
Natal et al. (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: