Turingmaschinen

• Nichtdeterministische TM

  • Zustandsübergange nicht deterministisch
  • Kann richtige Lösung „raten“

• Definition: Laufzeit einer Turingmaschine:

  • Zeit zwischen Lesen des ersten Eingabezeichens
  • Bis zum Schreiben des letzten Ausgabezeichens

Notizen: