Registermaschine (RAM)

Ein computernahes Modell (Random Access Machine), ähnlich einem GOTO-Programm mit Pointern und Registern.

• Unit-Cost-Modell: Jeder Befehl kostet 1 Zeiteinheit.
• Word-RAM: Registergröße ist auf logarithmische Anzahl von Bits beschränkt. Dies erlaubt eine polynomielle Simulation durch TMs.