m i n d c o d e

Back in the 90’s, I came across an Amiga 500 program that simulated a 2D cellular automaton (CA) called Wireworld. The rational behind this cellular automaton is quite simple. You start with a grid (any size you want). Each cell in the grid has four possible states: 1. Empty, 2. Electron Head, 3. Electron Tail, 4. Conductor (or Wire).

Then, given any initial set of the grid, you apply the following rules in each step:

• Electron head → electron tail
• Electron tail → conductor
• Conductor → electron head iff one or two of the neighboring cells are electron heads

Guess what? You have a turing complete automaton. Let’s look at some examples on building simple gates. First, a diode:

In this picture, Heads are blue, Tails are red and Conductors (or wire) are yellow. Let’s look at a more complex example:

Here we can see two clock generators at the upper and lower left, and a XOR gate at the center right. Can we make AND gates? OR gates? Latches? The answer is yes. Actually, there are several kinds of gates that work depending on the cycle (or frequency) of the “electrons”. You can check a whole list of discovers in this page.

Still, the most amazing thing I’ve seen accomplished since that time was a complete working implementation of a programmable RISC computer. It is just amazing to see it in action. These guys have managed to implement flip-flops, binary adders, and register banks. Ingenious!

Despite the fact that an implementation of a simulator of this automaton is quite a simple exercise, you can check here for the Wireworld computer in action, or download the Mirek’s Cellebration software which includes a highly performant simulator of this and several other 1D and 2D cellular automatas.

P.S.: This is my hundredth post :-) 

In a previous post I wrote about a prize being offered by Stephen Wolfram, the creator of the Mathematica Software and author of A New Kind of Science, to whomever proved (or disproved) the universality of a 2,3 cellular automata.

Nearly 4 months later, Alex Smith has just won the $25,000 USD prize by demonstrating the universality of Wolfram’s Turing machine in an ingenious 40-page proof.

Congratulations goes to Alex Smith for this amazing scientific contribution.