Monthly Archives: July 2013

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]