Cu

A simple universal 2D CA

Cu is a simple intrinsically universal 2D cellular automaton with 3 states rotation-reflexion invariant and von Neumann neighborhood designed to illustrate the concept of universality by boolean circuit simulation. It is wire based in the style of Banks. The rule can be described as follows based on the current state of the cell :

• in state 0, if two opposite neighbors (N and S or W and E) are not in state 0 then enter state 1 else stay in state 0 ;
• in state 1, if the number of neighbors not in state 0 is greater or equal to 2 and either the number of neighbors in state 1 or the number of neighbors in state 2 is exactly equal to 1 then enter state 2, else stay in state 1 ;
• in state 2, enter state 0.

Design

The rule is designed to permit the construction of particles (a pair of states 0 and 2) moving along wires (a thread of states 1 in a world of states 0).

A particle in a dead end vanishes.

When two particles collide in odd position, they disappear.

At an intersection (3 or 4 ends), a single entering particle generates a leaving particle on every other end.

At an intersection (3 or 4 ends), all but one entering particles generate a leaving particle on the last end.

At an intersection (3 or 4 ends), other cases lead to no leaving particle.

Logic

Using this design, the universality for boolean circuits can be obtained with the following steps. First, construct a diode (a particle can cross from left to right but not from right to left).

With two diodes and some wires, construct a XOR gate (using XOR gates one can construct signal crossing).

Using the same scheme, construct an OR gate.

Wires, turns, fan-out, XOR and OR gates are enough to be universal (encoding a bit as a particle on a pair of wires). As an example, here are an encoded NOT gate and AND gate for signals encoded on pairs of wires.

Playing with Cu

cu.tar.gz contains a description of the rule and a bunch of patterns in a format suitable to use with Golly (a cross-platform 2D CA simulator using hashing techniques).

Feel free to send me lots of interesting patterns (better gates, small circuits coding nice functions, etc). Once a nice collection is obtained, I plan to submit it with the rule for inclusion into Golly.

Challenges

Simulation How fast can you simulate this cellular automaton? Hashing (à la Hashlife) is one way to accelerate, considering non quiescent parts (the few particles in an encoded circuit) is another.

Encoding Given a boolean function (m inputs, n outputs) can you efficiently encode it into Cu? Efficiency is concerned with the quantity of wire cells, the surface and the time to travel from the input to the output of the circuit. This involves proper logic synthesis, placement and routing algorithms adapted to this CA world.

Bibliography

Nicolas Ollinger. Universalities in Cellular Automata. In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 189–229. Springer, Berlin, 2012

Mis à jour le 25 février 2026