Satz Redundanz von Nichtdeterminismus

Einfache Sprache

DTM und NDTM sind gleich Ausdrucksstarkt.

Def. Satz Redundanz von Nichtdeterminismus

Beweisidee:

Simulation einer NTM $\mathcal{M}$ durch eine 3-DTM $\mathcal{N}$, wie folgt:

Band 1.

Das Eingabewort wird hier gespeichert und nicht verändert. D.h. nur gelesen bei Bedarf.

Band 2.

Wir definieren $r:=\max\{|\delta(q,a|:q\in Q,a\in\Gamma\}$ den maximalen Nichtdeterminismusgrad. => Zu wie viele nächsten verschiedenen Zuständen es geht von einem zustand, das maximum davon Wir zählen auf dem 2. Band alle möglichen Wörter in $\{1,\ldots,r\}^*$. Wir verwenden diese Wörter um dort die nichtdeterministische Berechnung von $\mathcal{M}$ auf der Eingabe auf dem 3. Band zu simulieren.

Band 3.

Es wird jeder mögliche Lauf von $\mathcal{M}$ auf der Eingabe simuliert => Stichwort Breitensuche