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.
There are 2 types of line, special lines which begin with '#' and instruction lines. The instruction lines are:
<label> INC <counter> label [#<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>]
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 Example Counter Machine
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:
The Example Turing Machine