Linear beschränkte Turingmaschine

Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des Bandes, auf dem die Eingabe steht, während der gesamten Berechnung nicht verlässt.

Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.