Register machine

The register machine (RM) is an abstract machine of theoretical computer science . Register machines are Turing-complete , which means that in principle they are capable of all calculations that Turing machines or real computers can perform. Since one can prove that the register machine and the Turing machine can simulate each other with polynomial runtime , statements that can be proven for the Turing machine also apply to the register machine and thus also to any calculating machine. This is an advantage in theoretical computer science, since it is easier to prove many statements using the Turing machine.

history

The model goes back to a work by John C. Shepherdson and Howard E. Sturgis (* 1936) from 1963, although they had a forerunner in Heinz Kaphengst .

Formal definition

There are several, slightly different definitions of register machines. The commands and their meaning differ depending on the author. A simple register machine with three basic operations is described below.

The register machine works with natural numbers . All numbers that appear from now on should be viewed in this context.

The register machine consists of:

a program consisting of finitely many numbered commands (starting with number 1)
an instruction counter b
an input value m
an output value n
and from an infinitely large memory of numbered memory cells ( registers ) r (1), r (2), r (3), ... Each register stores a natural number.

A program consists of the following commands:

command	Effect 1	Effect 2	Explanation
${\ displaystyle A_ {i}}$ then p	r (i): = r (i) + 1	b: = p	Increment of a register by 1.
${\ displaystyle S_ {i}}$ then p	If r (i)> 0 then r (i): = r (i) - 1	b: = p	Decrement a register by 1 if the content of the register is not already 0.
if then p else q ${\ displaystyle T_ {i}}$		If r (i) = 0 then b: = p otherwise b: = q	Test whether a register contains 0.

To start the program, an input data record consisting of m ordered values should also be available.

At the beginning the command pointer b is set to the value of the start marker of the program. The memory cells from numbers 1 to m are set to the corresponding values of the input data set. The remaining memory cells receive the value 0.

The register machine then executes the program's commands one after the other. The command with the number b is always executed. The execution of a nonexistent command terminates the program.

After termination, all values from r (1) to r (n) are output.

Register machines , like all machines, can be clearly illustrated using flow charts .

Example identity function

Example of a register machine

The register machine shown on the right always outputs the value that is transferred to it as the first input value.

The blue-coded boxes of the flow chart represents a test. If this is negative, then the register machine runs through the loop and decremented at each iteration and increments . Finally contains the value 0, the test is positive and the machine goes into the hold state. It is clear that exactly the input value from in must always be in the hold state . So the present register engine is a simple implementation of the identity function . ${\ displaystyle R_ {1}}$ ${\ displaystyle R_ {0}}$ ${\ displaystyle R_ {1}}$ ${\ displaystyle R_ {1}}$ ${\ displaystyle R_ {0}}$

Random Access Machine

The Random Access Machine ( RAM for short ) is a special type of register machine . It has the ability to address the registers indirectly .

The Random Access Machine consists of:

a program consisting of finitely many numbered commands (starting with number 1)
an instruction counter b
an accumulator c (0)
and an infinitely large memory of numbered memory cells ( registers ) c (1), c (2), c (3), ...

Each register (including b and c (0)) stores an arbitrarily large natural number .

At the beginning the command counter b contains the value 1, the accumulator the value 0. The memory cells from number 1 contain the finite input at the beginning. The remaining memory cells contain the value 0.

A program consists of the following commands:

command	Effect 1	Effect 2
LOAD i	c (0): = c (i)	b: = b + 1
CLOAD i	c (0): = i	b: = b + 1
INDLOAD i	c (0): = c (c (i))	b: = b + 1
STORE i	c (i): = c (0)	b: = b + 1
INDSTORE i	c (c (i)): = c (0)	b: = b + 1
ADD i	c (0): = c (0) + c (i)	b: = b + 1
CADD i	c (0): = c (0) + i	b: = b + 1
INDADD i	c (0): = c (0) + c (c (i))	b: = b + 1
SUB i	${\ displaystyle c (0): = \ max (c (0) -c (i), 0)}$	b: = b + 1
CSUB i	${\ displaystyle c (0): = \ max (c (0) -i, 0)}$	b: = b + 1
INDSUB i	${\ displaystyle c (0): = \ max (c (0) -c (c (i)), 0)}$	b: = b + 1
MUL i	c (0): = c (0) * c (i)	b: = b + 1
CMUL i	c (0): = c (0) * i	b: = b + 1
INDMUL i	c (0): = c (0) * c (c (i))	b: = b + 1
DIV i	${\ displaystyle c (0): = \ lfloor c (0) / c (i) \ rfloor}$	b: = b + 1
CDIV i	${\ displaystyle c (0): = \ lfloor c (0) / i \ rfloor}$	b: = b + 1
INDDIV i	${\ displaystyle c (0): = \ lfloor c (0) / c (c (i)) \ rfloor}$	b: = b + 1
GOTO i		b: = i
IF c (0) GOTO i ${\ displaystyle \ alpha \, l}$ ${\ displaystyle \ alpha \ in \ {<, =, \ neq,> \}, \; l \ in \ mathbb {N}}$		b: = i if the condition is true, b: = b + 1 otherwise.
END		b: = b

The register machine executes the program commands one after the other. The command with the number b is always executed next. Almost all commands increase the command counter by 1, so that after such a command the next command with the next higher number is executed. The register machine stops as soon as the instruction counter b designates the END instruction. The result of the calculation is then in (previously) defined registers.

literature

John C. Shepherdson, Howard E. Sturgis: Computability of Recursive Functions. In: Journal of the Association of Computing Machinery (JACM). Vol. 10, No. 2, 1963, ISSN 0004-5411 , pp. 217-255 doi : 10.1145 / 321160.321170 (received December 1961).

Web links

Register machine , Hessian education server
Register machine (RAM), Church Turing thesis , Prof. Dr. Berthold Vocking, RWTH Aachen, 2010 (PDF)
Lecture Theoretical Computer Science II , Bernhard Beckert, University of Koblenz Landau, 2007 (PDF)

Individual evidence

^ Register machines and Turing machines in comparison with proof
↑ Origins and Foundations of Computing, Friedrich L. Bauer , p. 96

[1] Register machines and Turing machines in comparison with proof

[2] Origins and Foundations of Computing, Friedrich L. Bauer , p. 96