A Stack Constructor for the Turing Machine

The only restriction on the length of time the Turing Machine can run is, time itself and a supply of blank tape for the machine to use. The limit on time is only a practical limitation. The limit on blank tape is a procedural problem. It is not acceptable to make all the blank tape first as this puts a limit on the amount of blank tape for any particular program. There are two solutions either empty space acts as blank tape or blank tape must be added while the program is running. Unfortunately for this design empty space will not work. It is a straight forward procedure to stop the machine and paste on a bit of blank tape every now and again. It would be more satisfactory to build a life pattern that did the job. This is the current project which has progressed to the point at which a stack constructor has been built (16/11/2010).

The first observation is that the stack used in the Turing Machine is not quite 45 degrees. I have a new design which is 45 degrees. This is much simpler to construct. The Turing Machine stack is made up of cells which can hold a value and a delay mechanism to slow the value as it is pushed from one cell to another. This is required to ensure that the destination cell is empty when the value arrives for storage. The new design replaces the delay mechanism with another holding cell. There are separate controls for each side of each cell so this new design requires twice as many control signals.

However by making the main cell wider and using two glider guns to form a "U" shape, one control signal stream can control both sides of the cell. The delay cell does not need to be wider as the gliders pass through it one at a time and in this case buckaroos work to make the "U" shape. In fact only the gliders required to hold the gliders for the fixed delay (3 loops round the cell) are provided in the delay cell. The delay is included it in the pop cycle as well as the push cycle so that the position of the gliders in the main cell does not depend on the number of pushed and pops performed.

 

The pattern for the stack design (left above) is here in rle format. It shows a very short stack with control logic driven by a fixed cycle of push and pops. The data arrives in serial form and is converted to parallel and pushed on the stack. The parallel data from the stack is converted to serial form again after popping.

The pattern for the stack design (right above) is here in rle format. It shows same stack but with control logic to perform pop or push cycle from a single glider. The parallel data from the stack is converted to serial form again after popping.The guns that generate these come from Dieter and Peterís gun collection.

Videos of the stack
 

The stack constructor has 2 convoys of rakes one moving vertically and one moving horizontally. These fire gliders towards each other. The diagonal collision site is where the stack is generated. This procedure builds stack cells much quicker that it takes the Turing Machine to perform one cycle.

 

The placement of all these rakes was quite time consuming and need repeating many times to overcome the difficulties of synthesizing the components without unwanted collisions. I used python scripting in Golly to aid in this job.

The pattern for the stack constructor design is here in rle format (963 KB). It has two wings each with 167 rake constructs which insert gliders into the construction stream using the kick back reaction. All the rake constructs are identical and insert one glider, with the exception of one in the left wing which inserts a pair of gliders. This pair are too close together for the kickback reaction to place them. They are needed to synthesise a boat which is used in the construction process.

Here is a simple python script (36 KB) to run in Golly which will build the constructor. It takes two and a half minutes on my laptop.

The same principle applies to diagonal rake. My first attempt was using c/12 diagonal rakes based on the period 96 cordership. To create stack cells 90 life cells apart requires period 1080 c/12 rakes. These where built from 4 period 4320 rakes. The rle patterns for these are:

P1080 side rake (26kb)

P1080 backward rake (39kb)

P1080 kickback side rake (63kb)

The stack constructor is built from these is very large. P1080 diagonal stack constructor (21.8mb)

Much smaller alternative rakes where found by Adam P. Goucher and Matthias Merzenich using C/5 components. The stack constructor below was built using the P450 kickback side rake (17kb). The stack constructor is built from these is still quite large. P450 diagonal stack constructor (4.9mb) completed 15/02/2011.

This builds one stack cells every 450 generations which is actually slightly faster that the stack control signals move up the stack. These are gliders moving at c/4 but the path they take is a little longer than the diagonal.





Turing Machine Main Page

UTM page

Full UTM page

Counter Machine Simulator

Site by Paul Rendell.

Last Update 27th March 2011

Comments to Paul Rendell