Wireworld!

I love cellular automata. As I said in my post about Conway's Life, it's fascinating to see how utterly trivial rules can result in the astonishingly complex behaviors. Today I'm going to show one of my favorite CAs: WireWorld.

Wireworld is a very simple cellular automaton that can be used to simulate digital circuitry. Aside from the basic fascination of being able to build interesting things using CA, watching wireworld in action can actually help you understand how a computer works!

Wireworld uses four colors: black, copper, green and red. Black is the background; copper is wire; green is the leading edge of an electron, and red is the trailing edge of an electron.

There are only three rules in wireworld:

1. If a cell is green, next step it turns red.
   
2. If a cell is red, next step it turns copper.
   
3. If a cell is copper and it has one or two neighbors that are green, next step it turns green.
   

That, my friends, is it. Everything you need to build a complete simulation of the PowerPC that runs my computer, if you were insane enough to do it.

Let's look at how you build "circuits".

Clocks

One of the things that you almost always see in wireworld is a clock circuit. This injects electrons into a wire at regular intervals. Basic clocks in wireworld look like rectangles with their corners truncated; the period between injections of an electron into the wire is the number of cells in the clock loop. Here's a sequence of snapshots of a clock in action:

Diodes

Another simple circuit we can do is a diode: a diode is a basic electronic circuit that lets signals through in one direction, but not in the other.

Here's the sequence for a wire diode with an electron moving in the direction permitted by the diode:



And here, we reverse the diode, so that it blocks the electron:



When it moves in the direction permitted by the diode, the electron comes up a single wire to the point where the diode starts; it turns the three cells on the edge of the diode green; and then the two wires coming out of the diode each have two green neighbors, so they turn green. Then the wires rejoin - and the joint winds up with two green neighbors, which turns it green.

When it moves in the opposite direction, the signal gets to the diode branch, and turns both wires green; the two green wires make the three cell bar of the diode all turn green, so the wire exiting the diode has three green neighbors; it only turns green for one or two, so the signal stops.

Or Gate

Wireworld gets really interesting when you can start working with logic gates. For an example, here's an or gate, with a signal coming up one branch:



That's enough for today: drawing these things by hand is a serious pain in the neck. When I have some time, I'll write a java applet that I can use for running cellular automata on the blog; things will be rather clearer if you can see it in action.

In the meantime, if you're interested in wireworld, take a look at this: someone build a wireworld computer that calculates prime numbers and displays them on an LED-like grid!