Described here is a infinitely-configurable
universal (Turing machine)
Its equilateral triangular cells tile the plane and are isotropic; the
transitions for each cell depends only on (itself and) the
multiplicities of the values in the three cells directly abutting it.
Generations are discrete; all cells switch to their successor states
Table 1 - State Transition Rules
|[g]||440||0||->||4||(gap repair, collision, and junction)
|[m]||100||4||->||1||(repair wire end; period 3 oscillator)
|[n]||000||1||->||4||(repair wire end)
There are 10 possible combinations of states of three neighbors.
Times the 3 possible states of the cell itself yields 30 possible
transitions. Only the transitions which change the cell's state are
listed; the others leave it unchanged.
In the automata diagrams state "1" is coded by red (half-size
triangle), state "4" by black, and state "0" by white. In figure 1
nine successive generations scanning from the top left to right are
shown. Subsequent figures show just the initial state and are linked
to PDFs showing one generation per page.
There are interesting symmetries in the application of these rules to
the examples here.
- "4" never becomes "0";
- "1" never stays "1"; and
- "0" never becomes "1".
Figure 1 - Signal Propagation
Rules [a], [b], and [c] are needed for signal propagation in wires shown
in figure 1. Wires can bend 60 degrees. A bend behaves like a straight
wire because the rules do not distinguish between one neighbor and
another. The minimum radius is 2; a turn can wrap around the minimal
Two signals which meet on a wire annihilate each other. Both possible
phases of such meetings are shown in figure 2. Notice that the center
triangle of the upper wire never changes from black. This behavior of
rule [e] will be important later.
Figure 3 shows annihilations in wiggly wires.
Three wires along different axes meeting at a single cell constitute a
junction. Due to the gap repair rule [i] and the small neighborhood,
wires must come into junctions at 120 degree angles from each other.
Additional bends can be spaced 2 cells or further from the
junction. Figure 4 shows two junctions the minimum distance apart.
Rules [d], [e], [f], and [g] give the junction the property that a
signal coming in on one leg exits via the other two; demonstrated
twice in figure 4. The minimum distance between junction points such
that they don't interfere is 3.
Two signals arriving simultaneously at a junction annihilate each
other as shown in the top of figure 5.
Rule [i] allows the junction to function even if the signals are one
step out of phase on arrival. The result, as shown in the bottom of
figure 6 is that one signal exits on the remaining leg. This is in
effect the same as if the delayed signal were delayed more than one
step; being annihilated by the earlier signal having split through the
On a wire, the "1" logic level is represented by a pulse; "0" by the
lack of a pulse. The minimum spacing between logic "1"s on a wire is
3 cells, 3 generations.
Figure 6 - Delay elements
Time delays are formed from serpentine wires as shown in figure 6.
An oscillator is formed of a wire loop and a junction. A pulse
circulates in the loop and splits every time it passes through the
junction. Figure 7 shows a period 6 clock and a period 18 clock.
Figure 8 - Hybrid Combiner
Figure 8 shows a four legged hybrid combiner. It is named
for the radio-frequency component which couples adjacent ports while
isolating opposite ports. It has the properties:
- A pulse on just one leg exits on the two adjacent legs;
- pulses on opposite legs exit on their two adjacent legs;
- pulses on adjacent legs exit on the two opposite legs; and
- three simultaneous pulses combine to one exiting the other leg.
Figure 9 - hybrid combiner
Like the oscillators in figure 7, hybrid combiners can be reduced to
the minimum hexagonal form shown in figure 9.
Figure 10 - OR and Exclusive-OR Gates
The hybrid combiner can function as an OR gate as shown in
the top half of figure 10. With a one cycle offset between (possible)
input pulses, the hybrid combiner acts as an exclusive-or gate; shown
in the bottom half of figure 10.
Figure 11 - Crossover
Three exclusive-or gates can be combined to form a crossover routing
each of two inputs to its opposite wire; shown in figure 11.
Figure 12 - Switched Clock
An oscillator with a hybrid combiner forms a startable and stoppable
clock. Period 18 and period 6 clocks are shown in figure 12.
Combining the hybrid with an oscillator in a different way creates an
inverter (a "not" gate) as shown in figure 13. The first, six, and
seventh pulses from the oscillator are annihilated.
Everything is working in precise alignment except the OR
gate, whose output pulse is delayed one cycle when the only incoming
pulse is on the lower leg (figure 10). As
the inputs to the other components must be aligned, we need a way to
synchronize pulses emerging from networks containing OR
Figure 14 - Synchronizer
The synchronizer is an inverter allowing variation of input
timing with respect to its period. Two 18-cycle oscillators feed a
hybrid combiner so that their pulses cancel on the input side and
produce a pulse on the output. An input pulse splits onto the clock
legs, but does not emerge from the output side. Those pulses meet and
annihilate clock pulses, and thus prevent the output pulse-to-be.
The two synchronizers in figure 14 receive pulses at different times
showing the full 12-clock (out of 18) window for inputs to suppress
the synchronized output pulse. Notice that the sequence of pulses
exiting to right is the same, even though the input pulse arrivals
differ by 12 generations.
With wiring, delays, gates, crossovers, and oscillators we have all
the parts necessary to create a computer (a Turing-machine). Thus
this cellular automaton is
Figure 15 - CCITT 16-bit CRC
Figure 15 shows a reversed CCITT 16-bit cyclic redundancy check
circuit. Operating at 6 generations per bit, input is from the left;
output to the right. Every thrid generation is shown.
The machinery of mathematical proofs rarely makes practical devices.
What sort of computations is this automaton suited for?
- Acting as storage, long folded delays lines (wires) approach 1/6
bit per cell in density. Individual bit storage would require 15
cells at a minimum; a hexagon plus half of its shared 18-cell border.
- With a crossover 15 times larger than an exclusive-or gate,
bit-parallel busses would be space-inefficient. But serial logic is
small and quite well suited to delay-line storage.
Copyright 1974, 2002, 2004 Aubrey Jaffer
I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.
My actions and comments do not reflect in any way on MIT.|
|agj @ alum.mit.edu