Counter Machine

Idea

A register machine is an automaton idealizing the notion of computer registers, by removing an upper limit of the values in the register.

Configuration

A register machine consists of:

• A set of register indexes $\mathcal{R}$.
• A program made up of a finite list of instructions $\mathcal{I}$.

Instructions typically include:

• $R^{+}\to L$ - Increment register and jump to $L$
• $R^{-}\to L_1,L_2$ - If register $R$ is positive then decrement and jump to $L_1$ else jump to $L_2$
• $HALT$ - Stop executing.

Operation

States are made up of an instruction pointer $i$, and an map $\mathcal{R}\to \mathbb{N}$ for the register values.
The program runs the instruction, and then jumps to the appropriate next line. If the $HALT$ instruction is reached then terminate.