Random Access Machine - LinkFang.de





Registermaschine

(Weitergeleitet von: Registermaschine)

Dieser Artikel oder Abschnitt ist nicht ausreichend belegt.

Die Registermaschine (RM) ist ein Rechnermodell der theoretischen Informatik, das einem realen Rechner (PC) sehr ähnlich ist. Das Modell geht auf eine Arbeit von John C. Shepherdson und Howard E. Sturgis aus dem Jahr 1963 zurück, aufbauend auf einer Arbeit von Heinz Kaphengst.[1]

Einfache Registermaschine mit drei Grundoperationen

Wie es bei mathematischen Rechnermodellen häufig der Fall ist, gibt es verschiedene, leicht voneinander abweichende Definitionen von Registermaschinen. Eine sehr einfache Definition sieht folgendermaßen aus:

Zunächst gibt es eine Zahl von Registern, die man meist mittels Indexschreibweise voneinander unterscheidet, also [math]R_0, R_1, R_2, \ldots[/math] In den einzelnen Registern können natürliche Zahlen gespeichert werden. Auf den Registern können nun drei Grundoperationen ausgeführt werden:

  • Inkrementieren eines Registers um 1.
  • Dekrementieren eines Registers um 1 (falls der Inhalt des Registers nicht bereits 0 ist).
  • Testen, ob ein Register 0 enthält.

Um überhaupt Berechnungen ausführen zu können, benötigt die Maschine eine festgelegte Anzahl von Eingabewerten. Es wird vereinbart, dass der erste Eingabewert im Register [math]R_1[/math], der zweite in [math]R_2[/math] usw. steht. Das Register [math]R_0[/math] wird ebenso wie alle anderen Register, die keine Eingabewerte enthalten, mit 0 initialisiert. Welche Operationen auf diesen Werten konkret ausgeführt werden, kann mittels eines Datenflussdiagramms definiert werden. Dabei führt eine Registermaschine – vorausgesetzt sie arbeitet korrekt und ist zur Berechnung der Aufgabe überhaupt in der Lage – eine bestimmte Anzahl von Rechenoperationen aus und gelangt schließlich in einen Endzustand. Der Wert, der im Endzustand im Register [math]R_0[/math] steht, wird als das Ergebnis der Rechnung betrachtet.

Beispiel Identitätsfunktion

Die rechts abgebildete Registermaschine gibt immer den Wert aus, der ihr als erster Eingabewert übergeben wird.

Das blau unterlegte Kästchen des Flussdiagramms stellt einen Test dar. Fällt dieser negativ aus, so läuft die Registermaschine durch die Schleife und dekrementiert bei jedem Schleifendurchlauf [math]R_1[/math] und inkrementiert [math]R_0[/math]. Schließlich enthält [math]R_1[/math] den Wert 0, der Test fällt positiv aus und die Maschine geht in den Haltezustand über. Es ist klar, dass im Haltezustand immer genau der Eingabewert aus [math]R_1[/math] in [math]R_0[/math] stehen muss. Die vorliegende Registermaschine ist also eine einfache Implementierung der Identitätsfunktion.

Registermaschinen und Turingmaschinen

Registermaschinen sind prinzipiell zu allen Berechnungen in der Lage, die auch reale Rechner ausführen können. Da man beweisen kann, dass sich die Registermaschine und die Turingmaschine gegenseitig mit polynomieller Laufzeit simulieren können, gelten Aussagen, die man für die Turingmaschine beweisen kann, auch für die Registermaschine und damit auch für jede beliebige Rechenmaschine. Dies ist in der theoretischen Informatik von Vorteil, da man viele Aussagen anhand der Turingmaschine leichter beweisen kann.[2]

Registermaschinen mit zwei Registern

Zu jeder Registermaschine mit n Registern gibt es eine äquivalente Registermaschine mit nur zwei Registern.

Zwei weitere wichtige Registermaschinen-Modelle

Man unterscheidet gelegentlich zwei wichtige Typen von Registermaschinen aus zwei Bereichen der Informatik. Sie unterscheiden sich unter anderem durch die Befehlsanzahl voneinander.

Siehe auch

Literatur

  • John C. Shepherdson, Howard E. Sturgis: Computability of Recursive Functions. In: Journal of the Association of Computing Machinery (JACM). Bd. 10, Nr. 2, 1963, ISSN 0004-5411 , S. 217-255 doi:10.1145/321160.321170 (eingegangen Dezember 1961).

Einzelnachweise

  1. Origins and Foundations of Computing, Friedrich L. Bauer, S. 96
  2. Registermaschinen und Turingmaschinen im Vergleich mit Beweis

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Registermaschine (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.