Registermaschine

Die Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik. Registermaschinen sindTuring-vollständig, das heißt, sie sind prinzipiell zu allen Berechnungen in der Lage, die Turingmaschinen oder 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.