Using biased coins as oracles

Details Using biased coins as oracles Using biased coins as oracles

2004-01-23

arxiv.org/abs/cs/0401019v1

Computer Science

Other Computer Science

11 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Using biased coins as oracles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Using biased coins as oracles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using biased coins as oracles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7795