Number-conserving cellular automata I: decidability

AbstractWe prove that definitions of number-conserving cellular automata found in literature are equivalent. A necessary and sufficient condition for cellular automata to be number-conserving is proved. Using this condition, we give a quasi-linear time algorithm to decide number-conservation