Parity rule

Parity rules (or odd rules) are a specific class of one-dimensional cellular automata which may be defined to have each cell's state determined by the XOR of their neighbourhood for two-state patterns, and more generally, their sum modulo p for higher prime state numbers p.

XOR (and summation modulo an integer) is a distributive; using the ⊕ symbol, a⊕(b⊕c) = (a⊕b)⊕c. As such, a parity rule is distributive with XOR; for a parity rule r, beginning with two states, S and T, r(S⊕T) = r(S)⊕r(T). Since XOR is not a universal logic gate , no parity rule may be Turing-complete.

Although XOR is bijective, parity rules are not, since some admit nonempty patterns that vanish under their application, with which a pattern's predecessor may be XORed; however, such a perturbation must be infinite, so all finite patterns have unique finite predecessors.

The behaviour of several classes of patterns in two-dimensional cellular automata, notably replicators, are dictated by these parity rules.

An s-state rulespace in an n-cell neighbourhood has s^sn rules. However, each state can be assigned an integer in [0,s), then parity rules assign weights to each neighbour in a modular sum, meaning it has only sⁿ parity rules.

Etymology

Rather than each cell being the XOR of its neighbourhood, consider each cell being convolved with its neighbourhood rotated 180º, and both the universe U_t and the neighbourhood N to be multivariate polynomials (in as many variables as there are dimensions), with the cell at coordinates (n,k) being the parity of the coefficient of xⁿ*y^k (ie. its coefficients are over GF(2) ), then performing an iteration of the cellular automaton is equivalent to multiplication by N (ie. U_t+1 = U_t*N).

In one dimension

All two-state rules with two-cell neighbourhoods have evolution forming Sierpinski triangles, the only range-1 one-dimensional cellular automaton which does not is rule 150.

On February 1, 2022, Jiahao Yu showed a construction of oscillators of arbitrary period in rule 150, in finite tapes with differing edge states.

Table

An incomplete table of parity rules with prime n states and m>= copies is as follows:

Copies / States	2	3	5	7	11	13	17	19
0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1
2	2	2	2	2	2	2	2	2
3	3	3	3	3
4	4	4	4	4
5	5	5	5	5
6	6	6	6	6
7	7	7	7	7
8	8	8	8	8
9	9	9	9	9
10	10
11	11
12	12
13	13
14	14
15	15
16	16
17	17
18	18
19	19
20	20
21	21
22	22

The rule integers for 2-state rules follow the sequence A020988.

The following are parity rules in which the center cell is absent (2-state rule integers follow A108020):

Copies / States	2	3
0	0
2	12	532926
4	204
6	3276
8	52428
10	838860
12	13421772
14	214748364

In two dimensions

Replicator and Fredkin are parity rules in the outer-totalistic neighbourhood whose neighbourhoods exclude and include the central cell.

There are 2ⁿ² anisotropic parity rules in an n × n neighbourhood, and A054247(n) up to symmetry.

External links

• Shalosh B. Ekhad, N. J. A. Sloane, Doron Zeilberger (March 5, 2015). A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata [math.CO], accompanying Maple package