A year ago I wrote about “digital ants”, reversible cellular automaton with simple three-cells “gliders” (“ants”) moving freely in vertical and horizontal directions (with unit speed) with different types of regular collisions, reflections, splitting, as well as generation of both oscillating and chaotic patterns .
Yet another property I would like to determine could be computational universality. In irreversible computation AND, NOT gates are enough to construct any circuits. It may be also enough a single gate for universality, e.g., single “ANT” gate
A ANT B = A AND NOT B
is universal, because
1 ANT B = NOT B, A ANT (1 ANT B) = A AND B.
On the other side, it is well known, that reversible circuits are less trivial and it is always necessary to use gate with three input-output wires such as Toffoli or Fredkin gate. I did not have any success yet in implementation of Toffoli or Fredkin gates with digital ants (update 7/08: already succeed with Fredkin gate), but realized that ANT gate mentioned above may be treated quite naturally.
Indeed, if 0/1 values mean respectively absence/presence of ants, the truth table of ANT gate
may be explained in the following way: there are two intersecting paths and an ant entering the first one (input) may reach output only if yet another ant does not appear on the second path. But ANT gate is not reversible. It even does not have equal number of inputs and outputs and not only that. It may not be extended to reversible gate by attaching second output; otherwise it would contradict to well-known fact, that minimal amount of input/output wires for universal reversible gate is three.
Concrete example of the gate reproduced on the picture gives some clarification – in fact, instead of single output there are three ways out!
It may look a bit complicated in comparison with explanation above due to “zigzag” of first path for intersection with the second one and “oscillations” of second path for synchronization of ants motion.
The simplified scheme of such gate might be
i.e., (A, B) → (A AND B, B, A ANT B)
In such a case outputs values are enough to restore initial A and B, but number of inputs and outputs is not equal again! So the scheme again could hardly be treated as reversible gate.
What is the problem? Let’s apply any combination of ants to inputs and consider output values:
(0, 0) → (0, 0, 0); (0, 1) → (0, 1, 0); (1, 0) → (0, 0, 1); (1, 1) → (1, 1, 0).
If we run cellular automaton backward, all fine only for given output triples (see demo 28/07):
(0, 0, 0); (0, 1, 0); (0, 0, 1); (1, 1, 0).
What about other combinations such as:
(0, 1, 1); (1, 0, 0); (1, 0, 1); (1, 1, 1)?
We may apply these combinations in backward either to observe dynamical patterns which may not be described in a reasonable way via some circuits.
Anyway, the configuration above is an evidence that irreversible circuits may be used for implementation of universal computation on reversible cellular automaton either with initial version of universal 2→1 ANT gate or with extended 2→3 version with implementation of ANT, AND gates in single run.
The gif-animated picture represents circuit with three gates on a torus board. Three possible combination of inputs are presented (1,1); (1,0); (0,1), because (0,0) is simply absence of ants. Only combination (1,0) produces value on third, A ANT B output and the value is returned into first input with special loop synchronized with full period of motion of other pairs along the torus.
Experiments with the digital ants may be performed with rule file in archive from link attached to old post. The zip archive should be opened and used with Golly program. The “inversion of time” for such automaton may be performed by exchange of red and green cells (implemented by reverse-all.py Python script in the archive).
Update 28/07. Yet another demo: “There and back again.”
(1, 1) ↔ (1, 1, 0); (1, 0) ↔ (0, 0, 1); (0, 1)↔(0, 1, 0).
Update 7/08: success with Fredkin gate.