Register machine

The register machine (RM ) is a computer model of theoretical computer science, which is very similar to a real computer ( PC). The model goes back to a paper by John C. Shepherdson and Howard E. Sturgis from 1963.

Simple register machine with three basic operations

As is often the case with mathematical computer models, there are several, slightly differing definitions of register machines. A very simple definition is as follows:

First, there are a number of registers, which are mostly using index notation differs from each other, so in the individual registers are natural numbers can be stored. Now on the registers three basic operations can be performed:

• Incrementing a register by 1
• Decrementing a register by one (if the contents of register 0 is not already ).
• Testing whether a register contains 0.

In order to ever be able to perform calculations, the machine requires a fixed number of input values ​​. It is agreed that the first input value in the register, the second is on etc.. The register is, like all other registers which do not contain input values ​​, are initialized to 0. Which operations are carried out on these values, specifically, can be defined by means of a data flow chart. It performs a register machine - assuming it is working correctly and to calculate the task at all capable of - a certain number of arithmetic operations, and finally reaches a final state. The value is in the final state in the register is considered to be the result of the calculation.

Example identity function

The register machine pictured to the right is always from the value that is passed to it as the first input value.

The blue highlighted box of the flow chart provides a test dar. If these are negative, the register machine runs through the loop and decremented each time through the loop, and incremented. Finally, contains the value 0, the test is positive and the machine goes into the hold state. It is clear that on hold exactly should be the input value in. The present register machine is thus a simple implementation of the identity function.

Register machines and Turing machines

Register machines are in principle to all calculations in a position that can also perform real computer. Since one can prove that the register machine and the Turing machine can simulate each other with polynomial running time, statements that can be proved for the Turing machine, also for the register machine and thus also for any computing machine apply. This is in theoretical computer science is advantageous since one can prove many statements on the basis of the Turing machine easier.

Register machine with two registers

There is an equivalent register machine with only two registers for each register machine with n registers.

Two other important registers Machine Models

A distinction is sometimes two important types of register machines of two areas of computer science. They differ from one another by the number of instructions of each other.

• Register machine ( computability theory )
• Register machine ( complexity theory )