Life Universal Computer

Gallery
Figure 1

1/32nd-scale view of a Life Universal Computer


Figure 2
A 3-instruction MRM which adds the contents of two registers
1,378 x 1,369 - 16K
Adder
Figure 3
An 11-instruction MRM which multiplies the contents of two registers.
2,098 x 3,289 - 48K
Multiply
The Minsky Register Machine (MRM) is a model of computation equivalent in power to the Turing Machine.  A Universal MRM (URM) can be built which can emulate any other MRM by encoding its instructions and register contents as initial values of the URM's registers.

On 11th November 2002 I completed the construction of a Life pattern, based on Dean Hickerson's Sliding Block Memory, which implements the actions of a URM.  It is a true model of universal computation in Life.  Unlike the finite tape of Paul Rendell's marvellous Turing Machine, the values in the URM's registers are unbounded.

Version 0 of the URM is large (268,096 live cells in an area of 4,558 x 21,469) and slow (20 gen/s using Johan Bontes's Life32 on a 400MHz AMD K6-II).  I plan further versions which I hope will improve on these figures, producing at best a quadratic increase in speed.
 

DOWNLOAD a zip archive (185K) containing Version 0 of the Life URM and other examples.


Contents
Minsky Register Machine (separate page)
Design Overview
Overall Layout
Operation
Components
    Eater
    Split Left and Split Right
    Merge Left and Merge Right
    Latch
    Register

Design Overview

The pattern is constructed on a lattice of 30x30 squares.  Lightweight Spaceships (LWSSs) are used to communicate between components, which have P60 logic (except for Registers - see below).  A LWSS takes 60 generations to cross a lattice square.  Every 60 generations, therefore, any inter-component LWSS (pulse) is in the same position relative to the square it's in, allowing for rotation.

Seven components are used in the construction: Register, Latch, Split Left, Split Right, Merge Left, Merge Right, and Eater.

All inputs and outputs of a component are aligned spatially on lattice squares and temporally at the correct P60 phase.  A component is quiescent until a single input pulse arrives.  The input pulse triggers some activity in the component, which results some time later in the production of zero, one or two output pulses and possibly an internal state change.  After all processing is complete, the component re-enters its quiescent state.  Only one input pulse at a time is processed by each component.

Multiple pulses may exist concurrently.  More than one pulse may be heading for the same component at the same time, but are never required to arrive synchronously at that component.  The overall layout of the components ensures that pulses heading for the same component arrive sufficiently well-spaced and in the correct order where necessary.


Overall Layout

A description of a Cellular Automaton which was used as the blueprint for the design and operation of Life MRMs can be found here.

An MRM is made up of nine regions (Figure 1).
 
Left-to-right at the top:
Latch Header The small area in the top-left corner; converts Z and NZ pulses to Latch read and clear pulses
Register Table Along the top; the chief state information storage for the URM
 
Left-to-right across the middle:
Latch Table Down the left side; marks potential next instructions
Loopback Pulse Eater Table A thin column of eaters just right of the Latches; consumes loopback pulses.
Branch Table The irregular area right of the eaters; branch Splits generate branch pulses from loopback pulses to control program execution flow.
Loopback Table The relatively solid column just right of the Branch Table; loopback Splits and Merges generate loopback pulses from execution pulses.
NOP/HALT Eater Table Occasional eaters to the right of the Loopback Table; consumes execution pulses for NOP and HALT instructions.
Operation Table The sparse irregular area on the right; operation Merges redirect execution pulses upwards towards the Registers.
 
At the bottom:
Latch Footer Below the Latches; four eaters to consume Latch read and clear pulses.

Ten different kinds of pulse are used to communicate between MRM components:
 
Execution Rightward from Latch or branch-end Merge to operation Merge or NOP/HALT eater.
INC Upward from operation Merge to Register.
DEC Upward from operation Merge to Register.
Loopback Downward from loopback Split, then leftward from loopback Merge through branch Splits to eater.
Branch Upward or downward from branch Split to branch-end Merge.
Latch Set Leftward from branch-end Merge to Latch.
NZ Leftward from Register to Latch Header.
Z Leftward from Register to Latch Header.
Latch Read Downward from Latch Header through Latches to eater.
Latch Clear Downward from Latch Header through Latches to eater.

The sole initial pulse is an execution pulse.


Operation

As each instruction is performed, both an execution pulse and a loopback pulse for that instruction are generated.

The operation of the four kinds of instruction is as follows:
 
HALT  The execution pulse is consumed by an eater.  The loopback pulse generates no branch pulses and is consumed by an eater.  Thus no further instructions are executed.  Other pulses may still be en route even after the HALT instruction completes, so the final state of the machine should not be read before the absence of all pulses.
NOP The execution pulse is consumed by an eater.  The loopback pulse generates one branch pulse to the next instruction.
INC The execution pulse generates an INC pulse for the appropriate Register.  The loopback pulse generates one branch pulse to the next instruction.  Since the generation of the branch pulse is immediate, INC (and NOP) instructions are in effect "pipelined".
DEC This is by far the most complex instruction.

The execution pulse generates a DEC pulse for the appropriate Register.  The loopback pulse generates two branch pulses, which in turn generate two Latch set pulses for the Latches associated with the two possible next instructions according to whether the DEC instruction passes or fails.

There are two kinds of Latch, the NZ (pass) Latch and the Z (fail) Latch.  They have the same design, but are aligned at different horizontal offsets within the Latch Table.  NZ Latches are aligned to the right side of the Latch Table; Z latches are aligned to the left side of the Latch Table.

An instruction which has no associated Latch is never the next instruction after a DEC instruction.  An instruction may have an NZ Latch or a Z Latch but not both.  Any instruction in the original MRM which is the target of both pass and fail branches is split into two instructions, the first a NOP, by the Life MRM pattern-builder software.

The Latch associated with the next instruction after the DEC instruction if it passes is always an NZ latch.  The Latch associated with the next instruction after the DEC instruction if it fails is always a Z latch.  Thus the two branch pulses generated by the DEC instruction ultimately set one NZ Latch and one Z Latch.

The DEC pulse attempts to decrement the appropriate Register, which some time later outputs either an NZ (pass) or a Z (fail) pulse towards the Latch Header.  The Latch Header generates two pulses, a Latch read pulse and a Latch clear pulse.  An NZ pulse from the Register generates a Latch read pulse aligned with the NZ Latches and a Latch clear pulse aligned with the Z Latches; conversely, a Z pulse from the Register generates a Latch read pulse aligned with the Z Latches and a Latch clear pulse aligned with the NZ Latches.

In the case of an NZ result, the Latch read pulse activates each NZ Latch in turn.  Cleared Latches ignore the pulse.  The single NZ Latch set by the DEC instruction generates an execution pulse for its instruction, and the Latch is cleared.  The Latch clear pulse activates each Z Latch in turn, and ensures that the Latch is cleared.

A Z result similarly executes the instruction associated with the single set Z Latch and ensures all Latches are cleared.

The layout of the MRM ensures that a Latch set pulse arrives before its associated Latch read and clear pulses, even though in large MRMs it may be the case that the read and clear pulses begin their journey from the Latch Header before one or both Latch set pulses have been processed.

In a large MRM, multiple Latch read and clear pulses may be en route, but the layout of the MRM again ensures that inputs to individual Latches always arrive in the right order.


Components

Eater
Split Left and Split Right
Merge Left and Merge Right
Latch
Register

Eater

The Eater has one input and no outputs.  It is just a standard eater.

Split Left and Split Right

Each Split component has one input and two outputs.  A Heisenburp reaction deletes a glider from a P60 gun (from Jason Summers's edition of Dieter Leithner and Peter Rott's gun collection), which in turn allows another P60 glider through to the orthogonal bees to generate a LWSS (by Paul Rendell and Paul Callahan).

Merge Left and Merge Right

Each Merge component has two inputs and one output.  An input LWSS from either of two orthogonal directions destroys a glider in a stream suppressing the output from the P30 LWSS gun (by Dean Hickerson), thus allowing an LWSS to escape.

Latch

The Latch is based on a reaction (obtained from Mark D. Niemiec's comprehensive library of glider syntheses, most by David Buckingham) in which two gliders coming from opposite directions synthesize a block which is offset from one of the glider paths sufficiently to avoid being hit by subsequent gliders on that path.

The presence of the block means that the Latch is in the set state; the absence of the block means that the Latch is in the clear state.

The Latch has three inputs and three outputs.  Two of the outputs, Latch read and Latch clear, are merely respective copies of the input of the same name.

The Latch set input pulse arrives from the right.  It is converted to a NE glider using Dieter Leithner and Stephen Silver's P30 LWSS-to-glider converter (also from Jason Summers's collection), which comprises a pentadecathlon and a clock.  This glider reacts with a SW glider from a P60 gun to create a block as described above.  Incidentally, the Latch set input is actually a toggle: if the Latch is in the set state, an input pulse will clear it.  However, this feature is not used here.

The Latch clear input pulse arrives from above, between the right-hand pair of P60 guns on the left.  A Heisenburp reaction destroys a glider in the SW suppressing stream, allowing a SE glider to escape towards the main part of the Latch.  The SE glider in turn destroys a NE glider in a supressing P30 stream, which releases a SE block detection glider heading for the site of the Latch state block.  If the block is present, the glider destroys it.  If it is absent, the glider passes through a gap in the SW P60 stream and is eaten.

The Latch read input pulse also arrives from above but activates the left-hand Heisenburp detector.  In this case, the resulting SE glider reacts with a glider from a P30 gun and a block using Dieter Leithner's signal duplicator reaction (from David Bell's pattern collection which is listed on Stephen Silver's Life Page), deleting a glider from the same suppressing P30 stream referred to above, and creating a new SE glider which is reflected NE by a buckaroo (by David Buckingham).

If the block is absent, the SE block detection glider and the NE glider from the buckaroo annihilate one another.  If the block is present, the block detection glider destroys it, thus clearing the Latch, and the unhindered NE glider from the buckaroo deletes a NW glider from a suppressing stream, which allows the escape of a rightward LWSS from the P30 LWSS gun to form the main Latch output.

Register

The Register is based on (and would not have been constructed without) Dean Hickerson's P120 Sliding Block Memory (SBM), which I have updated slightly by replacing the P120 gun available at the time of its original design with a smaller modern version.  This part of the component can be easily identified by its compact and efficient design.

The distance of a block NE from the diagonal marked by two long boats towards the upper right of the Register represents the nonnegative value held by it.  Note that I interpret as the value zero a position of the block which Hickerson in his original description interprets as the value one, and that therefore what Hickerson interprets as a transition from one to zero, I interpret as a transition from zero to minus one.

I shall not describe the SBM further, except to note that the P120 increment and decrement suppression streams and the P120 transition detector stream serve the same purposes here.

The Register has four inputs and two outputs.  Two of the inputs, NZ and Z, are merely copied respectively to the output of the same name by the merge subcomponents.

Each of the operation input pulses, INC and DEC, arrives from below.  Each is detected by a P60-to-P120 converter of my own design; the detector at the very bottom of the Register detects an INC input pulse on the left, while the detector immediately above detects a DEC input pulse on the right.

The converter comprises a pair of P120 guns, the upper one a standard on-off-off-off, and the lower one an on-off-off-on of my own design.  The first pair of gliders collide to create a block.  The final glider from the lower gun destroys the block.  The block thus lives for slightly fewer than 90 generations.  A correctly positioned LWSS arriving while the block exists destroys it, and the next glider from the lower gun escapes.  With correct timing, therefore, the block is destroyed by any P60 LWSS, and a P120 glider timed to the SBM is released.

The NW P120 glider generated by an INC input pulse is reflected by a series of twelve buckaroos up the left side of the Register, eventually hitting the back of the P30 gun which creates the P120 SBM increment suppression stream.  It thus suppresses a glider from the suppression stream, in turn causing the value held by the SBM to be incremented.

The NE P120 glider generated by a DEC input pulse immediately suppresses the suppression stream of a p30 LWSS gun, sending an (intra-component) LWSS up the right side of the Register.  This LWSS hits a P30 glider stream, and a signal duplicator reaction eventually produces two gliders, one heading NE and the other SW.

The SW glider takes a circuitous journey around the diamond shape created by the two back-to-back merge subcomponents.  It is reflected SE, NE, NW by buckaroos, and then SW and SE by two P8 reflectors (by Noam Elkies).  Its fate then depends on whether it encouters another glider (the Z glider) or not.  But supposing it doesn't, it is further reflected by three more buckaroos, SW, SE and finally NE, towards the glider stream circulating below the lower of the two merge subcomponents.  It annihilates a glider in that stream, in turn releasing an NZ output pulse heading left.

The NE glider from the duplicator is reflected NW by a buckaroo into the back of the P120 gun producing the SBM decrement suppression stream.  It thus suppresses a glider from the suppression stream, in turn causing the value held by the SBM to be decremented.

If the SBM held a nonzero value before it was decremented, the transition detection glider survives (as usual during the Register's quiescent state).  This glider in turn goes through a signal duplicator.  The (positive logic) NW glider from the duplicator suppresses a SW stream (the Z stream) from a P120 gun (with the help of a SE stream from a P60 gun at the very top of the register, needed because the NW-SW glider reaction isn't a clean annihilation).  The (negative logic) gap left in the SW stream from the duplicator is timed to allow the P120 increment suppression glider through.

If the SBM held zero (and was therefore decremented to minus one), the transition detection glider is destroyed.  No hole is created in the SW stream from the duplicator, and thus the increment suppression stream is interrupted, in turn immediately causing the SBM to be incremented, thus restoring its value to zero.  The absence of a glider in the NW stream from the duplicator in turn allows a SW glider to escape along the Z stream.

If it is created, the Z glider is reflected NW by a buckaroo, then SW by a P8 reflector.  It then zigzags down the left side, reflected by the other end of each of five buckaroos which are also used to guide the INC glider upwards.  (This two-way buckaroo ladder is of my own design.)  The Z glider exits the ladder by being reflected SW by a P8 reflector, then SE by a buckaroo, and heads for a signal duplicator (narrowly missing the circuitous glider).

The straight-ahead output from the duplicator annihilates a glider in the stream circulating above the upper of the two merge subcomponents, in turn releasing a Z output pulse heading left.  The (negative logic) output of the duplicator is inverted to a SW glider by a P30 gun; this glider is reflected NE by the pentadecathlon, and annihilates the circuitous glider.

Thus overall, if the decrement succeeds, the circuitous glider survives to cause the output of an NZ pulse.  If the decrement fails, the Z glider causes both the destruction of the circuitous glider, and the output of a Z pulse.

If even one person has actually read through this and followed the operation in one of the MRM patterns, then it has been worth writing.