Evolution of Cellular Automata toward a LIFE-Like Rule Guided by 1/f Noise

Shigeru NINAGAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.6   pp.1489-1496
Publication Date: 2010/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1489
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
cellular automaton,  genetic algorithm,  computational universality,  1/f noise,  

Full Text: PDF>>
Buy this Article




Summary: 
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.