Using biased coins as oracles

Toby Ord, Tien D. Kieu

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 b…