Cellular Automata

Minsky Register Machine using 4-state CA

A picture of a working Minsky Register Machine modelled using a 4-state Moore CA in which the centre cell, orthogonal neighbours, and diagonal neighbours, are summed separately.  This machine has 6 registers and calculates the nth prime, here about to start with n=10.  Any MRM can be emulated, up to and including a universal MRM.  Some notes follow below the picture.  Please post any comments to comp.theory.cell-automata.


First, a short glossary:

Pulse - a lightspeed orthogonal spaceship consisting of a head cell and a tail cell.
Track - the route a pulse follows, which is normally a straight line.

There a four parts to the machine:

(1) The instructions are arranged along the bottom.  An instruction is executed by a downward pulse, which is reflected leftward towards one of the registers along one of two tracks.  In a Minsky Register Machine there is no explicit instruction ordering - every instruction (except halt) has one or two branch fields.  Nevertheless, execution tends to proceed conventionally from left to right.

(2) The six registers are on the left.  The value of a register is the distance of a single memory cell from its left hand side.  A register is capable of performing two instructions, each sent as a single leftward-travelling pulse on a different track.  The "inc" instruction increments the register and eats the pulse.  The "test-dec" instruction works as follows: if the register contains zero, it is left unchanged and a single pulse is sent upward along the Z track; if the register is nonzero, it is decremented and a single pulse is sent upward along the NZ track.  Pulses on Z and NZ tracks pass unchanged though any registers above, and are reflected at the top-left rightward towards the latches.

(3) The next-instruction latches are along the top.  Each latch corresponds to the instruction below it.  When a test-dec instruction is executed, two latches are set corresponding respectively to the next instruction to be executed if the result of the test-dec was Z, and the next instructon to be executed if the result was NZ.  When the register returns a Z or NZ pulse, the pulse travels along the latches.  The set latch causes a new pulse to shoot downward towards its instruction.  The Z or NZ pulse is also accompanied by a reset pulse, which resets all latches ready for the next test-dec instruction.  The reset pulse follows a little behind the Z or NZ pulse, so the latter can read the latch before it is reset.

An instruction with no latch above it is never the destination of a test-dec instruction branch.  An instruction can have a Z latch or an NZ latch but not both.  Instructions which can be the destination of both Z and NZ branches are split into two instructions, the first a nop, by the pattern-builder software, so that each can have its own latch.

(4) The branch logic is the irregular area between the latches and the instructions.  As an instruction begins executing, further pulses are routed through this logic.  In the case of an inc instruction, a pulse is routed immediately to the next instruction (not necessarily in left-to-right sequence).  In the case of a test-dec instruction, pulses are directed to the two latches which mark the possible next instructions.

As the CA runs, some parallelism is incidentally exhibited when multiple inc instructions are executed one after another.  Only when a test-dec instruction is executed does the machine have to wait for the return Z or NZ pulse.  The further a test-dec instruction is from the registers, the longer it takes to execute, but we are hardly concerned with performance here.  When a test-dec instruction towards the right branches "back" to a more leftward instruction, the instruction pulse and the latch-set pulse appear to "race" each other, but the latch-set pulse will always win.

The design is globally asynchronous, which is to say no syncronization of pulses over long distances is required, as long as in certain cases some pulses beat others by a decent margin to the same part of the machine.

For anyone interested, here is a quickly-assembled statement of the rules of the 4-state CA.

There are four states:

    O: Dead
    H: Head (of pulse)
    T: Tail (of pulse)
    M: Memory

The default next-states for these states, where no further rule is specified, are:

    O -> O
    H -> T
    T -> O
    M -> M

The rest of the rules are stated in the form c/q/d -> s, where c is the centre cell state, q and d are the totals of the orthogonal and diagonal neighbour states respectively, and s is the new state.  O states are omitted from q and d for readability.

    O/H/- -> H (move)
    O/H/M -> H (pass)
    O/HM/- -> H (pass)
    H/MT/- -> H (long head)
    T/H/M -> T (long tail)
    H/H/M -> O (copy enable)
    O/HM/H -> T (copy diode)
    M/-/HH -> H (push)
    O/H/HH -> M (push)
    O/H/MT -> T (pull)
    H/MTT/- -> M (pull)
    M/H/TT -> O (pull)

So eg M/-/HH means centre cell is M, orthogonal neighbours are all Os, diagonal neighbours are 2 Hs and 2 Os in any order.  Written out in full, this would be M/OOOO/HHOO.