Ah, the low basis theorem does make more sense of Drucker’s paper. I thought Turing degrees wouldn’t be helpful because there are multiple consistent guessing oracles, but it looks like they are helpful. I hadn’t heard of PA degrees, will look into it.
Yeah, there’s a sort of trick here. The natural question is uniform—we want a single reduction that can work from any consistent guessing oracle, and we think it would be cheating to do different things with different oracles. But this doesn’t matter for the solution, since we produce a single consistent guessing oracle that can’t be reduced to the halting problem.
This reminds me of the theory of enumeration degrees, a generalization of Turing degrees allowing open-set-flavoured behaviour like we see in partial recursive functions; if the answer to an oracle query is positive, the oracle must eventually tell you, but if the answer is negative it keeps you waiting indefinitely. I find the theory of enumeration degrees to be underemphasized in discussion of computability theory, but e.g. Odifreddi has a chapter on it all the way at the end of Classical Recursion Theory Volume II.
The consistent guessing problem isn’t a problem about enumeration degrees. It’s using a stronger kind of uniformity—we want to be uniform over oracles that differently guess consistently, not over a set of ways to give the same answers, but to present them differently. But there is again a kind of strangeness in the behaviour of uniformity, in that we get equivalent notions if we do or do not ask that a reduction between sets A, B be a single function that uniformly enumerates A from enumerations of B, so there might be some common idea here. More generally, enumeration degrees feel like they let us express more naturally things that are a bit awkward to say in terms of Turing degrees—it’s natural to think about the set of computations that are enumerable/Σ1 in a set—so it might be a useful keyword.
Ah, the low basis theorem does make more sense of Drucker’s paper. I thought Turing degrees wouldn’t be helpful because there are multiple consistent guessing oracles, but it looks like they are helpful. I hadn’t heard of PA degrees, will look into it.
Yeah, there’s a sort of trick here. The natural question is uniform—we want a single reduction that can work from any consistent guessing oracle, and we think it would be cheating to do different things with different oracles. But this doesn’t matter for the solution, since we produce a single consistent guessing oracle that can’t be reduced to the halting problem.
This reminds me of the theory of enumeration degrees, a generalization of Turing degrees allowing open-set-flavoured behaviour like we see in partial recursive functions; if the answer to an oracle query is positive, the oracle must eventually tell you, but if the answer is negative it keeps you waiting indefinitely. I find the theory of enumeration degrees to be underemphasized in discussion of computability theory, but e.g. Odifreddi has a chapter on it all the way at the end of Classical Recursion Theory Volume II.
The consistent guessing problem isn’t a problem about enumeration degrees. It’s using a stronger kind of uniformity—we want to be uniform over oracles that differently guess consistently, not over a set of ways to give the same answers, but to present them differently. But there is again a kind of strangeness in the behaviour of uniformity, in that we get equivalent notions if we do or do not ask that a reduction between sets A, B be a single function that uniformly enumerates A from enumerations of B, so there might be some common idea here. More generally, enumeration degrees feel like they let us express more naturally things that are a bit awkward to say in terms of Turing degrees—it’s natural to think about the set of computations that are enumerable/Σ1 in a set—so it might be a useful keyword.