Nichtdeterministische Turingmaschinen

Aus Einführung in die Theoretische Informatik und in die Mathematische Logik

Version vom 24. August 2018, 15:50 Uhr von Css (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, da…“)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Wechseln zu: Navigation, Suche

Analog zur Automatentheorie gibt es auch für Turingmaschinen eine nichtdeterministische Variante. Man kann sie auch analog definieren indem man es erlaubt, dass man mehrere Sprungziele angibt bei jeder Anweisung. Allerdings werden wir dies nicht tun, sondern stattdessen ein Orakelband verwenden.

Abgerufen von „http://uxul.de/4DQNJeqOrv/index.php?title=Nichtdeterministische_Turingmaschinen&oldid=239“