Parallel Arithmetic by Cellular Automata

In one study, Steiglitz, Irfan Kamal, and Arthur Watson (1988) designed a particular class of CAs—the one-dimensional, binary-state, parity-rule filter automata — to perform arithmetic. This class of automata has the property that propagating periodic structures often act as solitons —that is, they can pass through each other in space-time without destroying eax h other, but only shifting each others phase. It turns out that such a feature can be useful for implementing arithmetic operations in CAs via particle interactions. 

One-dimensional filter automata (FAs) differ from standard CAs in that their cells are updated asynchronously from left to right given radius r, a cell i is updated using the neighborhood, 

A binary-state parity-rule FA (BPFA) is defined by the update rule. 

The BPFAs are parameterized by the radius r. The lattice will be thought of as infinite, but the initial configurations will contain only a finite number of nonzero sites. 

Steiglitz, Kamal, and Watson devised an algorithm for enumerating all particles of period p that could be formed and could propagate in a BPFA with a given radius r. They also devised a scheme in which information could be encoded in a particle s phase state —a combination of its periodic phase and its displacement with respect to the left boundary of. the lattice. They were then able to empirically construct tables giving the results of collisions between pairs of particles las a function of their phase states. 

---