Open Question Lists
- Randomness and computability: open questions (by me and André Nies). Bulletin of Symbolic Logic, 12(3):390–410, 2006.
- The original version is available (also as a dvi file), but I would recommend the updated version that André Nies keeps on his website.
- AIM/ARCC workshop in effective randomness: open problem list (prepared by Rebecca Weber).
- Also from 2006. Again, there is an original version and an updated version. Both are hosted by Rebecca Weber on the website for the Algorithmic Randomness FRG.
Open Questions
Below is a very short list of open questions. These are not meant to be the big questions in the field, but little questions that I would like to see solved.
- Question. Is there an infinite set $B\subseteq\omega$ such that whenever $X$ is 1-generic, $X\cup B$ is 1-generic?
- If we replace 1-generic with 1-random, then no such $B$ exists.
- Question (Lutz). Is there a straight line $L\subseteq\mathbb{R}^2$ such that every point on $L$ has effective Hausdorff dimension 1?
- Question. If $X$ is computably random, it there a non-computable $A$ such that $X$ is computably random relative to $A$?
- There is a computably random $X$ such that, for almost every oracle $A$, $X$ is not even Schnorr random relative to $A$. Also note that if the question is answered in the negative, the there would be a single $X$ witnessing the fact that every low for computably random oracle is computable.
