Information Dynamics of Cellular Automata I – An Algebraic Study

Issue title: Cellular Automata

Article type: Research Article

Authors: Nishio, Hidenosuke | Saito, Takashi

Affiliations: Iwakura Miyake-cho 204, Sakyo-ku, Kyoto 606-0022, Japan | Faculty of Information Science and Technology Osaka Institute of Technology, Osaka 573-0196, Japan

Abstract: Information dynamics of cellular automata(CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate X called information variable and its dynamics is investigated by extending CA to CA[X] whose cell states are polynomials in X. For the global configuration of extended CA[X], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[X] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in the separate sections. Decision problems are also referred.

Keywords: cellular automaton, polynomials over finite fields, dynamical system, completeness, degeneracy, reversibility

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 399-420, 2003