Authors: Richard Beigel
Abstract: Let A be any nonrecursive set. For each k ≥ 0, we show that there are functions (k+1)-truth-table reducible to A that are not k-weak-truth-table reducible to A; and we show that there are functions (k+1)-Turing reducible to A that are not k-Turing reducible to A. Intuitively, this means that k+1 queries to a nonrecursive oracle are strictly more useful than k queries to the same oracle (for the sake of computing functions), and that k+1 oracle answers from a nonrecursive oracle provide information that cannot be provided by any k answers from the same oracle.
The situation is different for decision problems. We say that a set A is parallel-supportive if, for all k, there is a language that is (k+1)-wtt reducible to A but not k-wtt reducible to A. A set A is supportive if, for all k, there is a language that is (k+1)-Turing reducible to A but not k-Turing reducible to A. We show that every degree above 0' contains a set that is supportive but not parallel-supportive. We show that every hyperimmune-free degree contains a set that is neither supportive nor parallel-supportive. We also construct a subclass of the hyperimmune degrees with the same property.
On the other hand we show that parallel-supportive and supportive sets exist in abundance: all jumps of sets, all generic sets, all nonrecursive semi-recursive sets, all nonrecursive r.e. sets, all nonrecursive n-r.e. sets, and almost all sets are supportive and parallel-supportive. In particular every nonrecursive Turing degree contains a set that is parallel-supportive and supportive. We also show that all nonrecursive nonsuperterse sets are supportive.