Probabilistic Turing machine

Definition

A probabilistic Turing machine is a tuple $M = (Q, \Gamma, \sqcup, \Sigma, \delta_0, \delta_1, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}})$ with the following parts.

1. $Q$, $\Gamma$, $\sqcup$, $\Sigma$, $q_0$, $q_{\mathrm{acc}}$ and $q_{\mathrm{rej}}$ are as for a Turing machine with accepting state $q_{\mathrm{acc}}$ and rejecting state $q_{\mathrm{rej}}$.
2. $\delta_0$ and $\delta_1$ are two transition functions from $(Q \setminus \set{q_{\mathrm{acc}}, q_{\mathrm{rej}}}) \times \Gamma$ to $Q \times \Gamma \times \set{L, R}$.

At each step the machine chooses $\delta_0$ or $\delta_1$ with probability $1/2$ each, independently of all earlier choices, and moves by the chosen function. For an input $w$, the acceptance probability $\Pr[M \text{ accepts } w]$ is the probability that the run on $w$ reaches $q_{\mathrm{acc}}$. For a language $L \subseteq \Sigma^*$, the machine decides $L$ with bounded error if, for every $w \in \Sigma^*$, the run halts with probability $1$ and $$\Pr[M \text{ accepts } w] \ge 2/3 \text{ if } w \in L, \qquad \Pr[M \text{ accepts } w] \le 1/3 \text{ if } w \notin L.$$