Nichtdeterministische Turingmaschine (NTM)

Eine NTM ist erweitert um eine Übergangsrelation (statt Funktion), die mehrere mögliche Nachfolgezustände erlaubt: $\delta :(Z\setminus E)\times \mathrm{\Gamma }\to \mathcal{P}(Z\times \mathrm{\Gamma }\times \{L,R,N\})$.
Eine Eingabe $w$ wird akzeptiert, wenn es mindestens einen Berechnungspfad gibt, der in einem akzeptierenden Endzustand endet.