Random Access Machine (RAM)

Eine Random Access Machine, häufig auch als Registermaschine bezeichnet, ist ein mathematisches Rechnermodell, welches einem realen Rechner ähnlich ist. Im Gegensatz zu Turingmaschinene wird nicht nur sequentieller, sondern willkürlicher Zugriff auf den Speicher gewährleistet. Aus diesem Grund können manche Funktionen schneller berechnet werden als mit Turingmaschinen.

RAMs können sich lediglich in ihrem Programm (P), Bandalphabet (A) und der Nummerierung der Alphabetszeichen (Nr) unterschreiden.
Sei R = (P, A, Nr) eine RAM, so kann R als 6-Tupel definiert werden:
PC bezeichnet den Program Counter. Dieser gibt den aktuellen Inhalt des Befehlszählers an
ACC ist der Inhalt des Akkumulators
S bezeichnet den Inhalt des Datenspeichers
w ist das Eingabewort
x ist die Position des Lesekopfes auf dem Eingabealphabet
v  Ausgaben, die bereits auf das Ausgabeband geschrieben wurden

Eine RAM besteht aus einem endlichen Bandalphabet A = {0, 1, #, ☒}, einem Eingabeband, von dem die Eingaben gelesen werden und einem Ausgabeband, auf das die Ausgaben geschrieben werden. Die Felder der Bänder können mit jedem beliebigen Zeichen aus einem endlichen Alphabet A beschriftet werden. Der Kopf des Eingabe- und Ausgabebandes kann sich nur nach rechts bewegen.

Des Weiteren besitzen RAMs einen Speicher mit unendlich vielen Zellen, diese wiederum sind durchnummeriert (0, 1, 2...). Beim Start der RAM sind alle Zellen mit 0 initialisiert. Außerdem gibt es ein Programm (P) mit einer endlich numerierten Folge von Befehlen und eine zentrale Recheneinheit (CPU), die aus einem Akkumulator und einem Befehlszähler besteht.

Arithmetische Befehle

Transportbefehle

Sprungbefehle