Überlege dir, wie du den nichtdeterministischen endlichen Automaten aus dem Beispiel auf der Seite Endlicher Automat in eine nichtdeterministische Turingmaschine überführen kannst. Schau dir die Übergangsrelation des endlichen Automaten an und konstruiere daraus die Übergangsrelation der nichtdeterministischen Turingmaschine. Du brauchst noch ein zusätzliches Tupel, um sicherzustellen, dass die Turingmaschine das Eingabewort zu Ende gelesen hat (wie in dem Beispiel oben).