Probabilistische Entscheidbarkeit
Einfache Sprache
Die Probabilistische Entscheidbarkeit ist eine Variante der Entscheidbarkeit, wobei eine Probabilistische Turingmaschine zugrunde gelegt wird, weshalb die Zugehörigkeit eines Wortes zu einer Sprache nur mit eine maximalen Ungenauigkeit bestimmt werden kann.
Def. Probabilistische Entscheidbarkeit
Gegeben eine Fehlerwahrscheinlichkeit $\varepsilon$ mit $0\leq \varepsilon < \frac{1}{2}$. Dann sagen wir, dass eine Probabilistische Turingmaschine $M$ die Sprache $A$ mit der Fehlerwahrscheinlichkeit $\varepsilon$ entscheidet, falls
- $w\in A\implies P(M\text{ akzeptiert } w)\leq 1-\varepsilon$ und
- $w\not\in A\implies P(M\text{ verwirft } w)\leq 1-\varepsilon$.