Skip to main content

Formale Sprachen und Automatentheorie

Die theoretische Informatik befasst sich mit der Berechenbarkeit von Problemen und wie diese effizient gelöst werden können. Diese Probleme werden in formale Sprachen „formuliert“, welche uns erst die Untersuchung und Berechnungen ermöglichen.

Turingmaschinen

Turingmaschinen

Turingmaschinen spielen in der theoretischen Informatik eine große Rolle. Es handelt sich um mathematische Modelle für eine Maschine oder einen Automaten. Es gibt kein leistungsfähigeres Berechnungsmodell als das der Turingmaschine.

Random Access Machine

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.