Open Question Lists
- Randomness and computability: open questions (by me and André Nies). Bulletin of Symbolic Logic, 12(3):390410, 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 QuestionsBelow 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 a noncomputable Turing degree $\bf d$ that is PA over every degree strictly below it?
- Question. If $X$ is computably random, is 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.