A second-order reversible cellular automata with four states.

Stable gliders are three-cell "ants" moving in vertical and horizontal directions with unit speed with reflections, collisions and splitting. Unlike wireworld, the ants can be used for construction of different kinds of "wireless circuits."

There are four states: 0 (empty, white), 1 (red), 2 (green), 3 (blue).

• A cell with state 0 or 2 (white or green) is called "even"
• and a cell with state 1 or 3 (red or blue) is called "odd"

A step may be divided into two stages:

First stage:
Mark all cells satisfying two conditions:
(1) total number of odd cells in four closest positions (up, down, left, right) is one or two,
(2) cells in four diagonal positions are even.

Second stage:
For unmarked: exchange red and green cells (1<->2).
For marked cells: change empty into red, red into blue, blue into green,
green into empty (0->1->3->2->0).

• Forum post with example programs
• A Two-dimensional reversible cellular automata

incoming reversible computing