Details of a Turing Machine in Conway's Game of Life

Below is a list of the parts with links between. The main parts are the FINITE STATE MACHINE and the TURING TAPE joined by the SIGNAL DETECTOR.

 Index of Parts

1GAP3 1GAP4 1GAP8
COLUMN ADDRESS COMPARATOR CONTROL CONVERSION
FANOUT FINITE STATE MACHINE IN GATE
MEMORY CELL METAMORPHOSIS II MWSS GUN
NEXT STATE DELAY NOT XOR Gate OUTGATE
OUTPUT COLLATOR P120 Gun P240 Gun
P30LWSS GUN P30MWSS GUN POP CONTROL
PUSH CONTROL ROW ADDRESS SET RESET LATCH (a)
SET RESET LATCH (b) SIGNAL DETECTOR STACK
STACK CELL TAKEOUT TURING TAPE

Turing Machine Parts

1GAP3

This is a reaction of a glider with a P30 glider stream to produce a gap of 3 gliders in the stream. Two version of this are shown in the example pattern.

Back to top

Back Main Page

Download Pattern 1K

Picture 2K

Java Animation


1GAP4

This is a reaction of a glider with a P30 glider stream to produce a gap of 4 gliders in the stream. Four version of this are shown in the example pattern.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


1GAP8

This is a reaction of a glider with a P30 glider stream tamed by an eater to produce a gap of 8 gliders in the stream.

Back to top

Back Main Page

Download Pattern 1K

Picture 2K

Java Animation


COLUMN ADDRESS

The column address for the FINITE STATE MACHINE is imposed on a P30MWSS stream by the output of the OUTPUT COLLATOR. It has the form 1VVV where VVV is the symbol read from the TURING TAPE. At the foot of each column a COMPARATOR is preset for the column address and when it recognises its address fires an LWSS up the column using METAMORPHOSIS II.

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


COMPARATOR

The MWLSS address stream (COLUMN or ROW ADDRESS) is sampled to provide the input to the comparator. This feeds one input of a NOT XOR gate. The other input is a MEMORY CELL containing the pattern to be recognised. The output of the NOT XOR gate forms the set leg of a SET RESET LATCH. The reset leg is an inverted P240 gun which resets the latch at the start of each address frame. The output of the latch is sampled by another P240 gun just prior to the latch being reset. The sampling glider will be destroyed if any address bits did not match the pattern in the MEMORY CELL of the comparator. When the address did match the sampling glider forms the output.

This comparator can only compare 6 bits of the 8 bit frame. The first bit must match so that the latch is reset correctly. The last bit must match so that the state of the latch is sampled correctly.

The example pattern shows the comparator for the used for addressing the columns. The addresses are supplied by an expanded MEMORY CELL.

Back to top

Back Main Page

Download Pattern 5K

Picture 2K

Java Animation


CONTROL CONVERSION

Each STACK has a different version so that one performs a PUSH when the other performs a POP.

It has two inputs from the SIGNAL DETECTOR. Ones input is a glider stream with 8 gliders. It has the form DVVVSSSS where D is the direction POP or PUSH VVV is the symbol to push and SSSS is the next Turing machine state. The other input is a glider indicating a signal is present.

A P240 gun samples the NOT D glider from the inverted DVVVSSSS stream to produce an output only when D is present. This is then put through a FANOUT with one of the outputs being an input to the PUSH CONTROL or POP CONTROL of the stack and the other glider deleting the other input from the SIGNAL DETECTOR which otherwise becomes the POP CONTROL or PUSH CONTROL of the stack.

The VVV gliders from the DVVVSSSS stream go through a rather long delay loop to synchronise with the INGATE.

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


FANOUT (Copy Unit)

This is a pattern where two queen bees are used to reflect glider streams. They are arranged back to back so that the Queen bee reflecting the output of a P30 gun stabilises the one reflecting the input signal. In the process the input signal is duplicated. A range of 8 timings stabilises the reaction which is a very useful feature.

The example pattern shows a fanout with input form a P60 gun from Dieter & Peter's gun collection.

Back to top

Back Main Page

Download Pattern 4K

Picture 2K

Java Animation


FINITE STATE MACHINE

The Finite State Machine for the Turing Program contains 9 memory cells in 3 columns. It is easily expanded to 128 cells.

The ROW ADDRESS 1SSS comes from the NEXT STATE output of the SIGNAL DETECTOR. The COLUMN ADDRESS 1VVV comes from the TURING TAPE OUTPUT COLLATOR.

At the selected cell the LWSS coming up the column collides with the MWSS coming along the row. This collision results in a block being formed which is transformed into a glider by a pentadecathlon. The glider then triggers the MEMORY CELL which outputs its pattern of gliders.

The output from the cell is collected by 8 LWSSes which are sent along the selected row by the ROW ADDRESS logic. After collecting the output of the selected cell, the remaining LWSSes proceed to the right of the row to be collected by another 8 LWSSes passing up the matrix. These are generated by a P240 GUN sensing the timing signal of the column address and a 1GAP8 reaction on the glider stream blocking a P30 LWSS GUN. The output is inverted for input to the SIGNAL DETECTOR

This example Finite State Machine here has 4 stages and is driven by more guns from Dieter & Peter's gun collection. It has a simpler Output Collection mechanism.

Back to top

Back Main Page

Download Pattern 23K

Picture 9K

Java Animation


IN GATE

Three P120 GUN are aligned and synchronised to inject the value gliders into the stack. A blocking glider stream is modulated by the serial value glider stream VVV to let the gliders onto the stack. This stream comes from the CONTROL CONVERSION logic. In order to allow for the value stream to be common on the two used for the TURING TAPE an extra gate is used to ensure that values are only allowed on when a push operation is in progress. This gate uses the 1GAP3 reaction with input from PUSH CONTROL.

The example is a cut down version of the example for the stack, just a single stackcell and only one control signal.

Back to top

Back Main Page

Download Pattern 12K

Annotated Picture 16K

Java Animation


MEMORY CELL

Two versions are used here. One in the COMPARATOR which produces a continuous output and stores the row or column address and the other which forms the memory cells for the FINITE STATE MACHINE. This latter version has a 1GAP8 GATE controlling the output.

The heart of the cell is the FANOUT. It is constructed of two queen bees acting as glider reflectors. One stabilises the other and in the process its output mirrors the output of the other reflector. One copy loops round to form the input of the FANOUT and thus stores the pattern.

The example shows the memory cell from the FINITE STATE MACHINE.

Back to top

Back Main Page

Download Pattern 4K

Picture 3K

Java Animation


METAMORPHOSIS II

This pattern converts a glider into an LWSS. See Stephen Silvers Lexicon. The example shown here is one of my favourite patterns. Metamorphosis II, a queen bee reflector and 2 pentadecathlon acting as a reflector to create a closed loop.

Back to top

Back Main Page

Download Pattern 1K

Picture 2K

Java Animation


MWSS GUN

This is derived from the P60 MWSS Gun from my collection which has been stabilised to convert a glider to an MWSS. The example shows the arrangement used with a P240 gun providing the input.

Back to top

Back Main Page

Download Pattern

Picture 2K

Java Animation


NEXT STATE DELAY

This is just a long loop to delay the Next State so that it can address the FINITE STATE MACHINE in conjunction with the output from the TURING TAPE. Along the way an inverted 1GAP3 driven by a P240 gun is used to tidy up the address by deleting the DVV from the output of the SIGNAL DETECTOR to leave 1SSSS for input to the ROW ADDRESS.

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


NOT XOR Gate

This is used in the COMPARATOR. It is created by the head on collision of the two input glider patterns between the gliders of a sampling P30 gun. The sampling glider will survive to produce an output if gliders are present from both inputs or neither input. The sampling glider is destroyed when only one input glider is present. The example shows the gate with inputs from a P60 and a P90 guns.

Back to top

Back Main Page

Download Pattern 1K

Picture 2K

Java Animation


OUTGATE

The STACK output is obtained from the pattern left in the first STACK CELL value trapping glider stream by the values trapped in the cell. This is arranged by using a P120 gun to test for the 4 glider gap put in the control stream by POP CONTROL. When the gap arrives, the output of this gun is used to control a 1GAP4 gate sampling the 4 gliders in an inverted copy of the entrapping stream. The P120 sampling gun creates an extra gap in the entrapping stream which is included in the output. The output is then in the form 1VVV as required to address the FINITE STATE MACHINE. A BLOCKER is used to eat the value gliders as they leave the cell.

The example is a cut down version of the example for the stack, just a single stackcell and only one control signal.

Back to top

Back Main Page

Download Pattern 12K

Annotated Picture 14K

Java Animation


OUTPUT COLLATOR

The output of both STACKS OUTGATES are collated via an inverting reaction and feed through the stack control logic to the COLUMN ADDRESS of the FINITE STATE MACHINE

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


P120 Gun, P240 Gun

From Dieter & Peter's gun collection.

Back to top

Back Main Page

P120 Download Pattern 1K

P120 Picture 2K

P120 Java Animation

-

-

P240 Download Pattern 1K

P240 Picture 2K

P240 Java Animation


P30LWSS GUN

An LWSS gun using three p30 glider guns. The 3-glider synthesis of a LWSS was found by Dave Buckingham and is suitable for all periods from 23 onwards. From Stephen Silvers collection.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


P30MWSS GUN

Dieter Leithner found a way to hammer a LWSS with two more LWSS to make a MWSS. David Bell later found a smaller way of doing this at p30. Noam Elkies and Dieter Leithner both discovered very soon after this that a stabilized prepulsar can do the job on one side. The pattern shown here incorporates both these mechanisms, plus a final touch added by Dieter Leithner to make it even smaller. From Stephen Silvers collection.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


POP CONTROL

A single glider initiates a PUSH operation of a STACK. It is feed through a FANOUT and the 2 resulting gliders then perform the following:

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


PUSH CONTROL

A single glider initiates a PUSH operation of a STACK. It is feed through 2 FANOUTs and the 3 resulting gliders then perform the following:

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


ROW ADDRESS

The row address of the FINITE STATE MACHINE is imposed on a P30MWSS stream by the next state output of the SIGNAL DETECTOR. It has the form 1SSSS where SSSS is the next state. At the left of each row a COMPARATOR is preset for the row address and when it recognises its address it fires an MWSS along the row. Added to this MWSS is the output collection mechanism. The output collection mechanism is triggered by the MWSS passing through a glider stream. The inverse of this stream is then a single glider which triggers a 1GAP8 GATE. This gate is blocking a P30LWSS gun. The 8 LWSSes generated will follow the MWSS along the row to collect the output of the addressed MEMORY CELL.

Back to top

Back Main Page

No Download Pattern

No Picture

No Java Animation


SET RESET LATCH (a)

This is created using the 2 modes of a right angle collision between P30 glider streams. In one mode glider n of leg A (An) collides with glider n of leg B (Bn). In the other mode glider An collides with glider Bn+1. The An-Bn mode is switched to the An-Bn+1 mode by a glider missing from the B leg. The An-Bn+1 mode is switched to the An-Bn mode by a glider missing from the A leg. Gliders missing from both legs do not change the mode. For this RESET LATCH one mode generates a block which is converted to a glider by a pentadecathlon. This is the SET mode. The other mode is stabilised by another pentadecathlon. This latch is used in the COMAPITOR.

The example has inputs from two P240 guns.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


SET RESET LATCH (b)

A variant of SET RESET LATCH (a) and a bit bigger. One of the two collisions of the two glider streams destroys the gliders being reflected by a queen bee. This latch is used in the SIGNAL DETECTOR

The example has inputs from two P240 guns.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


SIGNAL DETECTOR

The signal detector joins the FINITE STATE MACHINE to the TURING TAPE. It detects the output from the finite state machine and generates the input to the CONTROL CONVERSION logic as well as sending the next state back to the FINITE STATE MACHINE. One important function is to provide a method of halting the Turing Machine.

The heart of the detector is a SET RESET LATCH TYPE (b). A Negative feedback loop 240 generations long has been used for the reset leg. This loop contains a FANOUT. The inverting reaction has been stabilised with a pentadecathlon. This leaves the tuneable leg of the FANOUT for blocking the output of a P240 gun. If any of the 8 gliders in the P240 frame defined by the P240 gun are present in the input the P240 gun's output will not be blocked and has detected a signal. The signal detector is not ready to trigger again until the reset has cleared through the feedback loop.

This output of the P240 gun is put through another FANOUT so that one copy goes into the CONTROL CONVERSION logic while the other copy is combined with a copy of the input to convert DVVVSSSS to DVV1SSSS so that 1SSSS can be used to address the FINITE STATE MACHINE. This signal is sent to the NEXT STATE DELAY.

In this example the input is derived from two gliders guns from Dieter & Peter's gun collection, one P270 and the other P300. This pair cycle through all the combinations of input. The outputs are aligned with another P240 gun to show clearly when the detector detects the input.

Back to top

Back Main Page

Download Pattern 5K

Picture 2K

Java Animation


STACK

A Stack is a memory device which can theoretically store any number of values. It is made of any number of STACK CELLS connected one after another. In the push cycle all the values on the stack move one cell way from the control end of the stack and a new value is added into the now empty cell at the control end. In a pop cycle the value at the control end is removed and all the values move one cell towards the control end ready for the next cycle.

Control signals pass up each side of the stack. The FANOUT pattern is used to copy this at each stack cell to make the cell walls. The PUSH and POP CONTROLs make holes in the control signals and thus into the cells walls of each cell in turn to allow the value gliders to pass between cells.

This example is controlled by some of Dieter & Peter's guns one for POP, one for PUSH and one for the Values.

Back to top

Back Main Page

Download Pattern 30K

Picture 12K

Java Animation


STACK CELL

The reflecting reaction between two gliders is used to trap the cell values between two opposing glider streams. Holes in the glider streams are created by PUSH and POP CONTROL to allow the value gliders in and out of the cell. This stack cell is designed for 3 value gliders in each cell in parallel. The value gliders cycle round in 120 generations.

In order for the control signal for the Push Operation to arrive in time to open the stack cell for value gliders to enter, the value gliders must be delayed. The delay is based on a pattern I call TAKEOUT. TAKEOUT allows the push and pop paths between stack cells to be separated. TAKEOUT provides a 90 degree reflection so a standard queen bee reflector is used to align the value glider for the next cell. The result is that each stack cell is slightly offset from its neighbours. The push and pop path together must be a multiple of 60 generations.

This example shows two cells connected by the delay logic. It is controlled by some of Dieter & Peter's guns to allow the value gliders to pass backwards and forwards between them.

Back to top

Back Main Page

Download Pattern 13 K

Picture 5K

Java Animation


TAKEOUT

TAKEOUT is used as a delay in the STACK CELL. It uses pentadecathlons to separate the forward and return paths of a glider which is reflected through 180 degrees by another glider. One pentadecathlon reflects the returning glider by 180 degrees putting it sufficiently off the line of the forward glider so that it can be reflected though 90 degrees by a pair of pentadecathlons which themselves do not interact with the forward glider.

This example has been arranged in a closed loop. The P30 stream with the glider removed is inverted to provide the input to TAKEOUT.

Back to top

Back Main Page

Download Pattern 1K

Picture 3K

Java Animation


TURING TAPE

The Tape is implemented as two STACKS so the contents move backwards and forwards past the FINITE STATE MACHINE reading head. The odd thing about this design is that there is no tape for the symbol under the reading head. The symbol is read into the machine to be used to as an address by the FINITE STATE MACHINE in the POP of one cycle and is replaced by the symbol written in the PUSH of the next cycle.

The outputs from the SIGNAL DETECTOR are copied to each STACKs CONTROL CONVERSION logic and either STACKs OUTGATE output is picked up by the OUTPUT COLATOR to pass to the FINITE STATE MACHINE.

Back to top Back Main Page No Download Pattern No Picture No Java Animation


Site by Paul Rendell. Last Update 25 Feb 03 Comments to Paul Rendell