0
$\begingroup$

Let's consider the class $CA$ of cellular automata where a cell is thought to exist in the $2$-dimensional grid ${\bf Z}\times{\bf Z}$, has binary states and the usual neighbourship relation of of diagonal or horizontal adjacency plus equality.

So essentially $CA$ consists of functions $f:\{0,1\}^9\rightarrow\{0,1\}$ or alternatively binary strings of length $2^9$.

I say a rule $r\in CA$ is population preserving, if for any population with a finite number of living resp. dead cells, the number of living resp. dead cells remains constant along one iteration step.

Is there an algorithm to decide whether a given rule is population preserving? Is there some way to localize the question, i.e. finding an equivalent definition which takes into acount only a finite number of populations to check on?

$\endgroup$
4
  • 2
    $\begingroup$ This is clearly decidable, since there is only a finite number of posibilities (namely $2^{512}$). $\endgroup$
    – Wojowu
    Feb 11, 2018 at 22:35
  • $\begingroup$ I also think it's decidable, but why is that so clear? If you take one rule, you still have an infinite number of populations to test on. $\endgroup$
    – fweth
    Feb 11, 2018 at 22:39
  • 1
    $\begingroup$ Take a list of all the population preserving rules. I don't care how you get it, but you should agree it exists and is finite. Now we can consider a Turing machine which has this list hard-coded into its ruleset and, given any rule, tells you immediately whether the rule is on this list. $\endgroup$
    – Wojowu
    Feb 11, 2018 at 22:41
  • $\begingroup$ Sorry, I didn't do my homework on theory of computation. I reformulated the question and deleted the decidability tag. $\endgroup$
    – fweth
    Feb 11, 2018 at 22:48

1 Answer 1

2
$\begingroup$

First, verify that the rule maps a neighborhood of all zeroes to zero, and all ones to one. Generate every possible $5\times 5$ array of cells where the center is 0. Apply the rule to all nine $3\times 3$ neighborhoods contained in this array, and sum the results. Then set the center to 1 and repeat this calculation. This test case passes if the new sum is one greater than the old sum. If every possible array passes, then the rule is population preserving.

Why does this work? Every configuration of finitely many “1” cells can be formed by starting with zeroes everywhere, then changing cells one at a time. Changing a cell only changes the next generation in the neighborhood surrounding that cell. Since every configuration passed the test, the count in the next generation always increases at the same rate as the current generation.

Also, this should generalize to any dimension, to any neighborhood size or shape, and any finite number of states.

UPDATE: I've looked around and found that there's already a much better algorithm. The most common term for this is number-conserving or conservative.

Durand and others (2003) gave a necessary and sufficient condition for a rule to be number-conserving. For a two-dimensional, two-state, $3\times 3$ neighborhood automaton, you have to plug (almost) all $2^9 = 512$ configurations of a $3\times 3$ square into an equation. (You don't have to test configurations where the first row or column is all zeroes, because all the terms cancel out.) This equation evaluates the rule 25 times over various sub-blocks of the configuration.

I also found a good overview.

B. Durand, E. Formenti, Z. Róka. Number-conserving cellular automata I: decidability. Theoretical Computer Science 299 (2003), pp. 523-535.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .