Random Explorations in Automata Theory
Gary J. Shannon
Mar. 2, 2003

States, Real and Virtual

The simplest automaton has two states, on and off.  When more states are added the number of possible rules explodes and the size of each rule increases as well. One way to explore a larger universe of rules without facing the explosion of possible rules with higher states is to introduce virtual states.

a virtual state is a ghost state in a 2-state machine.  It has a fixed life time, usually 1 or 2 generations, but possibly more.  While a cell or node is in a virtual state that node will not be updated and the virtual state will count as 0 when the neighborhood count is tallied. The virtual state is only entered when a node in state 1 is instructed by the rule to transition to state 0.  Instead of transitioning immediately to 0 the node transitions to the virtual state which will, after some fixed number of ticks, transition to 0 spontanteously.  No rule mentions the virtual state either as an input condition or an output result, although all transitions from state 1 to state 0 imply that the virtual state will be entered rather than entering state 0.

This has the effect of causing a refractory period in each node during which time the node is unable to respond to the rules in any way.  In other words, when a node in state 1 returns to state 0 it requires a rest period before it is able to return to state 1 again.  While the introduction of the virtual state does not alter the total number of possible totalistic rules in a 2-state automaton it does greatly increase the number of interesting rules in that universe of possible rules.  Even a rule as simple as "nodes with 1 neighbor go to state 1, all others go to state 0" will produce interesting behavior as shown in animation 1.  Here state 1 is represented by black and the virtual state is represented by grey. The matrix is a simple ring, equivalent to a 1-dimensional cellular automaton with the ends connected.

Animation 1.

State 1, the black dot, circulates in the ring in one direction only because the trailing virtual state blocks it from propagating backwards.

Now we will explore the introduction of a virtual state into an ordinary 2-dimensional cellular automaton.  The rule used in these examples is that an empty cell gives birth to state 1 if and only if it hase exactly 2 neighbors in state 1.  All other conditions result in state 0.  Animation 2 shows a "photon", the smallest particle that can travel at the speed of light in this cellular universe. (Look here for some examples using virtual states on a tubular toroidal grid.)

Animation 2. The Photon.

Using the same rule that state 1 happens only when an empty cell has 2 neighbors we can even find configurations that behave similar to the game of life glider as seen in animation 3.

Animation 3. The Glider.

== UNDER CONSTRUCTION. Much more to come ==