Random-access machine

Definition

A random-access machine has registers $r_0, r_1, r_2, \dots$, indexed by the natural numbers, each holding a natural number. A program is a finite sequence $I_1, \dots, I_m$ of instructions of the following kinds, where $i, j, k, c \in \N$ and $1 \le l \le m$.

1. $r_i \leftarrow c$, which loads a constant.
2. $r_i \leftarrow r_j + r_k$ and $r_i \leftarrow r_j \mathbin{\dot-} r_k$, where $a \mathbin{\dot-} b = \max(a - b, 0)$.
3. $r_i \leftarrow r_{r_j}$ and $r_{r_i} \leftarrow r_j$, the indirect load and store.
4. $\mathrm{JZ}(i, l)$, which goes to instruction $l$ if $r_i = 0$.
5. $\mathrm{HALT}$.

Every instruction other than a taken jump or $\mathrm{HALT}$ is followed by the next one in the list. A run starts at $I_1$ with the input in finitely many registers and all other registers $0$. When the run halts, the output is read from a fixed register. In the unit cost measure each instruction costs $1$. In the logarithmic cost measure an instruction costs the total number of bits of the addresses and values it uses.