Klaus Ambos-Spies
(Heidelberg University)
On the Strongly Bounded Turing Degrees of C.E. Sets: Degrees Inside Degrees

We consider two variants of strongly bounded Turing reductions: An identity bounded Turing reduction (ibT-reduction for short) is a Turing reduction where no oracle query is greater than the input while a computable Lipschitz reduction (cl-reduction for short) is a Turing reduction where the oracle queries on input x are bounded by x+c for some constant c. Since ibT-reducibility is stronger than cl-reducibility and cl-reducibility is stronger than wtt-reducibility (where a weak truth-table (wtt-) reduction is a Turing reduction where the oracle queries are computably bounded in the inputs) we may look at the partial ordering of the computably enumerable (c.e.) ibT-degrees inside the cl-degree of a noncomputable c.e. set A and, similarly, at the partial ordering of the c.e. cl-degrees inside the wtt-degree of a noncomputable c.e. set A. In our talk we discuss some properties of these partial orderings.