Solving the Parity Problem with Rule 60 in Array Size of the Power of Two
Shigeru Ninagawa
In the parity problem, a given cellular automaton has to classify any initial configuration into two classes according to its parity. Elementary cellular automaton rule 60 can solve the parity problem in periodic boundary conditions with array size of the power of two. The spectral analysis of the configurations of rule 60 at each time step in the evolution reveals that spatial periodicity emerges as the evolution proceeds and the patterns with longer period split into the ones with shorter period. This phenomenon is analogous to the cascade process in which large scale eddies split into smaller ones in turbulence. By measuring the Lempel-Ziv complexity of configuration, we found the stepping decrease of the complexity during the evolution. This result might imply that a decision problem solving process is accompanied with the decline of complexity of configuration.
Keywords: Parity problem, cascade process, Lempel-Ziv complexity, decision problem