Using biased coins as oracles
| dc.creator | Ord, Toby | |
| dc.creator | Kieu, Tien D. | |
| dc.date | 2004-01-23 | |
| dc.date.accessioned | 2026-07-07T03:20:50Z | |
| dc.date.available | 2026-07-07T03:20:50Z | |
| dc.description | 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. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0401019 | |
| dc.identifier | http://arxiv.org/abs/cs/0401019 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31968 | |
| dc.subject | Other Computer Science | |
| dc.subject | Quantum Physics | |
| dc.subject | F.1.1; F.1.2 | |
| dc.title | Using biased coins as oracles | |
| dc.type | text |