Nichtdeterministische Turingmaschine
Einfache Sprache
Eine nichtdeterministische Turingmaschine ist eine Turingmaschine dessen Transitionsfunktion mehrere Folgezustand haben kann, zwischen den zufällig ausgewählt wird.
Def. Nichtdeterministische Turingmaschine
Eine nichtdeterministische Turingmaschine ist wie eine TM nur das die Transitionsfunktion ist definiert als:
$$\delta:(Q\setminus\{q_{acc},q_{rej}\})\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R,N\})$$