Turingmaschinen

betrachten nichtdeterministische Turingmaschinen mit

• einem Eingabeband (read only, von links nach rechts)
• einem Arbeitsband (read/write, beliebig)

eine Teilmenge der Zustandsmenge ist als akzeptierend festgelegt.

Eine solche Maschine akzeptiert eine Eingabe, falls es ihrem Berechnunsbaum einen Pfad von der Wurzel (Startkonfiguration) zu einem akzeptierenden Blatt gibt.

Die Menge (= Sprache) aller akzeptierten Wörter der Maschine M heißt L(M)