Thursday, 5 September 2013

Probabalistic Turing Machines

Another model of computation worth mentioning due to its relevance to the quantum computation model involves the notion of  probability and randomization. Suppose at some step of an algorithm there exists more than one possible future action. In the case of the nondeterministic Turing machine, the computation was allowed to take all possible actions.  Now, assuming that only one of these possible actions could be carried out by the algorithm, which one does the algorithm execute? Perhaps the algorithm will just choose one at random and proceed with the computation. More specifically, there could be a predefined probability distribution that determines which action to take. For a probabilistic Turing machine such a randomization procedure is used to determine which possible action the computation will carry out.

One way to implement  randomization in a probabilistic TM is by supplying an additional random bitstring of sufficient length along with the usual input bits. The bits forming this random bitstring serve the purpose of determining at random (or with a certain probability) exactly how the TM will proceed given multiple choices. This random bitstring can be thought of simply as a supply of "coin flips" where the existence of a \(1\) or \(0\) in a particular location of the random bitstring would inform the TM to take one of the actions over an alternate.

A consequence of the probabilistic TM is that the overall action and output could be different for a certain input due merely to pure chance. It could very well be the case for a single input string, depending on the series of probabilistically determined actions,  that this input would result in the TM reaching an accepting state in one instance and a rejecting state in another. This is a complication that will become relevant in later discussions in complexity theory when the success rate of a computation will be given probabilistically. However, it is  important to note that although randomized Turing machines may help in performing certain computations more efficiently, there is nothing that can be computed on these randomized computers that could not be computed in principle using the standard Turing machine models.

No comments :

Post a Comment