Nichtdeterministische Turingmaschinen

Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, dass man mehrere Sprungziele angibt bei jeder Anweisung. Allerdings werden wir dies nicht tun, sondern stattdessen ein Orakelband verwenden.

Das Orakelband selbst darf nur einmal gelesen werden, man kann sich auf dem Orakelband nicht hin- und her-bewegen, sondern nur nach rechts.

Wir haben nun also Maschinen mit zwei Eingaben $M(o,i)$, wobei $o$ das Orakelband ist.

TODO