Akzeptieren (Automaten- und Komplexitätstheorie)

Die Begriffe Akzeptieren und Entscheiden sind in der Automaten- und Komplexitätstheorie für viele in ihrer Wahrnehmung annähernd gleich. Sie sind es aber nicht genau. Aus diesem Wahrnehmungsunterschied haben Mathematiker folgenden formalen Unterschied konstruiert:

Es sei eine Menge von Eingaben gegeben. Von diesen möglichen Eingaben seien besondere herauszufiltern, die zu einer Menge A gehören.

Ein Algorithmus akzeptiert A, genau dann wenn er für genau die Elemente aus A terminiert und eine positive Antwort zurückliefert.

Ein Algorithmus entscheidet A, wenn er in jedem Falle eine Antwort liefert: ja im Fall, dass die Eingabe zu A gehört und nein sonst.

In den meisten Fällen ist es in der Automatentheorie unerheblich, zwischen Akzeptieren und Entscheiden zu unterscheiden. Nur in den Fällen, in denen nichtdeterministisch (siehe auch NP (Komplexitätsklasse)) gerechnet wird oder wenn es unendlich lange Berechnungen geben kann (siehe Rekursive Aufzählbarkeit), hier ist es sehr wohl von Bedeutung diesen sprachlich wahrgenommen Unterschied in unserer Definition zu nutzen.

Weblinks

 Wiktionary: akzeptieren – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen