Using biased coins as oracles
<|reference_start|>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 that 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 $p_{X}$ such that if a Turing machine is given a coin which lands heads with probability $p_{X}$ 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.<|reference_end|>
@article{ord2004using,
    title={Using biased coins as oracles},
    author={Toby Ord and Tien D. Kieu},
    journal={arXiv preprint arXiv:cs/0401019},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0401019},
    primaryClass={cs.OH quant-ph}
}