Register machine

Definition

Let $k \ge 1$. A register machine (counter machine) with registers $R_1, \dots, R_k$ is a finite sequence $I_1, \dots, I_m$ of instructions of the following three kinds, where $1 \le i \le k$ and $1 \le j, l \le m$.

1. $\mathrm{INC}(i, j)$: add $1$ to $R_i$ and go to instruction $j$.
2. $\mathrm{DEC}(i, j, l)$: if $R_i = 0$, go to instruction $l$; otherwise subtract $1$ from $R_i$ and go to instruction $j$.
3. $\mathrm{HALT}$: stop.

A configuration is a pair $(p, r)$ of an instruction number $p$ and a vector $r \in \N^k$ of register contents. Here $\N$ is the set of natural numbers. A run starts at instruction $1$ and performs the instructions in turn until it reaches $\mathrm{HALT}$, if ever. The machine computes the partial function $f \colon \N^n \rightharpoonup \N$, for $n < k$, that takes $(x_1, \dots, x_n)$ to the final content of $R_1$. Here the run starts with $R_{i+1} = x_i$ for $i \le n$ and all other registers $0$, and $f(x)$ is undefined when the run does not halt.