Register Machine

computation

Definition

Register Machine

A register machine with $m$ registers consists of 3 components:

$$R=⟨S,O,T⟩$$

where:

• $S={\mathbb{N}}^m$: stored states in $m$ registers
• $O=\{A_i\mid 1\le i\le m\}\cup \{S_i\le i\le m\}$: storage commands
• $T=\{t_i\mid 1\le i\le m\}$: test commands

The content of the $i$th register is denoted as $R(i)\in \mathbb{N}$.

Semantics:

• $A_i$: $R(i)\leftarrow R(i)+1$ (add)
• $S_i$: $R(i)\leftarrow R(i)-1$ (subtract)
• $t_i$: Is $R(i)=0$?

Properties

Turing-completeness

Register machines are Turing-complete and thus computation-equivalent to Turing machines.

Minimality

Already 2-RMs - modulo suitable encodings of inputs and outputs as single numbers - are computationally universal.

Relation to Modern Computer Models

RMs can be generalised quite directly to realistic formal models of modern computers (e.g. the Random Access Machine, where memory areas have to be addressed explicitly).

Program

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 labels of any instruction are called end labels. Labels are unique.

Link to original