Asymptotic Notions of Computability

In computability theory, the classical definition of a Turing machine M solving a problem requires M to always halt and always give the right answer. If we relax the "always" to "almost always", we give rise to asymptotic notions of computability, where now M halts and gives correct answers only asymptotically always. There are four asymptotic notions of computability: generic, coarse, dense, and effective dense computability. This dissertation studies these asymptotic notions of computability, specifically the degree structures arising from the associated reducibilities. Two of the main results concerns minimal pairs: pairs of sets which are both noncomputable, and which have no common computational power. We prove that there are only measure-0 many minimal pairs for the generic degrees (which is in contrast with the classic Turing degrees, for which there are measure-1 many minimal pairs) and construct a $\Delta^0_2$ minimal pair for the coarse degrees. The third main result concerns attractive degrees. The formalization of the asymptotic notions of computability can be generalized to provide a notion of distance between Turing degrees, called the Hausdorff distance H. It turns out that for every set A, there are either measure-1 many sets which are at a distance 1 from A, or there are measure-1 many such sets which are at a distance 1/2 from A. The former are called dispersive, and the latter are called attractive. We provide a Kolmogorov-complexity flavored sufficient condition for a set to be attractive.