Previous Back to index Next

The Life computer

1. Logic gates

It is possible, in fact it is fairly easy, to create logic gates for these streams of gliders, using only glider guns and eaters. We make a NOT gate simply by aiming a gun's output at the data stream; any gliders in the stream will destroy the gun's glider, and any gaps will let one pass.

An AND gate is made by arranging that either glider stream is destroyed unless the other stops the control stream from destroying it. This also requires an eater to mop up any gliders from the gun that didn't destroy a data-carrying glider.

An OR gate is made by checking whether a gun's stream has been intercepted by a data stream – if it has, another gun's gliders pass through (A and B = true); if not, this gun's stream is intercepted by the stream of the first gun so that A and B) = true.

On the following page are diagrams of these three gates. The plane has been turned by 45° for ease of reference. In a circle, a G indicates a glider gun and E an eater; arrows are glider streams; A and B are input streams; and O is the output. Star shapes represent annihilation reactions.

A NOT gate.
An AND gate.
An OR gate.

Note that, if we so desired, we could combine the AND and OR gates and take both results from the same gate at a time, simply by replacing the eater in the AND gate with whatever we wanted to handle that data.

2. Making a thin gun

The ordinary Gosper gun creates a glider every 30 generations, so that there are 7.5 spaces between each glider. This can cause some phasing problems as not every glider is in the same state at any given place. Also, it's not possible to interleave two glider streams as they would inevitably collide. To solve this, we use the kickback reaction to remove every 4th glider so we have the stream 111011101110... Then we complement this using the above NOT gate to give the stream 000100010001... which is the same as the usual Gosper gun stream except at ¼ of the density. This allows 2 streams to be interleaved without colliding. Here is a diagram of the mechanism:

3. Further computing

Up until now data streams have been only a single series of gliders, with no means of copying them. It is possible, however, to copy the stream and feed it into something else, unmodified, although this does require the data to be in a rather less simple format than a simple binary number.

It is also possible to create memory for the computer using one (or both) of two methods: circulating loops of gliders (which would have limited capacity and would eventually overrun), or blocks whose distance from the computer determines the value. It takes a lot of effort to arrange all this, but it is possible. This proves that Life is universal, allowing implementation of a universal Turing machine, capable of any calculation that any other Turing machine is capable of.

Previous Back to index Next
Copyright © 2004
Peter Berry