A first open question

First of all: thanks to Rupert for putting up this blog. It looks great! My first post will be a question which I stumbled upon while working on effective Brownian motion with Kelty Allen:

Let $X$ be an ML random real and $Y$ some real. Is there always a sequence $R$ of rationals converging to $Y$ such that $X$ is random relative to $R$?

Of course the only interesting case is when $X$ is not ML-random relative to $Y$. Note that the answer is no if we further ask $R$ to be nondecreasing (take $X=\Omega$ and $Y=1-\Omega$: any nondecreasing sequence converging to $1-\Omega$ computes $1-\Omega$ so it derandomizes $X$)

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?

Randomness and Turing degrees

Continue reading

$K^X \ge_T X$

Written by Turetsky. Proved by Miller and Turetsky, and then vastly simplified by Bienvenu.

Proposition. For any real $X$, $K^X \ge_T X$.

Proof. $X$ is $X$-trivial. That is, $K^X(X\!\!\upharpoonright_n) \le K^X(n) + c$. Note that $K^X$ can compute the tree $\{\sigma \in 2^{<\omega} : K^X(\sigma) \le K^X(|\sigma|) + c\}$. This tree has finitely many infinite paths, and $X$ is one of them. As an isolated path, $K^X$ can compute $X$. [Source: The 2013 Logic Blog, page 31]