UC Berkeley

A generic computation of a subset A of the natural numbers consists of a computation which correctly computes most of the bits of A and never incorrectly computes any bits of A, but which does not necessarily give an answer for every input. This concept derives its motivation from a recent trend in complexity theory to study the complexity of a problem in terms of how difficult it is to compute the majority of size n instances of the problem, and not in terms of how difficult it is to compute the most difficult size n instances of the problem.

When considered from a purely recursion-theoretic point of view, generic computability proves to be somewhat counterintuitive. It can be shown to be, in some sense, as nontransitive as possible, and not only do minimal pairs not exist in this context, but even finite minimal sets of reals can be shown to not exist.

If we modify the definition of generic computation to make it transitive, we are naturally confronted with a deduction procedure in which the oracles, like the computations, are not required to be total. For this reason, “generic reduction” is defined in an inherently Pi11 manner. While studying generic reduction, we show that it is Pi11-complete, and we also present a characterization of the hyperarithmetic reals in terms of generic reduction.

Finally, we increase the level of abstraction, studying transitive and nontransitive deduction procedures with partial oracles. We provide a framework for discussing such reductions, we mention how various known results in recursion theory can be fit into this framework, and we discuss a number of seemingly trivial reductions, showing how subtle variations in the definitions can impact the produced reduction.