\input zb-basic
\input zb-ioport
\iteman{io-port 02113949}
\itemau{Nishio, Hidenosuke; Saito, Takashi}
\itemti{Information dynamics of cellular automata. I: An algebraic study.}
\itemso{Fundam. Inform. 58, No. 3-4, 399-420 (2003).}
\itemab
Summary: 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 separate sections. Decision problems are also referred to.
\itemrv{~}
\itemcc{}
\itemut{polynomials over finite fields; dynamical system}
\itemli{}
\end