4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are the sorts of probability distributions used? (I have a math background.) $\endgroup$ – David Oct 6 '15 at 7:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Jake Oct 6 '15 at 8:04
  • 4
    $\begingroup$ So in short it's because "0 with probability 100%", i.e. only one possible outcome, is a special case of a probability distribution. $\endgroup$ – Steve Jessop Oct 6 '15 at 10:49
  • $\begingroup$ Yes. Nicely put. $\endgroup$ – Jake Oct 6 '15 at 13:07
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.