# Boolean derivatives and computation of cellular automata

## 1 Introduction

This work is based on the concept of Boolean derivatives, introduced in the context of cellular automata by G. Vichniac . A cellular automaton (CA) is defined on a lattice by an interaction range (for instance on a two dimensional square lattice, with nearest and next to nearest neighbors interactions), and by an updating rule that gives the future value (state) of a lattice variable given its present state and the state of its neighbors. The rule is applied in parallel on all the sites of the lattice, and can be either deterministic or probabilistic. From a computational point of view, the simplest case for the rule is a Boolean deterministic function, and, if not otherwise specified, we shall refer to this situation in the following. Cellular automata are often studied from a numerical point of view. Generally large lattices and long time simulations are required, and this originates the problem of developing efficient algorithms for the simulations of cellular automata on general purpose computers and sometimes on dedicated machines. For the first hardware resources, a technique that allows an efficient use of the memory and CPU is the Multi Site Coding (MSC) technique . This technique implies that the rule is coded only using bitwise operations. Although standard bitwise expressions (canonical forms) are easy to generate given a Boolean function, the minimization of the number of required operations is believed to be a np-complete problem . In Section 2 we recall the basic definitions and in the following section we introduce the Boolean derivatives that will lead to the Taylor and MacLaurin series for a Boolean function. They are more compact expressions than the standard canonical conjunctive and disjunctive forms. In Section 4 this technique is farther developed for the particular case of totalistic cellular automata, for which the future state of a cell depends only on the total number of neighbors that are in a certain state, regardless of their position. The symmetries of the problem allow the saving of a large number of Boolean operations. In Section 5 the results are applied to some models that appeared in literature. Finally, conclusions are drawn in the last section.

## 2 General definitions

Our fundamental set is $`B_1=\{0,1\}`$. This is called the Boolean set. Higher dimensional Boolean sets are indicated as $`B_n=\{0,1\}^n`$. By $`_{n,m}`$ we denote the set of functions $`f:\{0,1\}^n\{0,1\}^m`$. $`_n`$ stands for $`_{n,1}`$.

To an element $`a=(a_1,\mathrm{},a_n)B_n`$ corresponds a number $`a[0,2^n)`$:

$$a=\underset{i=1}{\overset{n}{}}a_i2^{i1};$$

and to each number $`a[0,2^n)`$ corresponds a $`n`$-tuple $`(a_1,\mathrm{},a_n)B_n`$:

$$a_i=a/2^{i1}mod2,$$

where $`a`$ stands for the integer part of $`a`$. An integer number is thus an ordered set of Boolean numbers (bits). In order to emphasize its Boolean structure we shall refer to these sets with the name of bitarray, whose dimension is that of the space in which it is defined. We introduce a partial ordering between bitarrays saying that $`ab`$ if, for all $`i`$, $`a_ib_i`$, where $`0<1`$. We can thus substitute the expression $`a[0,2^{n1})`$ by $`a2^{n1}1`$ or simply $`aB_n`$. A Boolean function $`f`$ is called monotone if $`ab`$ implies $`f(a)f(b)`$.

This mapping between numbers and Boolean $`n`$-ple corresponds to the representation of integer numbers in computers, the integer division by a power of two being equivalent to a right shift (in FORTRAN $`a/2^{i1}\mathrm{𝚂𝙷𝙸𝙵𝚃𝚁}(𝚊,𝚒\mathrm{𝟷})`$), and the modulo two operation to take the leftmost (less important) bit.

Let us introduce the most common Boolean operations. If applied to a bitarray, they will act bit by bit. There are $`2^{2^n}`$ Boolean functions in $`_n`$. With $`n=1`$ the most important function is the negation (NOT), indicated by the symbol $`\neg `$, or by a bar over the argument. With $`n=2`$ there are 16 functions. The ones that exist on (almost) all computers are the AND, OR and XOR operations. The AND (symbol $``$) gives one only if both the arguments are one (it is equivalent to a multiplication of the bits considered as integer numbers), the OR (symbol $``$) gives one if either one or the other argument is one, while the XOR (symbol $``$) corresponds to the sum modulo two. Notice that the XOR operation accounts both for the sum and for the subtraction or negation ($`aa=0`$ and $`a1=\neg a`$). The AND has higher priority than the OR and XOR operations. The negation has the highest priority. The OR and the XOR operations are distributive with respect to the AND. The XOR operation can be expressed by the NOT, AND and OR: $`ab=\neg aba\neg b`$. Equivalently the OR can be expressed by the AND and XOR operations: $`ab=abab`$. If two Boolean quantities $`a`$ and $`b`$ cannot be one at once, both the expressions $`ab`$ and $`ab`$ give the same result. In the following we shall emphasize this condition by writing $`a+b`$, and indeed in this case the usual sum operation can be used. On certain computers (namely on the CRAY), the logical and numerical unities can work in parallel. By mixing Boolean and arithmetic operations it is possible to speed up the actual calculations .

Often in the literature  the conditional negation is indicated by $`a^b`$ with the meaning that $`a^0=\neg a`$ and $`a^1=a`$. This is equivalent to $`\neg (ab)`$ or to $`ab1`$. In this work we prefer to assign a different meaning to exponentiation, more similar to the usual one. We define $`a^0=1`$ and $`a^1=a`$. With this definition the expression $`a^b`$ is equivalent to $`(a1)b1`$ or to $`a\neg b`$. When applied to bitarrays, the exponentiation is performed bit by bit and the results are afterwards ANDed together,

$$a^b=\underset{i=1}{\overset{n}{}}a_i^{b_i}=\underset{i=1}{\overset{n}{}}a_i\neg b_i.$$
(1)   
We note that $`a^b`$ is equal to one if and only if $`ab`$.

A Boolean function $`f_n:xB_nf(x)`$ is defined by giving its results for all the possible ($`2^n`$) configurations of its arguments (truth table). It is possible to obtain an expression for the $`f`$ only containing the AND, OR and NOT operations from this table. It is sufficient to give $`f^1(0)`$ or $`f^1(1)`$. The two canonical forms are

$$\begin{array}{cc}\hfill f(x)& =\underset{af^1(1)}{}\underset{i=1}{\overset{n}{}}\neg (x_ia_i);\text{disjunctive form, and}\hfill \\ \hfill f(x)& =\underset{af^1(0)}{}\underset{i=1}{\overset{n}{}}x_ia_i;\text{conjunctive form.}\hfill \end{array}$$

These canonical forms are the standard starting points for the problem of minimizing the number of required operations given a function. It is possible to demonstrate  that the minimal expression for a monotone function only contains the AND and OR operations; the expression is unique and easy to compute.

As the NOT and the OR can be expressed by the AND and XOR operations, any function $`f`$ can be given in terms of the latter two operations (Ring Sum Expansion, RSE) . This form is identified by a Boolean vector $`f_i;iB_n`$

$$f(x)=\underset{iB_n}{}f_ix^i.$$
(2)   
Since the number of different Boolean vectors $`f_i`$ and of functions $`f_n`$ is equal, the RSE is unique.

## 3 Boolean derivatives

Following Vichniac , we define the derivative of a Boolean function $`f_n`$ with respect to its $`i`$-th argument $`x_i`$ as

$$\frac{f}{x_i}|_x=f(x_1,\mathrm{},x_i,\mathrm{},x_n)f(x_1,\mathrm{},\neg x_i,\mathrm{},x_n).$$

This (first order) derivative expresses the dependence of the function by its $`i`$-th argument: $`f/x_i`$ is one if $`f`$ changes when changing $`x_i`$, given the configuration $`x_1,\mathrm{},x_{i1},x_{i+1},\mathrm{},x_n`$. If the derivative of $`f`$ with respect to $`x_i`$ is one regardless of the other arguments, than the rule changes its value whenever $`x_i`$ does. In Ref.  a rule that shows this behavior is called a toggle rule.

This definition is consistent with the common expectations: the derivative of the identity function is one, and the derivative of a constant (0 or 1) is zero. Moreover, the derivative is linear with respect to the XOR operations, and it follows the standard rule for the derivative of a product,

$$\frac{(fg)}{x}=\frac{f}{x}gf\frac{g}{x}.$$

We can extend the definition to higher order derivatives. For example, a second order derivative with respect to $`x_i`$ and $`x_j`$ is defined as

$$\begin{array}{cc}\hfill \frac{^2f}{x_ix_j}|_x=& f(x_1,\mathrm{},x_i,\mathrm{},x_j,\mathrm{},x_n)f(x_1,\mathrm{},\neg x_i,\mathrm{},x_j,\mathrm{},x_n)\hfill \\ & f(x_1,\mathrm{},x_i,\mathrm{},\neg x_j,\mathrm{},x_n)f(x_1,\mathrm{},\neg x_i,\mathrm{},\neg x_j,\mathrm{},x_n).\hfill \end{array}$$

Note that the definition is consistent with the usual chain rule for derivatives, i.e.,

$$\frac{^2f}{xy}=\frac{}{y}\left(\frac{f}{x}\right).$$
(3)   
A second order derivative with respect to the same argument is identically zero.

We introduce a more compact definition for the Boolean derivatives. Indicating with $`x`$ the bitarray of the arguments $`(x_1,\mathrm{},x_n)`$ and with $`\delta `$ a (constant) bitarray of the same dimension, we define

$$_\delta f(x)=\underset{\alpha \delta }{}f(x\alpha ).$$

It is immediate to verify that $`_\delta f(x)`$ is equal to the partial derivative in $`x`$ of $`f`$ with respect to the variables that correspond to nonzero bits in $`\delta `$. For instance, indicating with $`\delta ^{(i)}`$ a bitarray in which only the $`i`$-th bit is set to one (i.e., $`\delta _i^{(i)}=\delta _{i,j}`$, where the latter is the usual Kronecker symbol), we have

$$_{\delta ^{(i)}}f(x)=\frac{f}{x_i}|_x.$$

We can now state our most important result. For a Boolean function the Taylor expansion is always finite. Let us start with a perturbation on only one variable. If $`y=x\delta ^{(i)}`$, from the definition (3) of the derivative we get

$$f(y)=f(x)_{\delta ^{(i)}}f(x).$$

Generalizing

$$f(x\delta )=\underset{\alpha \delta }{}_\alpha f(x),$$

with $`_0f(x)=f(x)`$.

Using our definition of the exponentiation (1), we can substitute the XOR over $`\alpha \delta `$ with a XOR over $`\alpha B_n`$. We need a test function that gives one if $`\alpha \delta `$ and zero otherwise, and from the consideration after Eq. (1) this can be expressed as $`a^b`$. Finally we obtain

$$f(x\delta )=\underset{\alpha B_n}{}\delta ^\alpha _\alpha f(x).$$

As a noticeable consequence, we can expand a function starting from 0 (the bitarray that has all the bits to zero), obtaining the MacLaurin series

$$f(x)=\underset{\alpha B_n}{}x^\alpha f_\alpha ,$$
(4)   
where

$$f_\alpha =_\alpha f(0);$$
(5)   
Which is the ring sum expansion of the function $`f`$, Eq. (2).

Let us explicitly write down the formula (4) for an elementary CA, whose evolution rule depends on the cell itself ($`y`$) and on its nearest neighbors ($`x`$ and $`w`$). Locally

$$y^{}=f(x,y,w)$$

where the prime indicates the future value of the cell. The MacLaurin expansion of $`f`$ is given by

$$\begin{array}{cc}\hfill y^{}=& f(0,0,0)\hfill \\ & x\frac{f}{x}|_{0,0,0}y\frac{f}{y}|_{0,0,0}z\frac{f}{z}|_{0,0,0}\hfill \\ & xy\frac{f^2}{xy}|_{0,0,0}xz\frac{f^2}{xz}|_{0,0,0}yz\frac{f^2}{yz}|_{0,0,0}\hfill \\ & xyz\frac{f^3}{xyz}|_{0,0,0}.\hfill \end{array}$$

The first order derivatives of all the elementary CA can be found in Ref. . Higher order derivatives can be obtained by using the chain rule (3). Otherwise, the array of derivatives $`f_i`$ in zero can be obtained from the truth table $`f(j)`$ via the matrix $`_{i,j}`$

$$f_i=\underset{jB_n}{}_{i,j}f(j);$$

where

$$_{i,j}=\left(\genfrac{}{}{0pt}{}{j}{i}\right)mod2.$$

The matrix $``$ can be recursively generated considering that

$$\begin{array}{cc}\hfill _{i,0}& =1;\hfill \\ \hfill _{0,j}& =0(j>0);\hfill \\ \hfill _{i,j}& =_{i1,j}_{i1,j1}(i,j>0);\hfill \end{array}$$
(6)   
To show an application of the MacLaurin expansion, let us examine the expression normally used to select between two random bits $`a`$ and $`b`$ according to a third one ($`r`$),

$$f(r)=ra\neg rb\text{(4 operations)}.$$

We only consider the explicit dependence of the function on $`r`$. To write down the ring sum expansion of $`f(r)`$ we need

$$\begin{array}{cc}\hfill f(0)& =b;\hfill \\ \hfill _1f(0)& =f(0)f(1)=ba.\hfill \end{array}$$

The RSE for $`f(r)`$ is

$$f(r)=br(ab)\text{(3 operations)}.$$

We consider it a good result to save one operation out of four in such a widely used and (apparently) simple expression. Other examples can be found in section 5.

## 4 Totalistic rules

The power of the algorithm is particularly evident when applied to totalistic CAs. The transition rule for these automata depends on the sum of the cell values in the neighborhood,

$$T^{(n)}=\underset{i=1}{\overset{n}{}}x_i.$$

Any totalistic evolution rule can be written as

$$f(x_1,\mathrm{},x_n)=f\left(T^{(n)}\right)=\underset{k=0}{\overset{9}{}}r_k\chi _k^{(n)}$$
(7)   
where $`\chi _k^{(n)}`$ is one if $`T^{(n)}=k`$ and zero otherwise (totalistic characteristic functions). Only one term contributes in the sums of equations (7) so that we can use the arithmetic summation. The quantities $`r_k`$ take the value zero or one and define the automaton rule. Probabilistic CAs may be implemented by allowing the coefficients $`r_k`$ of equation (7) to assume the values zero and one with probabilities $`p_k`$ (see also the last example of Section 5).

A totalistic function $`f`$ is completely symmetrical with respect to its arguments . This implies that the derivatives of $`f`$ of same order are all functionally equals. In particular, as the derivatives of the MacLaurin expansion (4) are calculated in zero, they are actually equals, and thus can be factorized. This leads to

$$f(x_1,\mathrm{},x_n)=f\left(T^{(n)}\right)=f_0f_1\xi _1^{(n)}f_2\xi _2^{(n)}\mathrm{}f_n\xi _n^{(n)};$$
(8)   
where the $`f_i`$ represents the derivative of order $`i`$ of $`f`$ in 0 (5), and the $`\xi _i^{(n)}`$ are the homogeneous polynomes of degree $`i`$ in the variables $`x_1,\mathrm{},x_n`$ (using the AND for the multiplication and the XOR for the sum)

$$\begin{array}{cc}\hfill \xi _1^{(n)}& =x_1x_2\mathrm{}x_n,\hfill \\ \hfill \xi _2^{(n)}& =x_1x_2x_1x_3\mathrm{}x_{n1}x_n,\hfill \\ & \mathrm{}\hfill \\ \hfill \xi _n^{(n)}& =x_1x_2\mathrm{}x_n.\hfill \end{array}$$

The functions $`\xi _i`$ satisfy some recurrence relations. The first one is based on the idempotent property of the AND operation ($`aa=a`$) and the nullpotent property of the XOR operation ($`aa=0`$)

$$\begin{array}{cc}\hfill \xi _1& :\text{ irreducible;}\hfill \\ \hfill \xi _2& :\text{ irreducible;}\hfill \\ \hfill \xi _3& =\xi _2\xi _1;\hfill \\ \hfill \xi _4& :\text{ irreducible;}\hfill \\ \hfill \xi _5& =\xi _4\xi _1;\hfill \\ \hfill \xi _6& =\xi _4\xi _2;\hfill \\ \hfill \xi _7& =\xi _4\xi _3=\xi _4\xi _2\xi _1;\hfill \\ \hfill \xi _8& :\text{ irreducible;}\hfill \\ & \mathrm{}.\hfill \end{array}$$

The second property is based on the separation of the variables in two groups (bisection). Let us call $`X`$ the group of the variables $`(x_1,\mathrm{},x_n)`$, with $`L`$ we indicate the left part of $`X`$ up to some index $`j`$, and with $`R`$ the right part of $`X`$

$$\begin{array}{cc}\hfill L& =(x_1,\mathrm{},x_j)\hfill \\ \hfill R& =(x_{j+1},\mathrm{},x_n).\hfill \end{array}$$

We have

$$\begin{array}{cc}\hfill \xi _i(X)=& \xi _i(L)\xi _{i1}(L)\xi _1(R)\xi _{i2}(L)\xi _2(R)\mathrm{}\hfill \\ & \xi _1(L)\xi _{i1}(R)\xi _i(R).\hfill \end{array}$$

As an example, let us explicitly calculate the $`\xi _i`$ for eight variables. We bisect homogeneously the set $`X=(x_1,\mathrm{},x_8)`$ first into $`L`$, $`R`$, and then into $`LL`$, $`LR`$, $`RL`$, $`RR`$. We have

$$\{\begin{array}{cc}\xi _1(LL)\hfill & =x_1x_2,\hfill \\ \xi _1(LR)\hfill & =x_3x_4,\hfill \\ \xi _1(RL)\hfill & =x_5x_6,\hfill \\ \xi _1(RR)\hfill & =x_7x_8;\hfill \\ \xi _2(LL)\hfill & =x_1x_2,\hfill \\ \xi _2(LR)\hfill & =x_3x_4,\hfill \\ \xi _2(RL)\hfill & =x_5x_6,\hfill \\ \xi _2(RR)\hfill & =x_7x_8;\hfill \end{array}$$

$$\{\begin{array}{cc}\xi _1(L)\hfill & =\xi _1(LL)\xi _1(LR),\hfill \\ \xi _1(R)\hfill & =\xi _1(RL)\xi _1(RR);\hfill \\ \xi _2(L)\hfill & =\xi _2(LL)\xi _1(LL)\xi _1(LR)\xi _2(LR),\hfill \\ \xi _2(R)\hfill & =\xi _2(RL)\xi _1(RL)\xi _1(RR)\xi _2(RR);\hfill \\ \xi _3(L)\hfill & =\xi _2(L)\xi _1(L),\hfill \\ \xi _3(R)\hfill & =\xi _2(R)\xi _1(R);\hfill \\ \xi _4(L)\hfill & =\xi _2(LL)\xi _2(LR),\hfill \\ \xi _4(R)\hfill & =\xi _2(RL)\xi _2(RR);\hfill \end{array}$$

$$\{\begin{array}{cc}\xi _1^{(8)}\hfill & =\xi _1(L)\xi _1(R);\hfill \\ \xi _2^{(8)}\hfill & =\xi _2(L)\xi _1(L)\xi _1(R)\xi _2(R);\hfill \\ \xi _3^{(8)}\hfill & =\xi _2\xi _1;\hfill \\ \xi _4^{(8)}\hfill & =\xi _4(L)\xi _3(L)\xi _1(R)\xi _2(L)\xi _2(R)\xi _1(L)\xi _3(R)\xi _4(R);\hfill \\ \xi _5^{(8)}\hfill & =\xi _4\xi _1;\hfill \\ \xi _6^{(8)}\hfill & =\xi _4\xi _2;\hfill \\ \xi _7^{(8)}\hfill & =\xi _4\xi _3;\hfill \\ \xi _8^{(8)}\hfill & =\xi _4(L)\xi _4(R).\hfill \end{array}$$

where $`\xi _k^{(8)}=\xi _k(X)`$. Taking into account the common patterns that appear in the expressions of $`\xi _2^{(8)}`$ and $`\xi _4^{(8)}`$, we only need 34 operations to build up all the $`\xi _i^{(8)}`$.

The extension of the calculations to 9 variables, only adds a small number (16) of operations

$$\begin{array}{cc}\hfill \xi _1^{(9)}& =\xi _1^{(8)}x_9,\hfill \\ \hfill \xi _i^{(9)}& =\xi _i^{(8)}\xi _{i1}^{(8)}x_9(2i8),\hfill \\ \hfill \xi _9^{(9)}& =\xi _8^{(8)}x_9;\hfill \end{array}$$

even though a careful bisection of the set of variables implies fewer (39) operations.

A kind of normalization condition on the $`\xi _i`$ is given by

$$\underset{i=1}{\overset{n}{}}x_i=\underset{i=1}{\overset{n}{}}\xi _i^{(n)},$$
(9)   
and can be used to save operations in building an expression containing a XOR of $`\xi _i`$. Another useful relation is

$$\underset{i=1}{\overset{n1}{}}(x_ix_{i+1})=\underset{i=1}{\overset{n1}{}}\xi _i^{(n)}.$$
(10)   
We now have to build up the derivatives (in zero) of a totalistic function $`f`$, Eq. (8). There are only $`n+1`$ independent derivatives $`f_i`$, $`(i=0,\mathrm{},n)`$, as all the derivatives of the same order $`i`$ are equal. We have

$$f_i=\underset{T=0}{\overset{i}{}}_{i,j}f(T),$$

where the matrix $``$ is defined in Eq. (6).

For completeness, we report the expressions for the $`\chi _k^{(8)}`$ and $`\chi _k^{(9)}`$,

$$\begin{array}{cc}\hfill \chi _1^{(8)}& =\xi _1\xi _3\xi _5\xi _7,\hfill \\ \hfill \chi _2^{(8)}& =\xi _2\xi _3\xi _6\xi _7,\hfill \\ \hfill \chi _3^{(8)}& =\xi _3\xi _7,\hfill \\ \hfill \chi _4^{(8)}& =\xi _4\xi _5\xi _6\xi _7,\hfill \\ \hfill \chi _5^{(8)}& =\xi _5\xi _7,\hfill \\ \hfill \chi _6^{(8)}& =\xi _6\xi _7,\hfill \\ \hfill \chi _7^{(8)}& =\xi _7,\hfill \\ \hfill \chi _8^{(8)}& =\xi _8;\hfill \\ \hfill \chi _1^{(9)}& =\chi _1^{(8)}\xi _9,\hfill \\ \hfill \chi _2^{(9)}& =\chi _2^{(8)}\mathrm{}\chi _8^{(9)}=\chi _8^{(8)},\hfill \\ \hfill \chi _9^{(9)}& =\xi _9.\hfill \end{array}$$
(11)   
Obviously, the $`\chi _k^{(9)}`$ are only formally similar to the $`\chi _k^{(8)}`$ and they are calculated with nine variables.

We note that the normalization condition on the $`\chi _k^{(n)}`$ is

$$\underset{k=0}{\overset{n}{}}\chi _k^{(n)}=1;$$
(12)   
from which $`\chi _0^{(n)}`$ can be obtained.

Putting all the stuff together, we need a maximum of 1024 operations for a generic rule with eight arguments, and 2304 operations for a generic rule with nine arguments (if all the operations are explicitly developed); 50 (resp. 57) operations for a generic totalistic rule with eight (resp. nine) arguments using directly the $`\xi _i`$ of Eq. (8) and 73 (resp. 82) using the $`h_k`$ of Eq. (7). These numbers should be compared with the $`3000`$ operations of the standard disjunctive form for a function of eight arguments whose truth table is half filled with ones and with the $`600`$ operations required for a totalistic rule with nine arguments as described in Ref. .

We can see that the Taylor expansion of a Boolean function allows a big saving if the function itself depends symmetrically on the variables (i.e., it is a totalistic function). Sometimes a function depends in a totalistic way only on part of the variables (see e.g., the Life rule in the following section). After rearranging the indices,

$$f(x_1,\mathrm{},x_i,x_{i+1},\mathrm{},x_n)=f^{}(g(x_1,\mathrm{},x_i),x_{i+1},\mathrm{},x_n),$$

where $`g(x_1,\mathrm{},x_i)`$ is a totalistic function. If this happens, we have

$$f_{(\mathrm{},x_j,\mathrm{},x_k,\mathrm{})}=f_{(\mathrm{},x_k,\mathrm{},x_j,\mathrm{})}(j,ki)xB_n.$$

From a computational point of view, $`f`$ depends symmetrically on $`x_j`$ and $`x_k`$ if

$$\underset{iB_n}{}\left(f_if_{i\delta }\right)=0,$$
(13)   
where $`\delta =\delta ^{(j)}\delta ^{(k)}`$. Symmetries among more than two variables can be obtained via the transition property.

## 5 Some applications

In this section we shall apply the algorithm to some problems, chosen among the ones that appeared in literature. Some of them were investigated with efficiency in mind, so they are supposed to be carefully studied with the aim of reducing the number of required operations.

The first example is the totalistic two-dimensional CA M46789 . The future value $`c^{}`$ of a cell $`c`$ is determined by the value most prevalent in its Moore neighborhood (nearest and next to nearest neighbors, nine variables), with a twist in case of a marginal majority or minority. In terms of Eq. (7) the rule is defined as

$$r_k=\{\begin{array}{cc}1\hfill & \text{if }k=4,6,7,8,9\text{;}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

The twist in the majority provides a kind of frustration that simulates a mobile interface according to the Allen-Cahn equation .

From the general expression (8), we get the simplified expression

$$c^{}=\xi _4\left[1\xi _1\left(1\xi _2\right)\right]\xi _8,$$

for a total of 39 operations.

The second model is the game of Life . This well known game has recently shown to be a good tool model for the problem of the self-organizing criticality . The evolution rule for Life depends separately on the sum of the eight nearest and next-to-nearest neighbors (outer Moore neighborhood), and on the central cell itself.

The evolution rule can be expressed saying that a dead (zero) cell can become alive (one) only if it is surrounded by three alive cells, while survival only occurs if the alive cell is surrounded by two or three alive cells. Developing first the rule for the central cell $`c`$, we get

$$c^{}=\chi _3^{(8)}\chi _2^{(8)}c,$$

where $`c^{}`$ represent the updated value of the central cell, and the $`\chi _k^{(8)}`$ are calculated on the outer Moore neighborhood.

The substitution of the expressions for the $`\chi _k^{(8)}`$ (11) and simplification gives

$$c^{}=\xi _2\left[c(1c)\xi _1\right]\left(1\xi _4\right).$$

As $`a\neg ab=ab`$ we have

$$c^{}=\xi _2\left(1\xi _4\right)\left(c\xi _1\right),$$

that implies only 33 operations, to be compared with the $`170`$ ones reported in Ref. .

We can also apply the method to non totalistic rules. Let us examine the Kohring rule  for an FHP  gas with obstacles. The collision rules are the same of the original FHP model, with a set of four body collisions. Let us label the six directions in a counterclockwise way with the indices ranging from one to six. The operations on the indices are supposed to be modulo six. All the Boolean quantities are actually elements of some array of integer words: we do not consider here the spatial indices. If the Boolean variable $`x_i`$ is one, there is an incoming particle on the site from direction $`i`$. Collisions occur for

$$(x_{j+1},\mathrm{},x_{j+6})=\{\begin{array}{cc}(1,0,0,1,0,0),\hfill & \text{two particles collisions;}\hfill \\ (1,0,1,0,1,0),\hfill & \text{three particles collisions;}\hfill \\ (1,1,0,1,1,0),\hfill & \text{four particles collisions.}\hfill \end{array}$$

The index $`j=0,\mathrm{},5`$ provides for all the rotational invariant configurations.

After the application of the collision rule, the variable $`y_i`$ equal to one means that there is a particle outgoing from the site with direction $`i+3`$. If the particles travel unperturbed, the updating rule is just $`y_i=x_i`$. On each lattice site there is an additional bit, indicated by $`a`$, to code the local conservation of angular momentum. If $`a`$ is one and a collision takes place, then all the particles on the site turn counterclockwise of $`\pi /3`$ (i.e., $`y_i=x_{i1}`$), otherwise the rotation is clockwise ($`y_i=x_{i+1}`$). The $`a`$ bit is reversed each time a collision takes place. Finally, a bit $`b=0`$ (1) indicates the presence (absence) of an obstacle. The meaning of $`b`$ is reversed from that in Ref.  for convenience. In the case $`b=0`$ no collision occurs, but the velocities of the particles are reversed, i.e., $`y_i=x_{i+3}`$. For further details about the implementation we refer to Khoring’s work .

First we want to obtain the expression for a bit $`c`$ that indicates the occurrence of a collision. The two cases of zero and six particles can eventually be included among the collisions, without having any consequence. There are no symmetries among the variables in the truth table of the collisions (see Eq. (13)), so it is preferable to divide them into two groups, two and four particles collisions in one group, and three particle collisions in the other one. The first group is characterized by symmetries between $`x_i`$ and $`x_{i+3}`$. Introducing the auxiliary variables $`w_i=x_ix_{i+3}`$ (only three of them are really needed), we get

$$c(0,2,4,6)=\chi _0^{(3)}(w1,w2,w3);$$

where $`c(i,j,\mathrm{})`$ indicates the contribution to the collision bit by the $`i,j,\mathrm{}`$ particles collisions, and the $`\chi _k^{(3)}`$ are the totalistic characteristic functions for three arguments. From Eq. (12), (9) and (11) we obtain

$$\neg c(0,2,4,6)=w1w2w3.$$

Three particles collisions occur when $`(x_1,x_3,x_5)`$ or $`(x_2,x_4,x_6)`$ are all zero or one, that is

$$\begin{array}{cc}\hfill \neg c& (0,3,6)=\hfill \\ & =\left[\chi _1^{(3)}(x_1,x_3,x_5)+\chi _2^{(3)}(x_1,x_3,x_5)\right]\left[\chi _1^{(3)}(x_2,x_4,x_6)+\chi _2^{(3)}(x_2,x_4,x_6)\right]\hfill \\ & =\left[\xi _1(x_1,x_3,x_5)\xi _2(x_1,x_3,x_5)\right]\left[\xi _1(x_2,x_4,x_6)\xi _2(x_2,x_4,x_6)\right].\hfill \end{array}$$

Using the property (10) we get

$$\begin{array}{cc}\hfill \neg c(0,3,6)& =(x_1x_3)(x_3x_6)(x_2x_4)(x_4x_6);\hfill \\ \hfill c& =\neg \left[\neg c(0,2,4,6)\neg c(0,3,6)\right].\hfill \end{array}$$

This expression for the collision bit is equal to that found in Ref. .

The expression for the $`y_i`$ can be though as a function of $`a,b,c`$. Developing the expression we get

$$y_i=x_{i+3}b(x_{i+3}x_iz_i),$$

where

$$z_i=\left[x_ix_{i+1}(x_{i+1}x_{i1})a\right]c.$$

Finally, we notice that

$$z_iz_{i+3}=\left[w_iw_{i+1}(w_{i+1}w_{i1})a\right]c;$$

but when $`c=1`$ all the $`w_i`$ are zero, so $`z_i=z_{i+3}`$. We need one more operation to reverse the angular momentum bit in case of a collision, $`a^{}=ca`$. Taking into account the common patterns in the expression of $`c`$,$`z_i`$ and $`y_i`$, we only need 35 operations to update all the six velocities, and 14 arrays (six for the old values of the particles, six for the new values, one for the angular momentum and one for the collision bits). For comparison, in Ref.  the algorithm needs 74 operations and 16 arrays.

Incidentally, we observe that only six arrays are really needed to store the configuration, without the needing of a translational phase. Indeed, the rule only implies an (eventual) exchange of the particles among the planes (the RAP1 machine  is based on this consideration). The translation of the particles can be taken into account by a logical shift of the origin of the arrays. The procedure is still vectorizable, but the mapping between the lattice and the arrays of integer words is indeed more complex, so maybe it is not worth doing the efforts unless perhaps for a dedicated hardware.

The last example involves a probabilistic totalistic CA for the simulation of the Ising model . The rule depends in a totalistic way on the outer Von Neumann neighborhood (the north, east, south and west neighbors). The rule can be expressed as

$$c^{}=\underset{k=0}{\overset{4}{}}r_k\chi _k^{(4)},$$

where the $`r_k`$ are random bits equal to one with predefined probabilities $`p_k=p(r_k)`$. Building the $`\chi _k^{(4)}`$ from the $`\xi _i`$ as in Eq. (11), we get the quoted result of 22 Boolean operations and four arithmetic summations. Writing down the RSE (2), we have

$$c^{}=r_0\underset{i=1}{\overset{4}{}}s_i\xi _i,$$

where the $`s_i`$ are random bits with probability $`p(s_i)`$, obtained as

$$\begin{array}{cc}\hfill s_1& =r_0r_1,\hfill \\ \hfill s_2& =r_0r_2,\hfill \\ \hfill s_3& =r_0r_1r_2r_3,\hfill \\ \hfill s_4& =r_0r_4;\hfill \end{array}$$

and considering that $`p(ab)=p(a)+p(b)2p(a)p(b)`$.

Using the approach described above, we need nine operations to build up the $`\xi _i`$ and eight operations for $`c^{}`$.

## 6 Conclusions

In this work we extend and complete the notion of the derivatives of a Boolean function already introduced in Ref. . We are thus able to derive the Taylor and MacLaurin series of a Boolean function. The latter represent the ring sum expansion for a Boolean function, which is more compact than the canonical conjunctive and disjunctive forms. Moreover, for totalistic functions (i.e., for functions completely symmetric in their arguments) very compact expressions are found. These ideas have wide applications in the development of faster algorithms, in particular for cellular automata simulations, and in the design of digital circuitry. As examples of physical applications, we analyze already published optimized algorithms, involving both deterministic and stochastic automata. We found that our procedure generally leads to more compact expressions. We think that the Boolean derivative is not limited to the minimization of Boolean functions. Work is in progress about the connection between Boolean derivatives and the chaotic properties of cellular automata, possibly leading to the definition of Lyapunov exponents for discrete systems.

## acknowledgements

We are grateful to G. Vichniac, R. Livi and S. Ruffo for fruitful discussions. We also acknowledge the Institute for Scientific Interchange Foundation (Torino, Italy) where this work was first started in the framework of the workshop Complexity and Evolution.