Article ID Journal Published Year Pages File Type
4662152 Annals of Pure and Applied Logic 2008 15 Pages PDF
Abstract

A set A⊆ω is called computably enumerable (c.e., for short), if there is an algorithm to enumerate the elements of it. For sets A,B⊆ω, we say that A is bounded Turing reducible to (or alternatively, weakly truth table (wtt, for short) reducible to) B if there is a Turing functional, Φ say, with a computable bound of oracle query bits such that A is computed by Φ equipped with an oracle B, written . Let be the structure of the c.e. bT-degrees, the c.e. degrees under the bounded Turing reductions. In this paper we study the continuity properties in . We show that for any c.e. bT-degree , there is a c.e. bT-degree such that for any c.e. bT-degree , if and only if . We prove that the analog of the Seetapun local noncappability theorem from the c.e. Turing degrees also holds in . This theorem demonstrates that every is noncappable with any nontrivial degree below some (i.e. if and then ).

Related Topics
Physical Sciences and Engineering Mathematics Logic