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

Article type: Research Article

Authors: Ambos-Spies, Klaus^{a; *} | Downey, Rod^b | Monath, Martin^c

Affiliations: [a] University of Heidelberg, Department of Mathematics and Computer Science, Im Neuenheimer Feld 205, D-69120 Heidelberg, Germany | [b] Victoria University, School of Mathematics and Statistics, P.O. Box 600, Wellington, New Zealand | [c] University of Heidelberg, Department of Mathematics and Computer Science, Im Neuenheimer Feld 205, D-69120 Heidelberg, Germany

Correspondence: [*] Corresponding author. [email protected].

Abstract: 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 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 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.

Keywords: Computably enumerable sets, maximal sets, hh-simple sets, dense simple sets, Post’s Programme, Turing degrees, wtt-reducibility, ibT-reducibility, jump, bounded jump, lowness, bounded lowness, bounded jump traceability, array (non)computability, totally ω-c.a. sets, Downey–Greenberg Hierarchy

DOI: 10.3233/COM-220432

Journal: Computability, vol. 13, no. 1, pp. 1-56, 2024