Direkt zum Inhalt

Lexikon der Mathematik: Nichtdeterminismus

mathematisches Konzept, das besagt, daß ein Berechnungsvorgang in einem Automaten oder einer Turing-Maschine sich in jedem Schritt so aufspalten kann, daß mehrere Rechnungen simultan nebeneinander existieren. Für den „Erfolg“ einer solchen Rechnung wird lediglich verlangt, daß mindestens eine dieser nichtdeterministischen Rechnungen auf die gewünschte Lösung führt.

Beispiele für Automaten, in die das Konzept des Nichtdeterminismus eingeht, sind NFAs, nichtdeterministische Kellerautomaten, nichtdeterministische linear beschränkte Akzeptoren, und nichtdeterministische polynomial zeitbeschränkte Turing-Maschinen. Grundsätzlich nichtdeterministische Konzepte sind darüber hinaus allgemeine Grammatiken und Semi-Thue-Systeme.

Nichtdeterminismus stellt ein idealisierendes, aber mathematisch und beweistechnisch sehr nützliches Konzept dar. In der Praxis kann ein nichtdeterministisches Verfahren letztlich nicht realisiert werden, sondern muß auf irgendeine Weise in ein deterministisches Verfahren überführt werden.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.