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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What are the sorts of probability distributions used? (I have a math background.) $\endgroup$
    – David
    Commented Oct 6, 2015 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
    Commented Oct 6, 2015 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
    Commented Oct 6, 2015 at 10:49
  • $\begingroup$ Yes. Nicely put. $\endgroup$
    – Jake
    Commented Oct 6, 2015 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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