Probabilistic Computability and Choice

Abstract

We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-valued function, which is a function that can be computed on a probabilistic Turing machine that receives a random binary sequence as auxiliary input. The machine can take advantage of this random sequence, but it always has to produce a correct result or to stop the computation after finite time if the random advice is not successful. With positive probability the random advice has to be successful. We characterize the class of Las Vegas computable functions in the Weihrauch lattice with the help of probabilistic choice principles and Weak Weak Kőnig's Lemma. Among other things we prove an Independent Choice Theorem that implies that Las Vegas computable functions are closed under composition. In a case study we show that Nash equilibria are Las Vegas computable, while zeros of continuous functions with sign changes cannot be computed on Las Vegas machines. However, we show that the latter problem admits randomized algorithms with weaker failure recognition mechanisms. The last mentioned results can be interpreted such that the Intermediate Value Theorem is reducible to the jump of Weak Weak Kőnig's Lemma, but not to Weak Weak Kőnig's Lemma itself. These examples also demonstrate that Las Vegas computable functions form a proper superclass of the class of computable functions and a proper subclass of the class of non-deterministically computable functions. We also study the impact of specific lower bounds on the success probabilities, which leads to a strict hierarchy of classes. In particular, the classical technique of probability amplification fails for computations on infinite objects. We also investigate the dependency on the underlying probability space.

Information and Computation (accepted for publication)

References in corpus (2)

• On the algebraic structure of Weihrauch degrees
• Computation with Advice

Cited by in corpus (19)

• On the algebraic structure of Weihrauch degrees
• On the Uniform Computational Content of Ramsey's Theorem
• On computability and disintegration
• Completion of Choice
• On the Uniform Computational Content of Computability Theory
• Finding descending sequences through ill-founded linear orders
• Weihrauch-completeness for layerwise computability
• Algebraic properties of the first-order part of a problem
• Dividing by zero - how bad is it, really?
• On the Uniform Computational Content of the Baire Category Theorem
• Projection operators in the Weihrauch lattice
• Computability and Analysis, a Historical Approach
• Game characterizations and lower cones in the Weihrauch degrees
• The Vitali Covering Theorem in the Weihrauch Lattice
• Borel-piecewise continuous reducibility for uniformization problems
• The Weihrauch degree of finding Nash equilibria in multiplayer games
• Stashing And Parallelization Pentagons
• Randomized Computation of Continuous Data: Is Brownian Motion Computable?
• Open sets in computability theory and Reverse Mathematics