Computability relative to generic sets
If a set is computable using sufficiently random or generic information, then is it computable in the usual sense?
(under construction)
A well-known theorem by de Leeuw, Moore, Shannon, and Shapiro states that if a set is computable relative to a positive-measure set of oracles, the it is computable outright. This theorem is supposed to show that computability is highly robust: “almost surely computable” is just plain old computable.
This can be generalized in two dimensions: the computability concept, and the randomness notion. In one direction, Sacks independently proved that if a set is hyperarithmetic in a positive-measure set of parameters, then it is just hyperarithmetic. In the other direction, Hinman and Thomason proved that if a set is computable (or hyperarithmetic) in a nonmeager set of oracles, then it is just computable (or hyperarithmetic).
In this project, I aim to see how far this phenomenon can be pushed. For example, can we replace the randomness notion with any notion of genericity? Can we replace the computability concept with a more general notion of definability?