Intrinsic Density, Asymptotic Computability, and Stochasticity

There are many computational problems which are generally 'easy' to solve but have certain rare examples which are much difficult to solve. One approach to studying these problems is to ignore the difficult edge cases. Asymptotic computability is one of the formal tools that uses this approach to study these problems. Asymptotically computable sets can be thought of as almost computable sets, however every set is computationally equivalent to an almost computable set. Intrinsic density was introduced as a way to get around this unsettling fact, and which will be our main focus.

Of particular interest for the first half of this dissertation are the intrinsically small sets, the sets of intrinsic density 0. While the bulk of the existing work concerning intrinsic density is focused on these sets, there are still many questions left unanswered. The first half of this dissertation shall endeavor to answer some of these questions. We shall prove some useful closure properties for the intrinsically small sets and apply them to prove separations for the intrinsic variants of asymptotic computability. We shall also completely separate hyperimmunity and intrinsic smallness in the Turing degrees and resolve some open questions regarding the relativization of intrinsic density.

For the second half of this dissertation, we shall turn our attention to the study of intermediate intrinsic density. We shall develop a calculus using noncomputable coding operations to construct examples of sets with intermediate intrinsic density. For almost all r in (0,1), this construction will yield the first known example of a set with intrinsic density r which cannot compute a set random with respect to the r-Bernoulli measure. Motivated by the fact that intrinsic density coincides with the notion of injection stochasticity, we shall apply these techniques to study the structure of the more well-known notion of MWC-stochasticity.