JCA HomeIssue Contents

A Characterization of von Neumann Neighbor Number-Conserving Cellular Automata
Naonori Tanimoto and Katsunobu Imai

A number-conserving cellular automaton (NCCA) is a cellular automaton such that all states of cells are represented by integers and the total number of its configuration is conserved throughout its computing process. In this paper, we show necessary and sufficient conditions for a two-dimensional von Neumann neighbor CA with and without rotation-symmetry to be number-conserved. According to these conditions, the local function of a rotation-symmetric NCCA is represented by summation of two binary functions. Then we show a construction method based on the representation. As a result, we construct a smaller state logically universal NCCA with rotation-symmetry than the ±45-degree reflection-symmetric one.

Full Text (IP)