In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite computable (...) ordinal α. It is known that jump traceability and superlowness coincide on the c.e. sets and we show that for every infinite computable ordinal α, jump traceability with ‐ or ‐bound of a c.e. set A is equivalent to the fact that. Finally, we consider the generalized truth‐table reducibilities and prove that for every (not necessarily the Turing jump of a c.e. set) set A and every limit computable ordinal α, iff. (shrink)

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤ wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very (...) close to the definition of superlow cuppability. Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set whose join with every low c.e. set is low. (shrink)

A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i. e. one whose Turing jump is truth-table reducible to the halting problem θ'. A negative answer to this question is provided by giving an explicit construction of a promptly simple set that (...) is not superlow cuppable. This problem relates to effective randomness and various lowness notions. (shrink)

This paper investigates indifferent sets for comeager classes in Cantor space focusing of the class of all 1-generic sets and the class of all weakly 1-generic sets. Jockusch and Posner showed that there exist 1-generic sets that have indifferent sets [10]. Figueira, Miller and Nies have studied indifferent sets for randomness and other notions [7]. We show that any comeager class in Cantor space contains a comeager class with a universal indifferent set. A forcing construction is used to show that (...) any 1-generic set, or weakly 1-generic set, has an indifferent set. Such an indifferent set can by computed by any set in GL2 which bounds the (weakly) 1-generic. We show by approximation arguments that some, but not all, ∆0 1-generic sets can compute an indifferent set 2 for themselves. We show that all ∆0 weakly 1-generic sets can compute 2 an indifferent set for themselves. Additional results on indifferent sets, including one of Miller, and two of Fitzgerald, are presented. (shrink)

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then there (...) is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (shrink)