|Life Universal Computer|
1/32nd-scale view of a Life Universal Computer
A 3-instruction MRM which adds the contents of two registers
1,378 x 1,369 - 16K
An 11-instruction MRM which multiplies the contents of two registers.
2,098 x 3,289 - 48K
|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.
Minsky Register Machine (separate page)
Split Left and Split Right
Merge Left and Merge Right
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.
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).
Ten different kinds of pulse are used to communicate between MRM components:
The sole initial pulse is an execution pulse.
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:
The Eater has one input and no outputs. It is just a standard eater.
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).
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.
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.
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.