Wireworld++

Several years ago I discovered the wonderful world of cellular automata.

After some Googling I discovered a cellular automata called Wireworld that is designed to simulate electronic circuits. Each of its square cells can be in one of four states, “empty” (which always stays empty, and is shown here in black), “electron head” (which subsequently turns to a tail, and is shown in blue), “electron tail” (which subsequently turns to wire), and “empty wire” (which remains wire unless exactly 1 or 2 of the 8 neighbors is a “head”, and is shown in orange.) Have a look at the Wikipedia page on Wireworld for more details.

Almost simultaneously with that I discovered a magnificent computer constructed in Wireworld by David Moore and Mark Owen. They also have a rudimentary introduction to Wireworld construction on their website along with an overview of their computer – http://quinapalus.com/wi-index.html. The link to Julien Thevenon’s reverse engineering is down, but after some more Googling I found it buried at pages 120-164 of http://1010.co.uk/org/erdsir_modes_reader.pdf. I have extracted the relevant pages here so you don’t have to scroll, and in case that goes down too.

Here it is, displayed using Chris Rowett’s LifeViewer: (and the RLE file for Golly: quinapalus_primes.rle)

I cobbled together a small Wireworld simulator in Processing, and made some investigations and modifications to the Quinapalus computer. I am not going to bother posting that anywhere because it is really slow, the graphics are laggy, and you can’t make edits mid-simulation. I ended up converting everything to Golly format. (If you don’t know what Golly is, it’s a cross-platform general purpose cellular automata simulator that uses Bill Gosper’s ingenious Hashlife algorithm to run patterns insanely fast. Highly recommend it.)

Unfortunately, the Quinapalus guys did a pretty darn good job of optimizing their computer. Dissatisfied with the massive loops of electrons I searched for another computer in Wireworld and instead discovered another rule. The Wireworld++ rule, as described in the paper by Gladkikh et al (local copy), is a fusion of two “flavors” of Wireworld into one another: a “strong” wireworld and a “weak” wireworld. With one flavor only it behaves exactly like regular Wireworld. But where the two flavors touch it enables creating some very tiny logic gates – two strong wires touching a weak wire form an XOR gate, and two weak wires into a strong wire form an AND gate.

Here is the Wireworld++ rule file for running it in Golly: Wireworld++.rule The top also contains a Python function that was used to generate it.

And here is a comparison of the Wireworld++ AND and XOR gates (on the left) along with their conventional Wireworld counterparts (on the right), hooked up to period-24 loops that test all the possible inputs (00, 01, 10, and 11) at period 6:

Notice how much smaller the Wireworld++ gates are compared to their Wireworld counterparts. All of the constructions discussed in the original paper work, and are smaller than their Wireworld counterparts.

Crossovers

One of the focal points in the Wireworld++ paper is the tiny wire crossover. However, it isn’t a double channel crossing, meaning that if two signals come in at the same time, they will crash into each other, and one or both will be lost. The equivalent Wireworld crossing is the double-ANDNOT gate, and while bulkier, it still suffers from the same problems:

A true double-channel crossing is made with three XOR gates like so:

and in Wireworld:

Knowing how small the XOR gate is in Wireworld++, I figured the crossover could be made much smaller – and indeed it can:

However after playing around a little more I made two iterations that were successively smaller:

Multiplexers

Looking back at the Quinapalus computer, I saw one big place where it could be optimized: the multiplexer that loads the new data into the memory loops.

The multiplexer they used was wired like this:

In this demo, you can see the loop starts out originally with 1100 in it, and then 1010 is written to it.

(The loop was originally period 96, to fit 16 bits, but I shortened to to period 24, for the sake of brevity.)

After some work, I reworked the multiplexer to use this design:

and the multiplexer was able to be shrunk to this:

While I was at it I also made a tiny demultiplexer too:

Adder

The next part of the computer that I improved was the serial adder.

The original adder, adding 3 (0011) on the top + 6 (0110) on the bottom:

The only problem with this is because the carry clock has an ANDNOT gate to clear it, a NOT gate is needed in the middle – which requires an always-1 producer, so input signals must be synchronized with the loop. Here’s what happens if they don’t get synchronized – the carry clock gets ‘stuck’ on and produces 1111111111111111111… infinitely:

My improved adder, of course, takes advantage of the tiny 3-cell AND gate of Wireworld++ that can be welded into the carry loop:

Because there is no loop, the signals only need to by synchronized with each other, and not also the adder itself.

Incrementor

The incrementor is simply a pared-down adder, that adds 1 to a number when it is triggered. It is composed of a XOR gate and a carry clock. Here is the standard Wireworld version incrementing 7 (0111) to 8 (1000):

Naturally, the Wireworld++ version is smaller:

And combined with loop that repeatedly increments the value in the loop, it makes a very compact high-period clock, outputting a signal whenever the carry overflows on the most significant bit. For period-6 data, a loop of $n$ bits will form a clock with a period of $6n2^{n-1}$, so with a 6-bit loop, it forms a period-1152 clock:

Conclusion

At this point, I didn’t really bother making any more Wireworld++ constructions. Wireworld++ isn’t the limit for these kind of cellular automata.

Lode Vandevenne has variants of Wireworld with three and four “flavors” of wires – called, pretty simply, WireWorldRgb and WireWorldRYGB, and a 32-state wire rule called LLLL which also has the interesting property that signals can stretch to any length, composed of a head, some amount (or none) of “on” wire, and a tail, separated by “off” wire. (My experiments have shown that the “on” wire and “head” can be the same state and it works fine.)

Github user @HactarCE has also created another WireWorld variant called DECA and implemented part of a Picoblaze microcontroller in it, as well as another cellular automata called NoTimeAtAll which has the equally interesting property that signals stop and wait when they get to a junction and their partner signal is late – so only the topology matters, and timing is largely (but not completely!) ignored.

In hindsight I should have probably split this post up into smaller posts in a series, but I’m too lazy to split it now.

Related Posts

• Langton's Ant Music