nichtdeterministisches

Nichtdeterminismus, auch als nichtdeterministisches Verhalten bezeichnet, ist ein Begriff aus der Mathematik und Informatik, der beschreibt, dass aus einem gegebenen Zustand und einer Eingabe mehrere mögliche Folgezustände resultieren können. In einem nichtdeterministischen Modell existieren daher mehrere, voneinander unabhängige Rechenpfade. Die eigentliche Ausführung eines Systems wird oft als Sammlung möglicher Abläufe verstanden, statt als einzelner determinierter Verlauf.

In der Automatentheorie spielen nichtdeterministische endliche Automaten (NFA) eine zentrale Rolle. Im Gegensatz zu deterministischen endlichen Automaten (DFA) kann ein NFA bei einem Übergang in mehrere Folgezustände wechseln oder sogar ohne Eingabe in verschiedene Zustände springen. Eine akzeptierte Sprache ist jene, für die es einen Pfad gibt, der am Ende akzeptiert. NFAs können in äquivalente DFAs umgewandelt werden (Subset-Konstruktion), wenngleich NFAs oft kompakter formuliert werden können.

Nichtdeterministische Turingmaschinen (NTM) erweitern dieses Konzept auf das Reich der Berechnungstheorie: Auch hier existieren mehrere mögliche Rechenwege aus einem Zustand heraus; eine Eingabe wird akzeptiert, wenn irgendein Pfad zu einem akzeptierenden Zustand führt. In der Komplexitätstheorie dient dieses Modell zur Definition der Klasse NP; die Frage, ob P = NP, bleibt eines der zentralen offenen Probleme.

In praktischen Kontexten treten Nichtdeterminismen auch in parallelen und verteilten Systemen auf, etwa durch konkurrierende Prozesse oder asynchrone Ausführung. Dort erschwert Nichtdeterminismus Vorhersagen, wird aber durch formale Modelle und Modellprüfung adressiert.

Zusammenfassend bezeichnet Nichtdeterminismus die Eigenschaft, dass mehrere mögliche Abläufe existieren, statt eines einzigen vorgegebenen Pfades.hnung