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 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 within the Synchronous Tile Assembly Model is possible, unlike in the asynchronous Abstract Tile Assembly Model.
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 '#'.
# Registers 'r1' and 'r2' can be initialized to a
# nonnegative integer at the start of the program.
ld r1 42
ld r2 67
# This defines the state 'Q0' to be the initial state.
init Q0 {
# If 'r1' and 'r2' are both zeroes, 'r1' is incremented,
# 'r2' is kept the same, and the machine transitions
# to the state 'Q1'.
z z -> Q1 1 0
# If 'r1' is zero and 'r2' is nonzero, 'r1' is decremented,
# 'r2' is kept the same, and the machine transitions
# to the state 'Q2'.
z nz -> Q2 -1 0
# If 'r1' and 'r2' are both nonzero, the machine halts.
nz nz -> halt
# The last possible input, 'r1' is nonzero and 'r2' is zero,
# is unspecified and implicitly has the definition 'nz z -> halt'.
}