Random Access Machine

Random Access Machine

Die Registermaschine (auch RAM für engl. random access machine) 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.

Inhaltsverzeichnis

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 R0,R1,R2... 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 R1, der zweite in R2 usw. steht. Das Register R0 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 Flussdiagramms 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 R0 steht, wird als das Ergebnis der Rechnung betrachtet.

Es folgt ein einfaches Beispiel. Die folgende Registermaschine gibt immer den Wert aus, der ihr als erster Eingabewert übergeben wird:

Beispiel für eine Registermaschine

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 R1 und inkrementiert R0. Schließlich enthält R1 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 R1 in R0 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.

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


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Random access machine — In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of indirect addressing of its registers. Like the… …   Wikipedia

  • Random access machine — Pour les articles homonymes, voir RAM.  Ne doit pas être confondu avec Random Access Memory. La machine RAM, pour Random Access Machine, est un modèle abstrait d ordinateur destiné à étudier des algorithmes. Il s agit au départ d un modèle… …   Wikipédia en Français

  • Random Access Machine — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation …   Wikipédia en Français

  • Parallel Random Access Machine — In computer science, Parallel Random Access Machine (PRAM) is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine (RAM). In the same way, that the RAM is… …   Wikipedia

  • Parallel random access machine — PRAM, pour Parallel Random Access Machine, est un modèle abstrait de machine destiné à concevoir des algorithmes pour machines parallèles de modèle MIMD, ou pour de plus rares cas de modèle SIMD. PRAM modélise une machine parallèle à une mémoire… …   Wikipédia en Français

  • Parallel Random Access Machine — Als Parallel Random Access Machine, kurz PRAM, bezeichnet man ein Maschinenmodell zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie… …   Deutsch Wikipedia

  • Random access stored program machine — In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.The RASP is a Random Access Machine (RAM) model that,… …   Wikipedia

  • Dynamic random-access memory — DRAM redirects here. For other uses, see Dram (disambiguation). Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube …   Wikipedia

  • Dynamic random access memory — (DRAM) is a type of random access memory that stores each bit of data in a separate capacitor within an integrated circuit. Since real capacitors leak charge, the information eventually fades unless the capacitor charge is refreshed periodically …   Wikipedia

  • Magnetoresistive random access memory — Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube Non volatile …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”