# Why is a deterministic Turing machine a special case of a probabilistic Turing machine?

I have no formal training in computer science as I have not yet taken any such classes, so perhaps this question appears naive. I was reading about BPP and it was claimed that a deterministic Turing machine is a special case of a probabilistic Turing machine. I don't understand why this is.

## 2 Answers

Deterministic turing machines have one transition at any given time. Nondeterministic machines are allowed to have multiple transitions out of a given state but can have just a single. Probabilistic turing machines pick one of the possible transitions and perform it based on a probability distribution. So if you make a deterministic turing machine then it is also a probabilistic turing machine where there is only ever one transition to choose from at any given time.

• What are the sorts of probability distributions used? (I have a math background.) – David Oct 6 '15 at 7:57
• There are a finite number of states to transition to so the distributions are pretty boring. Any assignment of probabilities to the possible transitions that adds up to 1 is fine. Short of something like Bernoulli distribution or a finite uniform distribution it wouldn't be anything I could give a name to. Wikipedia informs me that these are called Categorical distribution. You could probably consider conditioning on input but I don't think that buys you any power. In fact I'm pretty sure you get all the power you could want out of a coin flip. – Jake Oct 6 '15 at 8:04
• So in short it's because "0 with probability 100%", i.e. only one possible outcome, is a special case of a probability distribution. – Steve Jessop Oct 6 '15 at 10:49
• Yes. Nicely put. – Jake Oct 6 '15 at 13:07

Probabilistic Turing machines are similar to deterministic Turing machines, but have the additional power of tossing coins. If you never make use of this power, you get a deterministic Turing machine.

In a similar fashion, a non-deterministic Turing machine is allowed to make guesses, but if it doesn't it is just a deterministic Turing machine.