# 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?

# $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]