In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can (unlike a deterministic Turing machine) have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

In the case of equal probabilities for the transitions, probabilistic Turing machines can be defined as deterministic Turing machines having an additional "write" instruction where the value of the write is uniformly distributed in the Turing machine's alphabet (generally, an equal likelihood of writing a "1" or a "0" on to the tape). Another common reformulation is simply a deterministic Turing machine with an added tape full of random bits called the "random tape".

A quantum computer (or quantum Turing machine) is another model of computation that is inherently probabilistic.

A probabilistic Turing machine is a type of nondeterministic Turing machine in which each nondeterministic step is a "coin-flip", that is, at each step there are two possible next moves and the Turing machine probabilistically selects which move to take.

A probabilistic Turing machine can be formally defined as the 7-tuple ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$, where

At each step, the Turing machine probabilistically applies either the transition function ${\displaystyle \delta _{1}}$ or the transition function ${\displaystyle \delta _{2}}$. This choice is made independently of all prior choices. In this way, the process of selecting a transition function at each step of the computation resembles a coin flip.

The probabilistic selection of the transition function at each step introduces error into the Turing machine; that is, strings which the Turing machine is meant to accept may on some occasions be rejected and strings which the Turing machine is meant to reject may on some occasions be accepted. To accommodate this, a language ${\displaystyle L}$ is said to be recognized with error probability ${\displaystyle \epsilon }$ by a probabilistic Turing machine ${\displaystyle M}$ if:

As a result of the error introduced by utilizing probabilistic coin tosses, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. One such notion that includes several important complexity classes is allowing for an error probability of 1/3. For instance, the complexity class BPP is defined as the class of languages recognized by a probabilistic Turing machine in polynomial time with an error probability of 1/3. Another class defined using this notion of acceptance is BPL, which is the same as BPP but places the additional restriction that languages must be solvable in logarithmic space.