## You are here

Homeexamples of unlimited register machines

## Primary tabs

# examples of unlimited register machines

In this entry, we illustrate the basic computing power of unlimited register machines by giving some examples.

Example (Addition). Here, we show how the addition of two non-negative integers can be achieved by a URM. Let $M$ be the URM with the instructions:

$I_{1},I_{2},I_{3},I_{4},I_{5}=J(2,3,5),S(1),S(3),J(1,1,1),Z(3)$ |

Let the input content be $a,b$ in the first two registers, and $0$ everywhere else. Then the ouput content has $a+b,b$ in the first two registers, and $0$ everywhere else. This is how the computation works:

1. compare the contents of registers 2 and 3,

2. if they are different, increase the content of register 1 by 1,

3. increase the content of register 3 by 1,

4. 5. erase the content of register 2,

6. erase the content of register 3.

7. the computation halts, because instruction 6 does not exist.

Below is an actual computation carried out where $a=3$ and $b=2$: This is how a computation works with input

$3$ | $2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

input |

$c_{1}$ |

$3$ | $2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{1}$ |

$c_{2}$ |

$4$ | $2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{2}$ |

$c_{3}$ |

$4$ | $2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{3}$ |

$c_{4}$ |

$4$ | $2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{4}$ |

$c_{5}$ |

$4$ | $2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{1}$ |

$c_{6}$ |

$5$ | $2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{2}$ |

$c_{7}$ |

$5$ | $2$ | $2$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{3}$ |

$c_{8}$ |

$5$ | $2$ | $2$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{4}$ |

$c_{9}$ |

$5$ | $2$ | $2$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{1}$ |

$c_{{10}}$ |

$5$ | $2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $\cdots$ |

$I_{5}$ |

Note that the last instruction $I_{5}$ above may be removed without affecting the outcome (in register $1$).

Example. Let $M$ be the URM with a single instruction $I_{1}=J(n,n,2)$. This machine, when run, halts immediately after the first computation step. If $I_{1}$ were $J(n,n,1)$ instead, then the machine loops forever when run, because it keeps jumping back to $I_{1}$. In both cases, the tape contents do not change. Nevertheless, we shall see that such instruction $J(n,n,p)$ is very useful in the next example.

Example (Transfer Instruction). Here, we show how the transfer instruction $T(m,n)$ may be simulated by other instructions. Let $M$ be the URM with the following instructions:

$I_{1},I_{2},I_{3},I_{4},I_{5}=J(m,n,6),Z(n),S(n),J(m,n,6),J(m,m,3)$ |

When a computation is started with any input,

1. $M$ first compares the contents of registers $m$ and $n$, if they are the same, it jumps to the 6th instruction, which does not exist, so the computation halts.

2. Otherwise, it goes to the next step, which reduces the content of register $n$ to $0$,

3. Then, step by step, $M$ increases the content of register $n$ by $1$.

4. During each increment, it compares the contents of registers $m$ and $n$. If they are not the same, the loops back to instruction 3, and increases the content of $n$ by $1$.

5. However, if they are the same, then it jumps to instruction 6, so that the computation halts.

Below is a computation of input where the contents of registers $m$ and $n$ are $9$ and $7$ respectively (assume $m<n$)

$r_{1}$ | $\cdots$ | $9$ | $\cdots$ | $7$ | $\cdots$ |

input |

$c_{1}$ |

$r_{1}$ | $\cdots$ | $9$ | $\cdots$ | $7$ | $\cdots$ |

$I_{1}$ |

$c_{2}$ |

$r_{1}$ | $\cdots$ | $0$ | $\cdots$ | $7$ | $\cdots$ |

$I_{2}$ |

$c_{3}$ |

$r_{1}$ | $\cdots$ | $1$ | $\cdots$ | $7$ | $\cdots$ |

$I_{3}$ |

$c_{4}$ |

$r_{1}$ | $\cdots$ | $1$ | $\cdots$ | $7$ | $\cdots$ |

$I_{4}$ |

$c_{5}$ |

$r_{1}$ | $\cdots$ | $1$ | $\cdots$ | $7$ | $\cdots$ |

$I_{5}$ |

$c_{6}$ |

$r_{1}$ | $\cdots$ | $2$ | $\cdots$ | $7$ | $\cdots$ |

$I_{3}$ |

looping instructions 3,4,5 until content of register $m$ reads 9 |

$c_{{21}}$ |

$r_{1}$ | $\cdots$ | $7$ | $\cdots$ | $7$ | $\cdots$ |

$I_{3}$ |

$c_{{22}}$ |

$r_{1}$ | $\cdots$ | $7$ | $\cdots$ | $7$ | $\cdots$ |

$I_{4}$ |

The result is precisely the same as running a URM with a single instruction $T(m,n)$. However, without $T(m,n)$, it takes 28 steps to achieve the same goal.

# References

- 1 J. C. Shepherdson, H. E. Sturgis, Computability of Recursive Functions. Journal Assoc. Comput. Mach. 10, 217-255, (1963).
- 2 N. Cutland, Computability: An Introduction to Recursive Function Theory. Cambridge University Press, (1980).

## Mathematics Subject Classification

68Q05*no label found*03D10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections