Affine cellular automaton

A 2-state cellular automaton is affine when each cell's transition function is an affine boolean function. A boolean function is said to be affine when each of its inputs either always or never affects its output. Equivalently, a boolean function is said to be affine when it can be written as f(x_1, ..., x_n) = w_1 x_1 ⊕ w_2 x_2 ⊕ ... ⊕ w_n x_n ⊕ b, where w_1, ..., w_n, b are booleans. The set of affine boolean functions also turns out to be exactly the set of functions that can be created from the XOR gate and the constant 1 function.

One-dimensional affine cellular automata

Among the 256 elementary cellular automata (that is, 2-state 1D cellular automata which operate on the 1D Moore neighbourhood), only 88 of them are non-equivalent (up to symmetry and black/white reversal). Among these 88 non-equivalent rules, only nine of them are affine (for instance, the rules 0, 15, 51, 60, 90, 105, 150, 170, 204).

Two-dimensional affine cellular automata

Among the 2²⁹ 2-state 2D cellular automata operating on the Moore neighbourhood, only 2¹⁰ = 1024 of them are affine. Among these, only 153 of them are non-equivalent (up to rotation, symmetry, and black/white reversal).

Universality

As Barbora Hudcová and Jakub Krásenský remarked in their article "Simulation limitations of affine cellular automata", there is currently no generally accepted formal definition of simulation or universality, making it extremely difficult to prove convincing negative results. However, they still show a negative result stating that almost every affine automaton can simulate only affine automata. Here, the definition of simulation is that an automaton A is simulated by an automaton B if each space-time diagram of A can be reproduced by B (after a suitable transformation).

However, it is still unknown whether there exists an affine cellular automaton which would "intuitively" be universal.

Black-white reversal

If the sum w_1 + ... + w_n is odd, then f(x_1, ..., x_n) = ¬f(¬x_1, ..., ¬x_n), and therefore the affine function is equal to its own black/white reversal. But if the sum w_1 + ... + w_n is even, then f(x_1, ..., x_n) != ¬f(¬x_1, ..., ¬x_n), and its black/white reversal is given by w_1 x_1 ⊕ w_2 x_2 ⊕ ... ⊕ w_n x_n ⊕ ¬b.