Using Biased Coins as Oracles

摘要

While it is well known that a Turing machine equipped with the ability to flip a fair coin cannot compute more than a standard Turing machine, we show that this is not true for a biased coin. Indeed, any oracle set X may be coded as a probability px such that if a Turing machine is given a coin which lands heads with probability px it can compute any function recursive in X with arbitrarily high probability. We also show how the assumption of a non-recursive bias can be weakened by using a sequence of increasingly accurate recursive biases or by choosing the bias at random from a distribution with a non-recursive mean. We conclude by briefly mentioning some implications regarding the physical realisability of such methods.