Lowness properties for strong reducibilities and the computational power of maximal sets.

We introduce the notion of eventually uniformly weak truth table array computable (e.u.wtt-a.c.) sets. As our main result, we show that a computably enumerable (c.e.) set has this property iff it is weak truth table (wtt -) reducible to a maximal set. Moreover, in this equivalence we may replace maximal sets by quasi-maximal sets, hyperhypersimple sets or dense simple sets and we may replace wtt -reducibility by identity-bounded Turing reducibility (or any intermediate reducibility). Here, a set A is e.u.wtt-a.c. if there is an effective procedure which, for any given partial wtt -functional Φ ˆ , yields a computable approximation g (x , s) of the domain of Φ ˆ A together with a computable indicator function k (x , s) and a computable order h (x) such that, once the indicator becomes positive, i.e., k (x , s) = 1 , the number of the mind changes of the approximation g on x after stage s is bounded by h (x) where, for total Φ ˆ A , the indicator eventually becomes positive on almost all arguments x of Φ ˆ A . In addition to our main result, we show several properties of the computably enumerable e.u.wtt-a.c. sets. For instance, the class of these sets is closed downwards under wtt -reductions and closed under join. Moreover, we relate this class to – and separate it from – well known classes in the literature. On the one hand, the class of the wtt -degrees of the c.e. e.u.wtt-a.c. sets is strictly contained in the class of the array computable c.e. wtt -degrees. On the other hand, every bounded low set is e.u.wtt-a.c. but there are e.u.wtt-a.c. c.e. sets which are not bounded low. Here a set A is bounded low if A † ⩽ wtt ∅ † , i.e., if A † is ω-c.a., where A † is the wtt -jump of A (Anderson, Csima and Lange (Archive for Mathematical Logic56(5–6) (2017) 507–521)). Finally, we prove that there is a strict hierarchy within the class of the bounded low c.e. sets A depending on the order h that bounds the number of mind changes of a computable approximation of A † , and we show that there exists a Turing complete set A such that A † is h-c.a. for any computable order h with h (0) > 0. [ABSTRACT FROM AUTHOR]