1
$\begingroup$

Ever example of computation on a probabilistic Turing machine that I have read uses only a binary tree to show the computational branches of a probabilistic Turing machine. I know that an NTM may use as many branches as needed during a computation, so is this also the case for a PTM? Or is a PTM limited to only binary branching?

$\endgroup$
1
$\begingroup$

There are many ways to think of how a probabilistic Turing machine works. One way is to imagine that it has the ability to flip a fair coin (sample a random bit) at any point. In that case, it's reasonable to imagine a binary tree, where each branch corresponds to a coin flip -- the fact that we are choosing a random bit / flipping a 2-sided coin is why it is a binary tree. Another way to think of a probabilistic Turing machine is that it has an additional input tape that is full of random bits. There you could imagine a binary tree, which each branch corresponds to another bit on that additional input tape.

Typically probabilistic Turing machines can sample a random bit, i.e., a random number from the set {0,1}. If you want a random number from a different range, you must emulate that by repeatedly sampling random bits and doing something with them.

$\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.