Fig. 1. Photons in the wild.
Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 3, 2003
Last Updated: Mar. 22, 2003
Building Logic Gates with a Pipeline CA
This CA can be explored with M-Cell or with my own Windows Bead Racer program which can be set to run these rules, the Bead Racer rules, or the Wire World rules. Download the Bead Racer program here.
There is a class of automata which, unlike their free-roaming cousins, are doomed to spend their existence confined to pipes or wires. An early CA called Wire World (by Brian Silverman in 1987) was of this type. My own Bead Racer CA is also of this type, but uses one more state and a slightlty more complicated rule. Rather than using the wide open arena of a conventional 2-dimensional automaton, members of this class operate within the confines of containment structures such as pipes and chambers of various sizes and shapes. These confinement structures are built from cells that contain an additional state that never changes and does not affect the states of the cells adjacent to them.
In addition to this extra state the automata has 3 states. State zero is an empty cell. State one is represented by a black cell and state 2 by a grey cell. Each of these automata has a set of fixed rules governing the death of black and grey cells but may have different rules regarding the birth of black cells. The fixed rules are:
Since the third state never contributes to the birth of a cell, and since it's rules are fixed I have refered to this state as a virtual state.
The rule set we will investigate has the fixed rules above plus the additional rule that an empty cell gives birth to a black cell only when it has exactly 1 or 3 black neighbors. Empty cells that have exactly 2 neighbors or that have more than 3 neighbors will remain white.
If this rule is turned loose in a open universe a single live cell spreads out into a symmetrical pattern that expands at the speed of light and eventually fills the entire grid. Figure 1 shows the pattern reached after 20 generations. If several starting cells are used the pattern still grows at the speed of light and still maintains a roughly square outer boundary but the inside of the structure becomes quite chaotic.
Fig. 1. Photons in the wild.
Clearly this is a rule that needs to be brought in from the wild and tamed. The first step is to confine the photons to pipes. Using these rules a photon made of a black cell adjacent to a grey cell will propagate down a 1-cell wide pipe at the speed of light.
Before we can investigate the properties of various confinement devices we will need a steady source of photons to feed into the device under investigation. The device shown in figure 2 will emit a photon every 3 ticks of the generation clock. We can call this device a generator.
Fig. 2. The Generator.
Pipes and Corners
The next question to arise concerns the manner in which photons propagate through pipes of various dimensions and geometries. We observe that when a pipe 1 cell wide turns a corner that the photons are able to negotiate the turn and continue in the new direction (figure 3).
Fig. 3. Turning corners.
When turning a corner an extra block can be put in the corner cell without changing the behavior. This block becomes necessary if it is desired to make an abrupt U-turn since the photon will not negotiate such a sharp turn without such a block in each corner of the turn. (See figure 3.1)
Fig. 3.1. The U-Turn with corner blocks.
We can also use diagonal pipes which are also handy for creating delays to insure that photons arrive at the right place at the right time.
Fig. 3.2. The diagonal pipe.
If we feed a stream of photons into a pipe with a width of 2 cells we discover, as in figure 4, that photons will not propagate in a pipe of that size. In fact no configuration of cell states will survive for long in a width 2 pipe.
Fig. 4. Width 2 pipe.
Stair-step pipes behave oddly. Some will pass all the photons, others will pass only some or even none of the photons. A stair 4 steps high (figure 5 top) will pass every photon, but a 3-step stair (figure 5 middle) won't pass any photons from the stream. And stranger still, the 2-step stair only passes every other photon. (Figure 5 bottom)
Fig. 5. Stair step pipes.
Three Cell Pipes and Backwaves
If the stream of photons is fed into a pipe that is 3 cells wide the first two photons are converted into heavier particles (Figure 6 at A and B) that continue to propagate, but as they move they emit backward photons (Figure 6 at E, for example) that disrupt the incoming photons and prevent any additional photons from entering the pipe. As long as this back wave is maintained it seems that no further photons can enter the pipe from the source without being annihilated by the reflex photons in the back wave.
However, since the heavy particles that are emitting the reflex wave are moving in a direction opposite the emitted photons those photons experience a doppler shift and are stretched to a wavelength of 4 cells as opposed to the 3 cell wavelength of the incoming stream. Eventually, 45 cells behind the leading edge of the heavy particles, (At C in figure 6.) a photon continues to propagate in the forward direction down the center of the pipe, surfing the flanking reflex waves as if in a virtual pipe or wave guide. Unlike the leading heavy particles, this particle maintains its identity as a photon. Another 12 cells behind that photon, at D in figure 6, a second photon follows suit and also surfs the virtual wave guide in a forward direction.
Fig. 6. Backwave propagation in a 3-cell pipe.
Notice also in figure 6 that the reflex photons have been phase-shifted by 180 degrees each time a photon surfs them. Compare the blue marks at the top of figure 6 which show the phase of the reflex photons before encountering the forward photon at C. What was the space between reflex photons is now the photon and what was the photon is now the space. Finally, 48 cells behind the leading photon of the pair of forward photons we find another pair of forward photons, F, surfing the reflex wave, again separated by a distance of 12 cells from each other.
After that a pair of forward photons will be found propagating forward down the center of the pipe every 48 cells behind the leader of the previous pair, and always with a separation of 12 cells. The transient response to the initial introduction of photons has settled down and the pipe continues to carry 2 forward photons along every 48 cells of its length.
When a width 3 pipe is closed off at the opposite end the back waves cancel out the incoming photons and the pipe alternately fills and empties. Figure 6.1 shows the pipe full on the right, while the left shows it a few cycles later after it empties and begins a new cycle.
Fig. 6.1. Periodic filling of the chamber.
Chaotic Resonators
As it turns out a 3-cell pipe cannot turn a corner without disrupting the propagation of the particles and other photons traveling down the pipe. The result is chaotic turbulence within the pipe. Unlike a terminated straight pipe, which oscillates as it fills and empties of forward particles and back reflex wave, the corner pipe does not oscillate and the backward moving reflex waves vanish to be replaced by asymmetrical and uncoordinated behavior as seen in figure 7.
Fig. 7. Turbulence in a bent 3-cell pipe.
Since 3-cell pipes are of little use as transmission conduits we might take a look at what other uses they might serve. We have observed that all propagation in the 3-cell pipe is symmetrical about the axis of the pipe, with reflex photons always moving in pairs on opposite walls and surfing photons always riding down the axis. Terminating the pipe results in setting up a characteristic resonant frequency at which the pipe fills and empties in response to the stream of incoming photons. The use of a 3-cell pipe as a resonating chamber of some sort certainly sounds like a possibility.
Turning a corner disrupted the symmetry of the propagation pattern and introduced chaotic turbulence. We can further observe that anything introduced into the 3-cell pipe that disturbs its symmetry will result in turbulence, whether the anomaly is a single cell barrier inside the pipe or a single cell notch in the wall of the pipe, indicated by the arrows in figure 8. A 3-cell pipe with an asymmetry is no longer resonant at a fixed frequency as a plain closed pipe is. This suggests at the very least that a finite length the 3-cell pipe with one or more asymmetric disruptions might serve as a source of noise or random photons. Figure 8 shows two examples of pipes with flaws.
Fig. 8. Flaws in the tube cause turbulence.
Once it has been filled with a random initial state and provided with an output pipe the inside of the resonator will churn around emitting photons at random intervals. After a while, however, the state of the chamber is likely to enter a short repetitive cycle and the output will no longer be random. The easiest way to forestall this problem is to drive the chamber with a photon generator, or to cascade two such chaos chambers feeding the first from the photon generator and feeding the second with the output from the first. See figure 9 for some possible configurations.
Fig. 9. Cascaded chaotic resonators generating random photons.
The use of chaotic resonators will need to be investigated further before any solid conclusions can be drawn about their randomness.
Tuned Resonators
Returning now to the property of resonance we might ask what the resonance properties of a finite length 3-cell pipe would be if pipes were attached at both ends. If we build a resonator 4 cells long and feed a stream of photons into one end we will observe that only half as many photons emerge from the exit pipe at the other end. Notice in figure 10 that the steady stream has been chopped and consists of a pair of photons followed by 2 photon's worth of empty space. We can describe this by saying that this resonator has a period of 4 and an output of 1100, in other words, the four bit pattern 1100 1100 1100 ... will repeat every 4 ticks of the clock.
Fig. 10. A Length 4 cavity resonator.
The period happens to be equal to the length of the resonator but this is not always the case. In fact a resonator of length 9 has a period of 19 while a resonator of length 10 has a period of 5. There seem to be few useful resonators since most of them output rather odd sequences of photons and gaps. (See table 1.) The size 6 resonator might be of some use as it neatly chops out every other photon emitting half as many as were put in.
Resonator |
Period |
Output Pattern |
1 |
-- |
Pass all photons |
2 |
-- |
Pass all photons |
3 |
5 |
11110,11110 |
4 |
4 |
1100,1100 |
5 |
3 |
110,110 |
6 |
2 |
10,10 |
7 |
4 |
1100,1100 |
8 |
6 |
110000,110000 |
9 |
19 |
1000110000110010000,... |
10 |
5 |
10000,10000 |
11 |
6 |
110000,110000 |
12 |
22 |
1100000011000001000000,... |
13 |
14 |
11000001000000,... |
14 |
7 |
1000000,1000000 |
15 |
26 |
11000000110000000100000000,... |
16 |
11 |
11000000000,... |
17 |
10 |
1100000000,1100000000 |
Table 1. Periods and Patterns of a few resonators.
While a resonator of length 1 does nothing by itself, if such a notch is placed immediately before one of the longer resonators it does change the period and cycle of that resonator. Adding a notch immediately after the output of the resonator has no effect.
As an aside it should be noted that all of these behaviors were observed using a generator that supplies a photon every 3 ticks. The results might be quite different using a generator with a period of 4 ticks or 5 ticks. This remains to be investigated.
Joining Pipes and Building Logic Gates
We have already seen that a pipe can turn a corner without disrupting the flow of photons in the pipe, but what happens when a photon encounters a T-joint? As we can see in figure 11 when the photon enters from the stem of the T it duplicates at the joint and continues propagating in both directions simultaneously. However, when the photon enters from one of the side branches of the T it turns the corner and moves down the stem without propagating into the other branch.
Fig. 11. The T-joint.
The fact that the behavior of the photon is different depending on the direction it is travelling in the T implies that 2 T-joints could be configured to form a diode. Such a diode configuration is shown in figure 12. Notice that in figure 12A the photons enter the diode in the correct direction and pass through without disruption, but in figure 12B, entering from the wrong end of the diode, they are destroyed and do not pass through. This one-way valve device will come in handy whenever we need to insure that photons travel down a pipe in one direction only.
Fig. 12. The diode at work.
Another behavior of the T-junction is that the output from the stem will be the exclusive OR of the inputs from the two side branches. If photons arrive from either of the two branches they will emerge from the stem. If, however, no photons enter, or if photons enter from both side branches simultaneously then no photons will emerge from the stem. This is illustrated in figure 13.
Fig. 13. The Exclusive OR.
Notice that the input from branch B has a pattern of two photons followed by a gap and, since the input at A has no gaps, the output has the complementary pattern of two gaps followed by a photon.
In figure 14 we have combined the exclusive OR with a generator to form an inverter. This device will emit a stream of photons as long as no photons are input to it. When input photons enter the device then the outgoing photon stream will stop until the flow of input photons is again cut off. Thus it will emit an output opposite to its input.
Fig. 14. Invertor with
self-contained generator.
One detail that should be mentioned is that care must be taken to keep the photons from all inputs in phase with each other. Unpredictable operation will result if this precaution is not observed. This can be accomplished where necessary by adding an extra bit of length to one of the pipes by introducing a slight detour along the way.
Coming up on the next page, a differentiator, or edge detector, a memory element, and a way to make pipes cross over each other, just to mention a few of the goodies.