Probabilistische Turingmaschine
Einfache Sprache
Def. Probabilistische Turingmaschine
Eine Probabilistische Turingmaschine $M$ ist eine Nichtdeterministische Turingmaschine, bei der jeder nichtdeterministischer Schritt ein so genannter Münzwurfschritt in dem Sinne, dass es zwei gleich wahrscheinliche Auslegungsmöglichkeiten gibt, ist. Für jede mögliche Berechnung $b$ ergibt sich eine Eintrittswahrscheinlichkeit $P(b)$ für die Eingabe $w$ als
$$P(b) = 2^{-k}\,,$$wobei $k$ die Anzahl der Münzwurfschritte in $b$ sind.
Die Wahrscheinlichkeit das $M$ das Wort $w$ akzeptiert, ergibt sich als die Summe der Wahrscheinlichkeiten der akzeptierenden Berechnungen. Also
$$P(M\text{ akzeptiert } w) = \sum_{\begin{array}{c} b\text{ ist eine}\\\text{akzeptierende Berechnung}\end{array}}b$$Die Gegenwahrscheinlichkeit ergibt dann die Wahrscheinlichkeit das $M$ das Wort $w$ verwirft. Also
$$P(M\text{ verwirft } w) = 1- P(M\text{ akzeptiert } w)$$