Ich hab hier eine Aufgabe wo mir absolut kein vernünftiger Ansatz einfällt. Vielleicht könnt ihr mir da ja noch weiterhelfen:
Sei M eine T-zeitbeschränkte nichtdeterministische Turing-Maschine, bei der jede Konfiguration maximal zwei direkte Nachfolgekonfigurationen hat. Zeigen Sie: M kann durch eine O(2hochT * T)-zeitbeschränkte deterministische Turing-Maschine simuliert werden.
Vielen Dank für Ratschläge oder Lösungsvorschläge
Dennis