Category Archives: Conferences and Workshops

CCR 2014: Open questions

For a slightly more detailed discussion of the following questions, see the PDF version of the Logic Blog.

Computable randomness

Let $\mathrm{CR}$ denote the class of computably random sets.

Question. (van Lambalgen’s theorem for $\mathrm{CR}$) Let $X$ be computably random, and let $Y$ be computably random relative to $X$. Is $X \oplus Y$ computably random?

Question. (Joseph Miller) Let $X$ be computably random. Is there an incomputable oracle $A$ such that $X$ is computably random relative to $A$?


Let $\textrm{High}(\textrm{CR}, \textrm{MLR})$ denote the class of oracles $A$ such that $\textrm{CR}^A \subseteq \textrm{MLR}$.

Question. (Joseph Miller) Is every set in  $\mathrm{High}(\mathrm{CR}, \mathrm{MLR})$ PA-complete?


We write $A \le_{\mathrm{CR}} B$ if $\mathrm{CR}^B \subseteq \mathrm{CR}^A$.

Question.  (Nies) Is $\le_{\mathrm{CR}}$ equivalent to $\le_\mathrm{T}$?


Martin-Löf randomness

Let $A \triangle B$ denote the symmetric difference of sets $A$, $B$.

Definition. (Kihara) We say that $A$ is ML-additive if $Z \in \mathrm{MLR}$ implies $Z \triangle A\in \mathrm{MLR}$ for each $Z$.

Clearly every low for ML-random is ML-additive.

Question. Is every ML-additive oracle low for ML-randomness?


Definition. (Yu) We say $A$ is absolutely low for $R$ if for all $Y$,

$R \in \mathrm{MLR}^Y \rightarrow R\in\mathrm{MLR}^{Y\oplus A}.$

Fact. (Stephan and Yu) Let  $A$ be $K$-trivial. Then $A$ is absolutely low for $\Omega$.

Question. (Yu) Is every set that is absolutely low for $\Omega$ $K$-trivial?

Definition. (Merkle) We say an oracle $A$ is super-absolutely low for $\Omega$  if for each oracle  $Y$ which is low for $\Omega$,

$\forall n(K^Y(n)=K^{A\oplus Y}(n)+O(1)).$

Note that every such set  is  absolutely low for $\Omega$ by definition. In fact it  must be  low for $K$, by letting $Y= \emptyset$. We ask the converse.

Question. (Merkle) Is every low for $K$ set super-absolutely low for $\Omega$?