Complex Systems

Power Spectral Analysis of Elementary Cellular Automata Download PDF

Shigeru Ninagawa
Electronic mail address: ninagawa@infor.kanazawa-it.ac.jp
Division of Information and Computer Science,
Kanazawa Institute of Technology,
7-1 Ohgigaoka, Nonoichi, Ishikawa 921-8501, Japan

Abstract

Spectral analysis of elementary cellular automata is performed. A power spectrum is calculated from the evolution of 88 independent rules starting from random initial configurations. As a result, it is found that rule 110 exhibits 1/f noise during the longest time steps. Rule 110 has proved to be capable of supporting universal computation. These results suggest that there is a relationship between computational universality and 1/f noise in cellular automata.