Theoretische Informatik - Nichtdeterminismus (Ergänzung)

Home

Bücher Links Impressum

Nächste Seite: Komplexitätsklassen Aufwärts: Entscheidbarkeit Vorherige Seite: Andere unentscheidbare Probleme Inhalt

Unterabschnitte

Nichtdeterminismus (Ergänzung)

Nichtdeterministische Entscheidbarkeit

Eine NTM $\tau$ entscheidet eine Sprache

falls gilt:
1. $L(\tau)=L$ und
2. Der Berechnungsbaum für jedes mögliche Eingabewort $w\in\{0,1\}^{*}$ ist endlich, d.h. jedes Wort wird nach endlicher Zeit entweder akzeptiert oder verworfen.

NTM $\rightarrow$ DTM

Aus jeder NTM kann man eine DTM machen. Man geht dabei den Berechnungsbaum mit einer Breitensuche durch¹⁹.

Fußnoten

... durch ¹⁹: Hier darf man keine Tiefensuche verwenden. Das kann unter Umständen ins Auge gehen, da ein Berechnungsbaum ins Unendliche ragt, während ein anderer schon lange akzeptiert hat, man aber im unendlichen Berechnungsbaum immer tiefer geht und nie zum Ende kommt.