Register Machine Program

computation

Definition

Register Machine Program

A program of a register machine with $m$ registers consists of a start token $a\in \mathbb{N}$ and a finite set of instructions:

• Function instruction: $(r,f,p)$ read as $r$: do $f$ then goto $p$
• Test instruction: $(r,t,p,q)$ read as $r$: if $t$ then goto $p$ else goto $q$

$r$ is called the label of the instruction, and $p$ and $q$ are jump labels $(r,p,q\in \mathbb{N})$. Jump labels that are not labels of any instruction are called end labels. Labels are unique.

Computation

Computation of an arithmetic Function

Let $f:{\mathbb{N}}^k\to \mathbb{N}$ an arithmetic function and $R$ an $m$-RM.

Initial state:

• $R(i)=n_i\forall 1\le i\le k$
• $R(i)=0\forall k+1\le i\le m$

End state:

• end label reached
• $f(n_1,\dots ,n_k)=R(1)$

Number of Registers $m$ $\ne$ Number of Inputs $k$

In general, a register machine has more registers than input numbers.

Configuration:
$p:(n_1,\dots ,n_{k)}$: the current label is $p$; $R(i)=n_i$ after executing the previous instructions, or initially if $p$ is the start label

Addition Program

$$ADD=(0,\{(0,t_2,5,1),(1,S_2,2),(2,A_1,0)\})$$

Example (Calculation):

$$\begin{array}{rl}0:(5,2)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹1:(5,2)& \text{1: decrement }R(2)\text{ and goto 2}\\ ⟹2:(5,1)& \text{2: increment }R(1)\text{ and goto 0}\\ ⟹0:(6,1)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹1:(6,1)& \text{1: decrement }R(2)\text{ and goto 2}\\ ⟹2:(6,0)& \text{2: increment }R(1)\text{ and goto 0}\\ ⟹0:(7,0)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹5:(7,0)& \text{Endmark 5 reached, halt; output }R(1)=7\end{array}$$

The program computed $5+2=7$.

Subtraction Program

$$SUB=(0,\{(0,t_2,5,1),(1,S_2,2),(2,S_1,0)\})$$

Example (Calculation):

$$\begin{array}{rl}0:(5,2)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹1:(5,2)& \text{1: decrement }R(2)\text{ and goto 2}\\ ⟹2:(5,1)& \text{2: decrement }R(1)\text{ and goto 0}\\ ⟹0:(4,1)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹1:(4,1)& \text{1: decrement }R(2)\text{ and goto 2}\\ ⟹2:(4,0)& \text{2: decrement }R(1)\text{ and goto 0}\\ ⟹0:(3,0)& \text{0: if }R(2)=0\text{ then goto 5, else goto 1}\\ ⟹5:(3,0)& \text{Endmark 5 reached, halt; output }R(1)=3\end{array}$$

The program computed $5-2=3$.

Predecessor Program

$$PRED=(0,\{(0,t_1,0,1),(1,S_1,2)\})$$

Example (Calculation):

$$\begin{array}{rl}0:(2)& \text{0: if }R(1)=0\text{then goto 0, else goto 1}\\ ⟹1:(2)& \text{1: decrement}R(1)\text{and goto 2}\\ ⟹2:(1)& \text{Endmark}2\text{reached, halt; output R(1)=1}\end{array}$$

The program computed the predecessor of $2$, which is $1$.

Example (Calculation):

$$\begin{array}{rl}0:(0)& \text{0: if }R(1)=0\text{then goto 0, else goto 1}\\ ⟹0:(0)& \text{0: if }R(1)=0\text{then goto 0, else goto 1}\\ ⟹0:(0)& \text{0: if }R(1)=0\text{then goto 0, else goto 1}\\ ⟹\dots & \text{0: doesn’t halt}\end{array}$$

The program never halts as $0$ has no predecessor and the program has no special case for that.

Compositionality

Register machines programs - as Turing machines - can run other register machine programs.

Universality

There are universal register machine programs $P_U$:

Let $⟨F⟩$ the code of a program which computes $f:{\mathbb{N}}^k\to \mathbb{N}$. Then $P_U$ computes a function $u:{\mathbb{N}}^{k+1}\to \mathbb{N}$, such that:

$$u(⟨F⟩,n_1,\dots ,n_k)=f(n_1,\dots ,n_k)$$