Topic Archive: generic computability
The idea of a negligible subset of the natural numbers is highly appealing; bad behavior often seems restricted to a “small” set. Asymptotic density (the usual solution) has been used repeatedly in many fields, most prominently in number theory. Unfortunately, this is largely incompatible with the computability theorist’s perspective; even 1-equivalent sets can have wildly different densities. However, by restricting to cases where density is computably invariant, we develop a new notion with appealing properties. We will characterize exactly how hard it is to make a set with intrinsic density, and uncover connections to both computability and randomness. In particular, we suggest that Post missed a very natural immunity property when developing his notions of hyperimmunity.