Lowness properties for strong reducibilities and the computational power of maximal sets
Klaus Ambos‐Spies, Rodney G. Downey, Martin Monath · Computability · 2023
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 ([Formula: see text]-) 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 [Formula: see text]-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 [Formula: see text]-functional [Formula: see text], yields a computable approximation [Formula: see text] of the domain of [Formula: see text] together with a computable indicator function [Formula: see text] and a computable order [Formula: see text] such that, once the indicator becomes positive, i.e., [Formula: see text], the number of the mind changes of the approximation g on x after stage s is bounded by [Formula: see text] where, for total [Formula: see text], the indicator eventually becomes positive on almost all arguments x of [Formula: see text]. 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 [Formula: see text]-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 [Formula: see text]-degrees of the c.e. e.u.wtt-a.c. sets is strictly contained in the class of the array computable c.e. [Formula: see text]-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 [Formula: see text], i.e., if [Formula: see text] is ω-c.a., where [Formula: see text] is the [Formula: see text]-jump of A (Anderson, Csima and Lange ( Archive for Mathematical Logic 56(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 [Formula: see text], and we show that there exists a Turing complete set A such that [Formula: see text] is h-c.a. for any computable order h with [Formula: see text].