Notes on the Counter Machine Simulator / Chapman GoL Counter Machine Generator
The Counter Machine
A Counter Machine is capable of performing any theoretical calculation. For this it must have infinite capability. This is provided by the counters which in a theoretical machine can store any positive number however large. A counter machine only needs a very small instruction set. This example has 3 basic instructions INC, DEC and HLT.
INC increments a counter, DEC decrements a counter and HLT halts the program. Most counter machines have the concept of an ordered list of instructions which are executed one after another. The DEC instruction is the branching instruction which allows a choice for the next instruction. If the counter to be decremented holds the value zero the DEC operation is not carried out but the next instruction can be different to the non zero case.
A Chapman GoL machine has no natural way of moving onto the next instruction, the next instruction must be specified. This means that the instructions can be presented in any order. The order will not alter the outcome but will effect the time it takes the Chapman GoL machine run. The order of the counters in Chapman GoL machine has a similar impact on the runtime.
A Chapman GoL machine has one other quirk. The method of passing control to the next instruction following a DEC involves arming 2 latches, one for each possible next instruction. The outcome of the decrement causes one of these armed latches to be triggered and the other to be reset. The design only allows one type of latch for any one instruction. This limitation is easily overcome with the addition on an extra instruction NOP which stands for No Operation. The NOP instruction simply passes control on to another instruction which can be built with the other type of latch.
The P1 version of Chapman's GoL machine has its own quark. The triggering mechanism sends gliders down the column of latches to trigger one and reset all. This moves slower than the arming gliders. If an instruction I high in the table is arming an instruction low in the table a problem can occur if it is triggered itself. The triggering wave passing down the latch column that triggers I can be overtaken by an arming glider generated by I and the wave can go on to trigger the instruction that this glider has armed. The result will be two instruction cycles in the machine instead of one. Additional waves of triggering soon leads to further extra triggering in an exponential fashion. This is easily overcome by inserting a NOP instruction.
Instruction Format
There are 2 types of line, special lines which begin with '#' and instruction lines. The instruction lines are:
<label> INC <counter> label [#<comment>]
<label> DEC <counter> label label [#<comment>]
<label> NOP label [#<comment>]
<label> HLT [#<comment>]
Where <label> is a unique text label for this instruction when it appears at the beginning of the line and the label of the next instruction when it appear towards the end of a line. <counter> is a text label for a counter. The DEC instruction has two possible next instructions. The first is taken when decrement occurs and the second when it does not.
The special lines are:
#C <counter> [ [ = ] <number> [#<comment>]
#Start <label> [ [ = ] <number> [#<comment>]
Lines beginning with #C are counter specification lines. These allow the initial value of a counters to be specified via the optional <number> parameter. The '=' is optional. Counter specification lines also serve another purpose. The counter labels <counter> are allocated to the counters of the GoL machine in the order that the counter label is encountered. Putting counter specification lines, with or without an initial value, before the instruction lines allows this order to be determined. A Line beginning with #Start line specifies the initial instruction to be executed. The default is the first instruction. Only the last such line encountered is effective.
Universal Counter Machine (Counter Machine)
This is a brief explanation of the coding of the simulated counter machine in the preset code UCM-CM due to Paul Chapman.
The simulated counter machine's description is held in the first five counters of the UCM using gödel encoding. Gödel encoding uses prime numbers to encode a list of values into one number. A different prime number is used as the label for each instruction and each counter. This prime number is used by the UCM to extract the relevant quantity from the list held in the UCM's counter. The UCM requires the simulated counter machine to start with the first instruction which is allocated the prime number 2.
The counters are:
The Chapman GoL Machine has one extra feature. On the top left is an extra counter that counts the number of DEC instructions which did not decrement a counter due to it having zero value. The Counter Simulator also calculates this value which acts as an additional check that the machine is performing correctly.
The operation of the UCM are explained on Paul Chapman's web site. Here is a file in rle format of the UCM-CM suitable for pasting in most GoL application such as Golly.
The Example Counter Machine
|
The image on the right shows the top part of one counter in the Chapman GoL machine (P30). The paths of space ships and gliders during a decrement operation have been marked in grey. The insert shows the block indicating the counter value which is zero. When incremented the block moves one square diagonally up and right.
The UCM-CM program preset in the applet simulates another counter machine which adds the values of its two counters. The UCM counter 0, called 'registers' holds the values of this machines counters. The UCM starts with 'registers', the left most counter, holding value 6. This is calculated by the formula 2^1 x 3^1 = 6. When it completes its program the simulated CM should have values 2 and 0 in its counters which is coded as 2^2 x 3^0 = 4 in 'registers'.
Another example, get the simulated CM to perform the calculation 2 + 3 = 5. 'registers should start with 2^2 x 3^3 = 108 and end with 2^5 x 2^0 = 32.
|
|
Universal Counter Machine (Turing Machine)
This is a brief explanation of the coding of the simulated Turing machine in the preset code UCM-TM.
The simulated Turing machine's description is held in five counters of the UCM. The transitions of the simulated Turing machine are encode to follow a cycle starting with writing a symbol, moving the Turing machine read/write head and reading a symbol and then using the symbol read to select the next transition. The machine starts with the first transition encoded with prime number 2. Transitions numbers are mapped to reduce the size of the totals. 0 -> halt, 1-> 2, 2 -> 3, n ->n+2 where n+2 is prime.
The counters are:
Here is a file in rle format of the UCM-TM suitable for pasting in most GoL application such as Golly.
The Example Turing Machine
|
The example Turing machine changes a string of '0's between two '1's into '1's. The machine must start with its read/write head between the '1's and moves right until if finds a '1'. It them moves left changing '0's to '1's until it finds the other '1' and stops. The preset code initialises the both tape halves to 2 and the initial transition assumes '0' between giving '...10001..' for the full content of the tape. It finished as '...11111...' all on the left tape which codes as 31.
oOo |
|
Site by Paul Rendell. |
Last Update 24th November 2011 |
Comments to Paul Rendell |