Evolution of Cellular Automata toward a LIFE-Like Rule Guided by 1/f Noise
There is evidence in favor of a relationship between the presence of 1/f noise and computational universality in cellular automata. To confirm the relationship, we search for two-dimensional cellular automata with a 1/f power spectrum by means of genetic algorithms. The power spectrum is calculated from the evolution of the state of the cell, starting from a random initial configuration. The fitness is estimated by the power spectrum with consideration of the spectral similarity to the 1/f spectrum. The result shows that the rule with the highest fitness over the most runs exhibits a 1/f type spectrum and its transition function and behavior are quite similar to those of the Game of Life, which is known to be a computationally universal cellular automaton. These results support the relationship between the presence of 1/f noise and computational universality.
1/f noise computational universality genetic algorithm cellular automaton