| Summary: | In this thesis, we join the study of asymptotic computability, a project attempting to capture the idea that an algorithm might work correctly in all but a vanishing fraction of cases.
In collaboration with Hirschfeldt and Jockusch, broadening the original investigation of Jockusch and Schupp, we introduce dense computation, the weakest notion of asymptotic computability (requiring only that the correct answer is produced on a set of density 1), and effective dense computation, where every computation halts with either the correct answer or (on a set of density 0) a symbol denoting uncertainty. A few results make more precise the relationship between these notions and work already done with Jockusch and Schupp's original definitions of coarse and generic computability.
For all four types of asymptotic computation, including generic computation, we demonstrate that non-trivial upper cones have measure 0, building on recent work of Hirschfeldt, Jockusch, Kuyper, and Schupp in which they establish this for coarse computation. Their result transfers to yield a minimal pair for relative coarse computation; we generalize their method and extract a similar result for relative dense computation (and thus for its corresponding reducibility).
However, all of these notions of near-computation treat a set as negligible iff it has asymptotic density 0. Noting that this definition is not computably invariant, this produces some failures of intuition and a break with standard expectations in computability theory. For instance, as shown by Hamkins and Miasnikov, the halting problem is (in some formulations) effectively densely computable, even in polynomial time--yet this result appears fragile, as indicated by Rybalov.
In independent work, we respond to this by strengthening the approach of Jockusch and Schupp to avoid such phenomena; specifically, we introduce a new notion of intrinsic asymptotic density, invariant under computable permutation, with rich relations to both randomness and classical computability theory. For instance, we prove that the stochasticities corresponding to permutation randomness and injection randomness coincide, and identify said stochasticity as intrinsic density 1/2.
We then define sets of intrinsic density 0 to be effectively negligible, and classify this as a new immunity property, determining its position in the standard hierarchy from immune to cohesive for both general and Δ02 sets. We further characterize the Turing degrees of effectively negligible sets as those which are either high (a' ≥T 0") or compute a DNC (diagonally non-computable) function. In fact, this result holds over RCA0 , demonstrating the reverse-mathematical equivalence of the principles ID0 and DOM * DNR.
Replacing Jockusch and Schupp's negligibility (density 0) by effective negligibility (intrinsic density 0), we then obtain new notions of intrinsically dense computation. Finally, we generalize Rice's Theorem to all forms of intrinsic dense computation, showing that no set that is 1-equivalent to a non-trivial index set is intrinsically densely computable; in particular, in contrast to ordinary dense computation, we see that the halting problem cannot be intrinsically densely computable.
|
|---|
