Conway's
|
Stable technology
Contents
Technology in Life usually falls into two main categories:
stable and periodic. Periodic technology has been known
since 1970 with Gosper's glider gun. Stable technology
didn't fully emerge until 1996, but then a great discovery
in 2001 allowed lots of new devices to be built. In this
article I will explain the history of stable technology,
as well as some of the machines that have been built based
on it.
The Herschel is a small object in life that consists
of seven live cells. It forms naturally, and eventually
burns out into two gliders, two blocks and one ship.
However, it can be perturbed by catalysts to alter its
evolution.
It is produced (along with a block) as the 20th generation
in the evolution of the B-heptomino, a common arrangement
of cells that lasts for around 150 generations before
stabilising. This shows the evolution from B-heptomino to
Herschel.
The Herschel naturally emits a glider shortly after the
standard phase depicted above. If the Herschel could be
re-routed back to its original position, it could be made
to periodically emit gliders. The first conduit (pattern
that perturbs a Herschel into producing another Herschel
at a different location/orientation) is the 64-generation
right-turn conduit shown below:
The green Herschel represents the input, the red Herschel
represents the output and the black catalysts form the
permanent part of the conduit. This is a very basic conduit,
as well as being the first one discovered (by David J.
Buckingham). Since the conduit simply performs a 90° rotation,
4 copies of the device can be combined to yield an oscillator.
Furthermore, the Herschel emits a glider, which is not eaten,
allowing it to escape cleanly. This means that the device is
not simply an oscillator, but a gun. It operates at p256, and
is nicknamed "The Machine Gun".
This pattern was created in 1995, again by David Buckingham.
Here is the pattern represented as RLE (run-length-encoded)
format. This can be read by most Life programs:
Buckingham later discovered 7 additional conduits, and since
then another 8 have been found independently. These can be
used to make other guns, for example the P448 gun below:
Guns with all periods equal to or greater than 62 can be made
from these stable conduits, and a few others below that period
can be made by using periodic components.
Here I will show several of the conduits that can perturb a
Herschel cleanly to produce another Herschel (and in most cases
surplus gliders). The F171 is one of the more interesting
examples, as it is made out of just one component. It was
discovered by Brice Due in 2007 using a search program.
The Fx176 conduit has two distinct sections, with an
intermediate pi-heptomino stage:
The following conduit is peculiar in that it uses a catalyst
block in two completely dissimilar ways. The first time it
simply deflects the chaos, and the second time it is absorbed
and re-created in its original position.
Note the large catalyst at the top-right. This is called an
eater2, and is extremely versatile. It can absorb a glider on
any of four adjacent paths!
The smallest conduit is the Fx119 forward flip. The catalysis
is done completely on one side of the Herschel, and this conduit
fits into awkward places where none of the others can do. It is
also the basis of an incredible edge-shooting device.
This short Herschel track, made of two Fx77 flips, can be used as
a basic toggle switch. This makes it useful for constructing more
complex logic gates and computational devices.
Even more useful than a stable Herschel conduit would be a stable
glider reflector. This could be used to rephase, position and
orientate gliders, without needing to oscillate. The first attempt
at finding a stable reflector didn't succeed, but it did result
in an equally impressive device - a stable glider RS flip-flop.
This can be used to store a bit of information, so a memory unit
could be built from them. Here is the device: (by Paul Callahan)
Fortunately, Buckingham's Herschel conduits can help. Paul
Callahan found the following reaction, where a glider is
converted into some chaotic mess, creating a surplus beehive.
But what use is that mess? None in its current state, but it
can be perturbed by two blocks to form an R-pentomino.
An R-pentomino naturally forms a b-heptomino, plus some mess
that reacts with it. Fortunately, a boat can remove the mess,
allowing the useful B-heptomino to escape.
The transparent block reaction can be used to transform a
B-heptomino into a clean Herschel, without leaving any blocks
behind. This is done with the help of a snake or eater.
The entire conduit is shown below:
Now that we can produce a Herschel, maybe it can be re-routed
to delete the annoying beehive. Paul Callahan demonstrated
this in 1996, when he built the first stable reflector:
It is very large, and very slow. It takes a total of 4840 ticks
before it is able to accept another glider. It still works, but
at its current size it won't be very useful. Callahan soon
managed to optimise it:
He improved yet again, by using Buckingham's conduits more
imaginatively. This time he knocked the repeat time down to just
894 ticks. (October 1996)
Later he managed to optimise it further, producing a repeat time
of 850 ticks. Dean Hickerson made the next great leap, when he
used a custom still-life to allow a tighter compression of the
conduits. This improved it to 747 ticks: (November 1996)
David Buckingham used a different initial reaction based on a
glider hitting a boat. This produced a reflector that is dis-
similar to all of the previous ones. (May 1997)
As you've seen, the initial sequence of the previous reflectors
is composed of four main sections:
Stage 0: glider -> mess+beehive
Stage 1: mess -> R-pentomino
Stage 2: R-pentomino -> B-heptomino
Stage 3: B-heptomino -> Herschel
Stephen Silver found an interesting way of combining stages 2 and
3 of the initial sequence, making a fast R-pentomino -> Herschel
converter. Here is the converter, showing the input and output:
The converter can be used to make an improved stable reflector,
with a recovery time of 623 (October 1997). This is fast, but it
can still be improved. This is the complete reflector in RLE format:
In November 1998, Paul Callahan managed to combine all four stages of
the initial sequence into just one direct conduit:
This lead to him breaking the record again, with a stable reflector
with a recovery time of 575 ticks. It has a direct Herschel output,
which is turned into a glider on the edge of the pattern in the
example below:
This was soon beaten by Stephen Silver, who also used that same
initial stage.
This record of 497 ticks has not been beaten by any other 90°
reflectors, until 24 January 2009 when I managed to make a
staged-recovery reflector which recovers in just 466 ticks!
However, a superb 180° reflector was found by Dave Greene:
This reflector uses the very first initial stage found, but it
only uses section 0: glider -> beehive + mess. Dave then found
a way of perturbing the mess to produce another glider, which
happens to be on the correct lane for deleting the beehive. This
won two independent $100 prizes, because of its fast speed and
impressive compactness.
The reflector recovers so fast that two gliders 202 ticks apart
can be reflected. This makes it useful in situations where the
497-reflector is too slow. It can also fit into small spaces.
Two copies of the boojum reflector can be placed back-to-back
so that the output of one goes into the input of the other.
Because it is a 180° reflector, the output of the second reflector
goes back into the input of the first. This can form all oscillators
of periods 202 or more, as long as they're not divisible by 4.
However, Dave Greene's boojum reflector, as small and fast as it
is, is still not the fastest. In 2009, I discovered a reflector
with a recovery time of just 106 generations. It is unique in
being the only stable reflector that contains only a single stage;
the catalysts act in quick succession, and no unwanted objects
are produced.
Another interesting feature of the rectifier, and the reason for
its nomenclature, is the absence of catalysts along the output
path. This makes it viable as a merge circuit, although the small
separation between the input and output paths makes it impractical
in the classical sense of a merge circuit. However, this property
can still be used. The pattern below showcases the important
features of the rectifier:
When I accidentally discovered the rectifier, I was not aware of
this ability, so just considered it to be a faster alternative to
the boojum reflector. As opposed to the boojum reflector, this
required neither skill nor computational power; I manually added
an eater3 on to a reaction by Paul Callahan, which serendipitously
restored the block. If you've tried building reflectors before,
you will know that this amount of luck is seldom encountered.
For a more in-depth analysis of the rectifier and its uses, see
Dave Greene's article at:
http://pentadecathlon.com/lifeNews/2009/05/new_stable_180degree_glider_re.html#more
When Dieter Liethner and Alan Hensel originally proposed the two
prizes, they were expecting a 90° reflector. A 90° reflector would
be useful in more situations than a 180° reflector. Dave Greene
recycled $100 of his prize money to make two $50 prizes. If you
win the more ambitious prize, you will also get the money for the
easier prize. That is, unless someone wins the easier prize first.
The two prizes are:
Create a stable 90° reflector within a 50x50 box
Create a stable 90° reflector within a 35x35 box
There is some ambiguity within these statements. For starters,
does the bounding box only include the still-lifes, or does
it include temporary sparks? Secondly, if a stable reflector
emits multiple gliders, do all but one need to be eaterised?
It would be almost impossible to do this using Herschel technology.
The first, and easiest method, is to adapt one of Paul Callahan's
reactions. This is the technique used in the boojum reflector.
The second method is to try and create an even cleaner reaction.
That would be the most elegant way of doing the task. The third
option, which Dave Greene proposed, involves using drifter-based
technology to produce a glider. I think (but can't prove) that
this method is impossible, but it would produce the smallest
reflector.
We now know how we can rotate, reflect and multiply gliders
without synchronisation. However, can we turn a glider into
other signal types, like switch engines and LWSSes?
One method is to create and duplicate gliders, then collide
them to form the more complex object. This works well, but
only if the desired object has a glider synthesis. For example,
(at the time of writing) there is no known synthesis for any
of the c/3 ships, e.g. turtle, dart etc.
Another method is to collide gliders and Herschels. This leads
to more compact converters. An example is shown below:
This has a very fast recovery time. A smaller H->LWSS is
possible, but it is slower. The principle behind this is
to create an intermediate object "in passing", which is
then converted to the desired output using the same
Herschel. This is used in the following device, by Dieter
Liethner:
The first principle yields a good H->MWSS device:
which is roughly the same size as the one using the second
method:
The only H->HWSS converter built fires 3 gliders together
to form a HWSS. This means that it is much larger than
the other converters:
Now that we have converters from Herschels to spaceships,
how do we turn them back into Herschels/gliders? The obvious
method is to collide the spaceship into a still-life, which
is rebuilt by the output Herschel. The best LWSS->G is shown
below:
The following converter, which I found using Karel Suhajda's
Herschel track search program, Hersrch, converts either an LWSS
or an MWSS into a glider. It is the smallest of its kind:
I've also made the smallest (and fastest) HWSS->G device, which
takes just 1007 ticks to recover. The original version of this
used a boojum reflector, but Dave Greene suggested the following
replacement:
Dave also made a fast LWSS -> Herschel converter, with no inter-
mediate glider stage. The conduit can feed either an F116 or R64
conduit (shown below). Incoming LWSSes must be seperated by at
least 978 generations, although at certain timings the LWSS can
pass through unaffected. The circuit can be used as a demulti-
plexer.
More complex converters can be made. Two classic examples are
Dave Greene's H->swimmer and his and Noam's H->2c/3 transceiver.
You can find out about them on http://b3s23life.blogspot.com/
In February 2009, I found a way of optimising the H->swimmer
converter, removing an unnecessary glider from the recipe. This
allowed me to remove an entire track from the device. Next, I
used this converter to build the first glider -> Cordership
converter. A description of the converter (as well as the
pattern in RLE and MCell format) can be found at:
http://b3s23life.blogspot.com/2009/02/first-complete-glider-to-cordership.html
The most complex stable converter is my stable lightspeed trans-
ceiver. The receiver part is complete, but the transmitter part
requires five synchronised inputs. Completing the device is possible,
just extremely boring. Find out more on:
http://www.yucs.org/~gnivasch/life/lightspeed/index.html#beehive
Logic gates can be made easily in Life. The AND gate is the simplest:
The XOR gate is the second simplest. It has one glider and
one Herschel input, and one glider output.
Later I was able to produce two more XOR gates, both of them
being more compact than the one shown above. The latter one can
fire a glider on the very edge of the pattern!
The OR gate is the most complex elementary logic gate. The
smallest one produced is by Dave Greene:
In my opinion the most interesting form of logic gates are
those that can function asynchronously. I found the semi-
asynchronous AND gate pictured below:
To make it even better, it could be made completely asynchronous.
I'm working on making a variety of logic gates that function
this way, ranging from the simple to the complex. One of
the more complex ones that I've made is the ALU. Shown
below are two connected bits of the ALU; any number are
supported:
A block represents a 0, the absence of a block represents
a 1. Although this may seem counter-intuitive, it simplifies
the internal details.
Input 1 = READ (input)
Input 2 = CLEAR
Output 3 = READ (output)
Input 4 = ADD
The least significant bit is at the top, the most significant
bit is at the bottom. The device has been proven to work.
These logic gates, together with memory storage devices, make
it possible to build stable computers. Paul Chapman built the
first universal computer in Life, a Minsky Register Machine:
http://www.igblan.free-online.co.uk/igblan/ca/index.html
It is very powerful, but extremely slow due to the linear
data storage it uses (counter memory).
However, other memory architectures are possible; My U.C.C.
uses an unbounded binary data storage in order to vastly
accelerate the computer and make the process of programming
it more user-friendly. The U.C.C. is mentioned in more
detail in the 'Replicators' section.
The challenge of making a Universal Constructor has been
proven solvable for decades. Originally, people thought
that a constructor would be built out of p30 devices.
All of the required components (blocks, eaters, penta-
decathlons, queen bee shuttles etc.) were proven to have
a glider synthesis. This means that it is theoretically
possible to build a p30 machine that constructs p30
devices - including itself. Lengthly design schematics
for these things have been made, but no-one has ever
attempted to actually build one. The fundamental
components of such a device are known as "Buckingham
bits".
However, you don't require all of these "Buckingham bits".
Instead it is possible to build a Universal Constructor
from just 5 basic still-lifes. They are the block, the
eater, the beehive, the boat and the tub. Devices that
comply with this standard are known as Spartan devices.
Paul Chapman and Dave Greene built a functioning U.C.
using Spartan devices, that uses a slow-glider synthesis
to construct other Spartan devices, up to and including
itself.
The constructor reads instructions from a tape of boats
(1s) and blocks (0s). There is a very simple method for
interpreting this binary code as instructions. The first
part of the constructor simply reads the binary code. The
pattern below does not show the entire instruction tape,
which extends to the north-west:
The reader works by pulling a block (not shown) south-east
by multiples of 12 cells. Each time it does this, a glider
is emitted from the block (reading head) to the tape. If
there is a boat, the glider is reflected south-east. If
there is a block, the glider is absorbed. These still-lifes
are read destructively, so the tape is destroyed at the end
of the operation. This U.C. is not intended to be used
more than once.
The next section reads the binary code and converts it to
simple instructions. The instructions are:
DEC + Fire WHITE glider
DEC + Fire BLACK glider
DEC
INC
Here is the section that reads the binary code and converts
it to instructions. (Part of this overlaps with the first
section, so that you can see how to fit them together):
The third and final part follows the instruction by firing
gliders at a block. The first block acts as an "elbow" and
the second block acts as a "hand". These two degrees of
freedom allows something to be built at any position.
This construction arm is also used extensively in my U.C.C,
forming the basis for every register, tape read/write head
and the main construction arm.
Why do you need two seperate FIRE instructions? The reason
for this is because, like bishops on a chessboard, gliders
can only stay on their own colour (or parity).
The last part (again with an overlap) is shown below:
To see the pattern in action, download it from here:
http://entropymine.com/jason/life/oversize/jslife-oversize-20060831.zip
Or open "constructor-memory-tape" in Golly's library.
Unfortunately, the Universal constructor does not have a
method of replicating its instructions. This means that
the device cannot function as a replicator, puffer or
arbitrary-speed spaceship. However, a certain tape of
instructions can be fed into this device to make such
a pattern, but the synthesised device could not contain
a tape as complex as the one describing it, meaning that
it is impossible for this constructor to reproduce.
There are two methods of making a reproducing universal
constructor. The first way is to give it a section to
replicate the tape. This was Von Neumann's approach, and
works rather well. However, the much more flexible way
is to use a universal computer. This is a more elegant
solution, so this is the technique I implemented (see
below).
In 2009, I expicitly constructed a machine capable of
self-replication, which consists of a universal computer
connected to a construction arm. This machine is very
complex - it would take somewhere between 10^14 and 10^18
generations to reproduce, depending on whether any clever
algorithms are employed.
The pattern and description is available online at:
http://myweb.tiscali.co.uk/calcy/life/universal-CC/index.htm
A brief summary can also be found at:
http://www.conwaylife.com/wiki/index.php?title=Spartan_universal_computer-constructor
In June 2006, Brice Due made an incredible creation based
on p46 technology. This device, 2048 cells in diameter,
can simulate a single cell in Life. The two properties
that distinguish this from David Bell's Unit Life Cell
are the programmability (any outer-totalistic rule can
be simulated) and the fact that the middle of the pattern
acts as an indicator to whether the cell is live or dead.
As powerful as Brice's construction is, it seems out of
place on an article about stable technology. The reason
for this is that I created a stable version of Brice's
OTCAmetapixel, that works at p16777216 (rather than
p35328), is much bigger and is rotated 45° to the
orthogonal. It can also support more rules (2^512
instead of 2^18), including non-totalistic and
asymmetrical rules.
My metapixel relies on LC00-style logic circuitry. The
ROM uses a principle very similar to the universal
constructor, and the same shotgun (by Paul Chapman).
My ROM is non-destructive, so the metacell can be used
again and again without compromising the pattern.
It also uses a binary addressing system, which uses
a logic component I made called a 2^n-ifier. The
purpose of the device is to convert 1 glider into
2^n gliders (hence the name). Each input of the
addressing system is attached to a 2^n-ifier of
different index, so that the 9 inputs can be
transformed into a unique number between 0 and
511. Here is a 2^5-ifier:
The display used in my metacell is simply two waves of
diverging gliders, opposed to Brice's display which has two
waves of converging LWSSes. You can download the metacell
(along with a script) from:
http://cranemtn.com/life/files/UMC.zip
The display in my device has to be periodically fed with
gliders (the analogy of electricity) in order to be ON.
Dave Greene has suggested another method of display
device, which is stable in the ON and OFF states, and
only requires power to switch the state. The pattern
below demonstrates the principle, but cannot be readily
used.
Another suggested method (but too large and complicated)
is to synthesise a row of puffers, which lay down blocks
periodically to fill the display segment. This method can
permit a variety of shapes, whereas the liquid-crystal
idea can only allow parallelograms. The LCD parallelograms
can obviously be combined to yield some other shapes,
including the shape of a segment in a 7-segment display.
I have a working model of a stable LCD 7-segment display,
which you can find at:
http://myweb.tiscali.co.uk/calcy/life/7seglcd.gz
Herschel tracks are asynchronous, but signals can be
regularly spaced along them to produce oscillators or
guns of new periods. Near the start of this article I
mentioned the "Machine Gun", which is the shortest
Herschel loop. Oscillators of smaller periods can be
made by inserting multiple signals in the same track.
For example, oscillators called emus can be made, but
they can't emit gliders. The four emus are shown below:
Herschel tracks are not restricted to only containing stable
components, and lower periods than these can be attained by
using periodic ones. For example, Dieter Liethner and Stephen
Silver built guns of relatively low periods called Quetzals.
The p54 and p56 guns are moderately-sized.
P54 gun:
P56 gun:
On the other hand, the period 55 gun made using this method
was absolutely immense, because of an unlucky accident
meant that 44 corners were needed to make the track length
a multiple of 55. The Herschel loop is available online at:
http://www.argentum.freeserve.co.uk/1stq55.zip
However, Stephen Silver then managed to make a different p55
gun. The newer version uses glider streams, which collide to
produce a LWSS stream, which is converted into a Herschel
stream by another pair of glider streams. The pattern has a
distinct central 'spine' consisting of LWSSes and Herschels:
By Calcyman
Back to home page
E-mail me
The Herschel