Übersicht Automaten
6. Registermaschine
Die Registermaschine (auch RAM = Random Access Machine) ist ein Rechnermodell, das einem realen Rechner sehr ähnlich ist. Ein realer Rechner kann alles, was auch eine Registermaschine kann. Da man auch beweisen kann, daß 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 reale Rechner. Dies ist in der Theoretischen Informatik von Vorteil, da man viele Aussagen an Hand der Turingmaschine leichter beweisen kann.