Computability

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 .

We call a sequence ( a n ) n of elements of a metric space nearly computably Cauchy if for every increasing computable function r : N → N the sequence ( d ( a r ( n + 1 ) , a r ( n ) ) ) n converges computably to 0. We show that there exists an increasing sequence of rational numbers that is nearly computably Cauchy and unbounded. Then we call a real number α nearly computable if there exists a computable sequence ( a n ) n of rational numbers that converges to α and is nearly computably Cauchy. It is clear that every computable real number is nearly computable, and it follows from a result by Downey and LaForte (Theoretical Computer Science 284 (2002) 539–555) that there exists a nearly computable and left-computable number that is not computable. We observe that the set of nearly computable real numbers is a real closed field and closed under computable real functions with open domain, but not closed under arbitrary computable real functions. Among other things we strengthen results by Hoyrup (Theory of Computing Systems 60 (2017) 396–420) and by Stephan and Wu (In New computational paradigms. First conference on computability in Europe, CiE 2005, Proceedings (2005) 461–469 Springer) by showing that any nearly computable real number that is not computable is weakly 1-generic (and, therefore, hyperimmune and not Martin-Löf random) and strongly Kurtz random (and, therefore, not K-trivial), and we strengthen a result by Downey and LaForte (Theoretical Computer Science 284 (2002) 539–555) by showing that no promptly simple set can be Turing reducible to a nearly computable real number.

Slaman and Wehner independently built a family of sets with the property that every non-computable degree can compute an enumeration of the family, but there is no computable enumeration of the family. We call such a family a Slaman–Wehner family. The original Slaman–Wehner argument relies on all sets in the family constructed being finite, and in particular, it diagonalizes against computably enumerated families using only finite differences. In this paper we ask whether this is a necessary feature, that is, whether there is a Slaman–Wehner family closed under finite differences. This question remains open but we obtain a number of interesting partial results which can be interpreted as saying that the question is quite hard.

First of all, no Slaman–Wehner family closed under finite differences can contain a finite set, and the enumeration of the family from a non-computable degree cannot be uniform (whereas, in the Slaman–Wehner construction, it is uniform). On the other hand, we build the following examples of families closed under finite differences which show the impossibility of several natural attempts to show that no Slaman–Wehner family exists: (1) a family that can be enumerated by every non-low degree, but not by any low degree; (2) a family that can be enumerated by any set in a given uniform list of c.e. sets, but which cannot be enumerated computably; and (3) a family that can be enumerated by a given Δ 2 0 set, but which cannot be computably enumerated.