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.