Can Biased Coins Enhance Computational Power?

Title: Can Biased Coins Enhance Computational Power?

Abstract: This research explores the potential of using biased coins as oracles in computational systems. The study investigates whether allowing non-recursive biases can enhance the computational power of a Turing machine, traditionally known for its limitations in computational resources. The authors demonstrate that a Turing machine equipped with a biased coin can compute arbitrarily accurate estimates to the bias on its coin and even compute arbitrarily many bits of the binary expansion of the bias. They conclude by discussing the implications of these findings and suggesting further areas of research.

Main Research Question: Can the addition of randomness to the resources of a Turing machine enhance its computational power, especially when non-recursive biases are allowed?

Methodology: The study uses the concept of a probabilistic Turing machine (PTM), which is a Turing machine with a special randomizing state. When the machine is in this state, a fair coin is tossed, and the machine goes to the specified 1-state if the coin comes up heads and the 0-state if it comes up tails. The authors consider both recursive and non-recursive biases in their analysis.

Results: The authors show that a PTM can compute arbitrarily accurate estimates to the bias on its coin and then strengthen this to computing arbitrarily many bits of the binary expansion of the bias. They also demonstrate that there is a single PTM that acts as a universal o-machine, meaning it can simulate a given oracle with a given input to a given level of confidence.

Implications: The findings suggest that allowing non-recursive biases can significantly enhance the computational power of a Turing machine. This has implications for the field of computational complexity, as it challenges the traditional understanding of the limitations of Turing machines. The study also opens up avenues for further research in understanding the potential of randomness in computational systems.

Link to Article: https://arxiv.org/abs/0401019v1 Authors: arXiv ID: 0401019v1