On Universality of Radius 1/2 Number-Conserving Cellular Automata

摘要

A number-conserving cellular automaton (NCCA) is a cellular automaton whose states are integers and whose transition function keeps the sum of all cells constant throughout its evolution. It can be seen as a kind of modeling of the physical conservation laws of mass or energy. In this paper we show a construction method of radius 1/2 NCCAs. The local transition function is expressed via a single unary function which can be regarded as 'flows' of numbers. In spite of the strong constraint, we constructed radius 1/2 NCCAs that simulate any radius 1/2 cellular automata or any radius 1 NCCA. We also consider the state complexity of these non-splitting simulations (4n~2 + 2n + 1 and 8n~2 + 12n - 16, respectively). These results also imply existence of an intrinsically universal radius 1/2 NCCA.