Well, I guess describing a model of a computably enumerable theory, like PA or ZFC counts. We could also ask for a model of PA that’s nonstandard in a particular way that we want, e.g. by asking for a model of PA+¬Con(PA), and that works the same way. Describing a reflective oracle has low solutions too, though this is pretty similar to the consistent guessing problem. Another one, which is really just a restatement of the low basis theorem, but perhaps a more evocative one, is as follows. Suppose some oracle machine T has the property that there is some oracle that would cause it to run forever starting from an empty tape. Then, there is a low such oracle.
(Technically, these aren’t decision problems, since they don’t tell us what the right decision is, but just give us conditions that whatever decisions we make have to satisfy. I don’t know what to say instead; this is more general then e.g. promise problems. Maybe I’d use something like decision-class problems?)
All these have a somewhat similar flavour by the nature of the low basis theorem. We can enumerate a set of constraints, but we can’t necessarily compute a single object satisfying all the constraints. But the theorem tells us that there’s a low such object.
I don’t know what the situation is for subsets of the digits of Chaitin’s constant. Can it be as hard as the halting problem? You might try to refute this using some sort of incompressibility idea. Can it be low? I’d expect not, at least for computable subsets of indices of positive density. Plausibly computability theorists know about this stuff. They do like constructing posets of Turing degrees of various shapes, and they know about which shapes can be realized between 0 and the halting degree 0′. (E.g. this paper.)
Are there any other nice decision problems that are low? A quick search only reveals existence theorems.
Intuitive guess: Can we get some hierarchy from oracles to increasingly sparse subsets of the digits of Chaitin’s constant?
Well, I guess describing a model of a computably enumerable theory, like PA or ZFC counts. We could also ask for a model of PA that’s nonstandard in a particular way that we want, e.g. by asking for a model of PA+¬Con(PA), and that works the same way. Describing a reflective oracle has low solutions too, though this is pretty similar to the consistent guessing problem. Another one, which is really just a restatement of the low basis theorem, but perhaps a more evocative one, is as follows. Suppose some oracle machine T has the property that there is some oracle that would cause it to run forever starting from an empty tape. Then, there is a low such oracle.
(Technically, these aren’t decision problems, since they don’t tell us what the right decision is, but just give us conditions that whatever decisions we make have to satisfy. I don’t know what to say instead; this is more general then e.g. promise problems. Maybe I’d use something like decision-class problems?)
All these have a somewhat similar flavour by the nature of the low basis theorem. We can enumerate a set of constraints, but we can’t necessarily compute a single object satisfying all the constraints. But the theorem tells us that there’s a low such object.
I don’t know what the situation is for subsets of the digits of Chaitin’s constant. Can it be as hard as the halting problem? You might try to refute this using some sort of incompressibility idea. Can it be low? I’d expect not, at least for computable subsets of indices of positive density. Plausibly computability theorists know about this stuff. They do like constructing posets of Turing degrees of various shapes, and they know about which shapes can be realized between 0 and the halting degree 0′. (E.g. this paper.)