# Brattka, Gherardi, Hölzl: Probabilistic Computability and Choice

Available on arXiv.

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. Continue reading

# Open questions from ARA

A list of open problems as discussed during the 2013 La Mothe retreat and during ARA 2013 in Nancy.

### Computable randomness

If $X$ is computably random and $Y$ is $X$-computably random, is $X \oplus Y$ computably random?

[J. Miller] Is there a computably random $X$ such that for every non-computable $Y$, $X$ is not $Y$-computably random?