The Two Counter Machine Simulator allows you to build and run counter machine programs restricted to only two registers that can be incremented or decremented. Although counter machines usually use sequential instructions along with labels to jump to, this implementation uses states to model machine instructions, further described in the Program Syntax and Semantics section.
In addition, the simulator is able to generate a tile assembly system in the Synchronous Tile Assembly Model (syncTAM) that simulates the defined counter machine.
Visit the Self-Assembly Wiki to learn more!
Marvin Minsky proved that two-counter machines is Turing equivalent. Since the syncTAM is able to simulate two-counter machines, it is shown that bounded-width computation in the syncTAM is possible, unlike in the asynchronous Abstract Tile Assembly Model (aTAM).
Unlike other counter machines, this implementation uses states to model the counter machine instructions instead of sequential instructions and labels to jump to. Although they look very different, they are equivalent and can simulate each other.
Each state takes both registers as inputs and checks whether they are zero or nonzero. Depending on the input, the two registers are each incremented, decremented, or kept the same before transitioning to the next specified state. States cannot decrement a register if the register is zero since registers only store nonnegative integers. Additionally, there must be one initial state, which can be specified by writing init before the name of the initial state.
If a state does not have a transition specified for a given input, the machine halts. States can explicitly halt for a given input using the keyword halt. States cannot be named halt or halt' since they are used internally.
There are two registers: r1 and r2. They can be initialized to a specified value using keyword ld e.g., ld r1 1024 stores the value 1024 to register r1
Note that the definitions of the states Q1 and Q2 are not shown.
# This is a comment! Comments start with a '#'.
# The two registers 'r1' and 'r2' can be initialized to a nonnegative integer at the start of the
# program. They are implicitly initialized to 0 if not specified.
ld r1 42
ld r2 0
# This defines an initial state called 'Q0'.
init Q0 {
# This is a transition. It specifies that if 'r1' is Zero and 'r2' is NonZero (denoted by 'z nz'),
# the machine transitions to state 'Q1' after 'r1' is incremented and 'r2' is kept the same.
z nz -> Q1 1 0
# To denote a register being decremented, '-1' is written. In this example, 'r1' is kept the same
# and 'r2' is decremented.
nz z -> Q1 0 -1
# 'halt' is used to explicitly denote that the machine halts.
nz nz -> halt
# The last possible input, 'r1' and 'r2' are both zero, is unspecified and implicitly has the
# of definition 'z z -> halt'.
}