Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 22, 2003
Last Updated: Mar. 22, 2003

CA Logic Gates: Adding a Dimension

[Note, the examples in this section were produced with my Win/95/98/2000/XP Bead Racer program which is available for download here.]

This section explores a major modification to the original Bead Racer/Pipeline rule set for the express purpose of making the building of larger digital circuits more practical. The first of the two changes is the addition of a second layer to the CA grid so that pipes can be made to cross over and under each other effortlessly. The second change is the addition of two new states. A gold bead remains gold until touched by two red beads, whereupon it turns blue for one clock tick. An empty cell with a single blue neighbor spawns a red bead.  These additional two states greatly simplify the building of the most important logic gates as shown below in figure 1.

Fig. 1. Some standard logic gates using the extra "gold" state.

The addition of the second layer also simplifies circuit design since signals can be routed across each other without the need for complex crossover circuitry. Here is a 7-bit binary counter, for example, with latched output that maintains the stream of photons for each output bit until that bit is changed.

Fig. 2. A 7-bit binary counter showing
an output count of 0100101 = decimal 37.

Notice the tracks or pipes in light green. Those are on the second layer and have no effect on the first layer photons. The black dots are feed-through cells that see all neighbors on both layers. The Bead Racer program allows either layer to be brought to the top for editing. The structure on the back layer at the bottom of the picture is a pulse generator that emits a single photon every 48 clock ticks (every 16th photon from the battery). The Bead Racer save file for this counter can be downloaded here. (Requires Version 1.1 or later of Bead racer)

== UNDER CONSTRUCTION while I dream up a cool circuit to build ==