Over the weekend I spent some time surfing through Googles of the usual set of topics, wrapping my head around the whole world of random generation again, and I stumbled upon Wireworld. I remember playing with Conway's Game of Life in college, and since then I've dabbled a tiny bit in cellular automata, but somehow I missed this one. Which is sad, because this one is pretty cool.

Like many common cellular automata, it involves an infinite plane of square grids (although, of course, most simulations aren't infinite after all) wherein each cell can hold 1 of 4 states. A small set of rules defines the state that a cell assumes on the next generation, based on the current generation. In this case, the cell rules are as follows:

A cell of state 0 always stays as state 0, and never changes.
A cell of state 1 always changes to state 2.
A cell of state 2 always changes to state 3.
A cell of state 3 remains state 3 unless it has 1 or 2 neighbors of state 1, in which case it becomes state 1 itself.

As in most interesting cellular automata, while the rules are simple, the behaviors that emerge can be extremely complex, based on the initial starting gate. The above-linked page likens the 4 states to these 4 settings:

0 = (blank, non-conducting)
1 = electron 'head'
2 = electron 'tail'
3 = conductor

Following from these associations, some simple circuits can be assembled. An electron 'pulse' is comprised of a head/tail pair on a copper conductor. As the CA propagates through succeeding generations, the electron pair translates along the copper conductor in the direction of the 'head'. Some pretty interesting behavior evolves if cells in the conductor state are structured in appropriate patterns.

The page enumerates several increasingly-complex examples, beginning with a structure that emulates a diode in an electrical circuit (allowing an electron pair to propagate through it in one direction, but blocking it from the other) and ramping up to an implementation of a ROM block that can store and retrieve bit patterns. The final culmination of the explanation on the site ends with this:



It's a fully fledged computer, programmable via a 1-instruction set with special-case registers for various actions, including the display of numbers on a series of 7-segment LED displays. The image of the CA above is the simulation running a 'program' that iterates through the set of odd integers (and the integer 2, to begin with) testing each one to see if it's prime, and displaying the calculated primes in succession on the LED display. It includes some pretty heavy duty functionality, including a Binary to BCD encoder, the aforementioned 7-segment displays, an ALU, a program counter, readable/writable registers, and so forth. Pretty amazing, considering it is based simply on the 4 state rules above.

The site contains a link to a Java version and a much more interesting link to a Flash version that let you see the CA simulation in action.