Befehlszähler: | Dieser zeigt auf den aktuellen Befehl. |
Programmspeicher: | Hier findet man die Befehlszeilen, welche RM-Befehle beinhalten. |
Akkumulator: | Das Register, auf dem die RM Operationen ausgeführt werden. Der Akkumulator wird auch mit bezeichnet. |
unendlich viele Register: | Diese nehmen Werte (Variablen) auf |
Register werden mit bezeichnet. |
Eine Registermaschine verfügt über folgende Befehle, die im Programmspeicher stehen können:
LOAD | Register in Akkumulator laden |
---|---|
STORE | Akkumulator in Register speichern |
ADD | Zum Akkumulator ein Register hinzuaddieren |
SUB | ... subtrahieren |
MULT | ... multiplizieren |
DIV | ... dividieren |
GOTO | Sprungbefehl. Der Befehlszähler wird verändert. |
IF (......) THEN ... | Bedingte Anweisung |
END | Der Befehlszähler wird auf gesetzt. |
Das Programm endet. | |
Konstante | # | k |
direkte Variable | nichts | c(i) |
indirekte Variable | c(c(i)) |
Es existiert sowohl das uniforme als auch das logarithmische Kostenmaß. Weiterhin existiert eine Zeit und eine Platzkomplexität:
uniforme Zeit | |
logarithmische Zeit | |
uniformer Platz | |
logarithmischer Platz |
Die Zeitkomplexität wird gemessen an den abgearbeiteten Befehlen. Die Platzkomplexität an den besuchten Registerzellen.
Für das logarithmische Kostenmaß wird die Wortlänge des zu bearbeitenden Wortes betrachtet. Hierbei gilt für das logarithmische Kostenmaß: