Registermaschine/Zahlen/Befehle/Programm/Definition

Registermaschine

Unter einer Registermaschine versteht man eine endliche Folge von Registern ${}R_{1},R_{2},\ldots ,R_{m}$ (oder Speichern), deren Inhalt jeweils eine natürliche Zahl ist, die durch eine endliche (eventuell leere) Folge von Strichen repräsentiert wird.

Ein Programm für eine Registermaschine ist eine endliche durchnummerierte Folge von Befehlen ${}B_{1},B_{2},\ldots ,B_{h}$, wobei es für die einzelnen Befehle ${}B_{j}$ die folgenden Möglichkeiten gibt.

1. ${}i+$ (erhöhe den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. um einen Strich).
2. ${}i-$ (reduziere den Inhalt des Registers ${}R_{i}$ um ${}1$, d.h. ziehe einen Strich ab; wenn der Inhalt leer ist, so lasse ihn leer).
3. ${}C(ij)$ (wenn das ${}i$-te Register leer ist, so gehe zum Befehl ${}B_{j}$, andernfalls zum nächsten Befehl).
4. Drucke (drucke den Inhalt des ersten Registers).
5. Halte an.

Dabei muss ${}i\leq m$ für alle in einer Programmzeile adressierten Register und ${}j\leq h$ für alle adressierten Befehlszeilen gelten. Die letzte Befehlszeile ${}B_{h}$ ist ein Haltebefehl und sonst gibt es keinen Haltebefehl.