Ψ Die Informatikseite

Unterabschnitte

• Nichtdeterministische Entscheidbarkeit
• NTM DTM

---

Nichtdeterminismus (Ergänzung)

Nichtdeterministische Entscheidbarkeit

Eine NTM entscheidet eine Sprache falls gilt:
1. und
2. Der Berechnungsbaum für jedes mögliche Eingabewort ist endlich, d.h. jedes Wort wird nach endlicher Zeit entweder akzeptiert oder verworfen.

NTM 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.

---