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 label 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)$$

Examples

$f_P(n)=3n+1$

Construct a 2-RM program $P$ that computes:

$$f_P(n)=3n+1$$

Let $(n,0)$ be the initial register values. The goal is that $R(0)=f_P(n)$, i.e. register slot 0 must contain the result at the end. Given that $n$ is smaller than $3n+1$ for almost all $n$, we first copy $R(0)\to R(1)$ and then run the computation (more efficient, but functionally equivalent to copying at the end). Thus:

$$I_{\text{copy}}=\{(0,t_1,3,1),(1,A_2,2),(2,S_1,0)\}$$

We’re adding to $R(2)$ and subtracting from $R(1)$ as long as $R(1)\ne 0$.

After executing this loop, our register values are: $(0,n)$. We just copied so far.

Next, we want to triple $n$ into $R(0)$. The idea is the following: we chain 3 add instructions with one subtract extraction, similar to what we did before, i.e.:

$$I_{\text{triple}}=\{(3,t_2,8,4),(4,A_1,5),(5,A_1,6),(6,A_1,7),(7,S_2,3)\}$$

After executing this loop, our register values are: $(3n,0)$.

Now, we only need to add $+1$ to $R(0)$ and end the program. Thus:

$$I_{\text{end}}=\{(8,A_1,9)\}$$

After executing these, we end up with the register values: $(3n+1,0)$, which was our goal. The register machine ends in mark $9$, which has no instruction, meaning it signals termination.

Therefore, our 2-RM program computing $f_P$ is:

$$\text{THREEPLUSONE}=(0,I_{\text{copy}}\cup I_{\text{triple}}\cup I_{\text{end}})$$