Ψ Die Informatikseite

Menü
Unterabschnitte

Registermaschinen (kurz: RM)

Registermaschinen-Berechenbar RM-berechenbar: Eine partielle Funktion $f: \mathbb{N}\rightarrow \mathbb{N}^{k}$ wird RM-berechenbar genannt, wenn es eine Registermaschine $R$ gibt, so daß $f=f_{R}$.

Aufbau und Befehle

Eine Registermaschine besteht aus
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 $c(0)$ bezeichnet.
unendlich viele Register: Diese nehmen Werte (Variablen) auf
  Register werden mit $c(Nummer)$ 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 (...$\bowtie$...) THEN ... Bedingte Anweisung
END Der Befehlszähler wird auf $\infty$ gesetzt.
  Das Programm endet.

 
Zu jedem der fett geschriebenen Befehle kommt eine Variable3, von denen es drei Arten gibt:
Konstante # k
direkte Variable nichts c(i)
indirekte Variable $\ast$ c(c(i))

Kostenmaße

Es existiert sowohl das uniforme als auch das logarithmische Kostenmaß. Weiterhin existiert eine Zeit und eine Platzkomplexität:

$t_{R}^{u}$ uniforme Zeit
$t_{R}$ logarithmische Zeit
$s_{R}^{u}$ uniformer Platz
$s_{R}$ 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 $n$ betrachtet. Hierbei gilt für das logarithmische Kostenmaß:

\begin{displaymath}L(n)=\Bigl\{\begin{array}{ll}
1&f\uml {u}r\,n=0\\
1+\lfloor \log n \rfloor&f\uml {u}r\,n\ge 1\\
\end{array}\end{displaymath}

Effiziente Algorithmen

Als effizient gelten Algorithmen, für die die Laufzeit polynomiell beschränkt ist:

\begin{displaymath}T(n)=O(poly(n)) \Leftrightarrow T(n) \leq p(n), wobei\,p(n)\,ein\, Polynom\end{displaymath}



Fußnoten

... Variable3
Ein-Adress-Registermaschinen haben dieselbe Mächtigkeit wie Null, zwei oder drei Adressregistermaschinen.