Register Machine Program

computation

Definition

Register Machine Program

A program of a register machine with registers consists of a start token and a finite set of instructions:

• Function instruction: read as : do then goto
• Test instruction: read as : if then goto else goto

is called the label of the instruction, and and are jump labels . Jump labels that are not label of any instruction are called end labels. Labels are unique.

Computation

Computation of an Arithmetic Function

Let an arithmetic function and an -RM.

Initial state:

End state:

• end label reached

Number of Registers Number of Inputs

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

Configuration:
: the current label is ; after executing the previous instructions, or initially if is the start label

Addition Program

Example (Calculation):

The program computed .

Subtraction Program

Example (Calculation):

The program computed .

Predecessor Program

Example (Calculation):

The program computed the predecessor of , which is .

Example (Calculation):

The program never halts as 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 :

Let the code of a program which computes . Then computes a function , such that:

Examples

Construct a 2-RM program that computes:

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

We’re adding to and subtracting from as long as .

After executing this loop, our register values are: . We just copied so far.

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

After executing this loop, our register values are: .

Now, we only need to add to and end the program. Thus:

After executing these, we end up with the register values: , which was our goal. The register machine ends in mark , which has no instruction, meaning it signals termination.

Therefore, our 2-RM program computing is: