WITH TINY USE
JOHANNA N. Y. FRANKLIN, NOAM GREENBERG, FRANK STEPHAN, AND GUOHUA WU
Abstract. In contrast with the notion of complexity, a setAis called anti- complex if the Kolmogorov complexity of the initial segments ofAchosen by a recursive function is always bounded by the identity function. We show that, as for complexity, the natural arena for examining anti-complexity is the weak-truth table degrees. In this context, we show the equivalence of anti- complexity and other lowness notions such as r.e. traceability or being weak truth-table reducible to a Schnorr trivial set. A setAis anti-complex if and only if it is reducible to another setBwithtiny use, whereby we mean that the use function for reducingAtoBcan be made to grow arbitrarily slowly, as gauged by unbounded nondecreasing recursive functions. This notion of reducibility is then studied in its own right, and we also investigate its range and the range of its uniform counterpart.
1. Introduction
In a recent talk [25], Nies gave a general framework for relating lowness notions and their dual highness notions with what he names “weak reducibilities” (with a prominent example being6LR, the low-for-randomness partial ordering). Even be- fore their extensive investigation in the context of effective randomness, in classical recursion theory, both strong and weak reducibilities gave rise to lowness and high- ness classes. For example, truth-table (or weak truth-table) reducibility induced the classes of superlow and superhigh Turing degrees; in the other extreme, hy- perarithmetic reducibility (and the hyperjump) allowed the definition of the useful class of hyperlow hyperdegrees (see [30]). In this paper we give a new notion of relative strength which, surprisingly, leads to a lowness notion which is analogous to familiar ones in the context of the weak truth-table degrees.
The motivation for our notion, which we call “Turing reducibility with tiny use”, comes from recent investigations into strengthenings of weak truth-table re- ducibility in a direction which is incomparable with truth-table reducibility, namely computable Lipshitz reducibility 6cl (also known as 6sw, strong weak truth-table reducibility) and identity-bounded Turing reducibility6ibT, and also, to a smaller extent, related reducibilities such as6C and6H. These reducibilities were intro- duced in order to combine the traditional Turing reduction, that is, computation of the membership relation using an oracle, and calibration of relative randomness, usually on the domain of left-r.e. reals (see [2]).
The second author was supported in part by the Marsden grant of New Zealand and by NTU grant RG58/06, M52110023. The third author is supported in part by the NUS grants R252- 000-308-112 and R252-000-420-112; he worked on this paper while on sabbatical leave to Victoria University of Wellington in October and November 2010.
1
Recall that computable Lipschitz reductions are weak truth-table reductions in which the use function is bounded byn+cfor some constantc. The idea of a Turing reduction with tiny use is to further restrict the use function of the reduction to recursive functions which grow more and more slowly. A set A is reducible to a set B with tiny use if one can use arbitrarily little of the oracle B to compute arbitrarily much ofA, so not only does B contain all the information that Ahas, it compresses that information arbitrarily well. To make the definition precise, we invoke the following definition first made by Schnorr [31]: an order function (or simply anorder) is a recursive function which is nondecreasing and unbounded.
Definition 1.1. LetA, B∈ {0,1}ω. We say thatAisreducible toB with tiny use and writeA6T(tu)B if for every order functionh, there is a Turing reduction of AtoB whose use function is bounded byh.
Let us agree on some notation and terminology. If Φ is a Turing reduction (a Turing machine with an oracle) and ΦB=A, then we let, for everyn < ω, theuse of this reduction,ϕ(n) =ϕB(n), bem+ 1, wheremis the largest number which is queried by Φ while computing An. HereA nis the string A(0)A(1). . . A(n−1), and we assume that before computing A(n) = ΦB(n), Φ first computes ΦB(m) for all m < n. Thus B ϕ(n) is the shortest initial segment of B which, serving as an oracle for Φ, outputsAn.
The motivation for considering reducibility with tiny use comes from a result of Greenberg and Nies [12], who showed that ifAis a recursively enumerable, strongly jump-traceable set and B is anω-r.e. random set, then A is reducible to B with tiny use. In fact, in [13] it is shown that this is a characterisation of the strongly jump-traceable r.e. sets.
We note here that this reducibility is unlike the more standard Turing reducibility (and, in fact, all reducibilities mentioned thus far) in that its domain and range are nontrivial. For instance, we will see that it is not the case that every set A is reducible to some set B with tiny use. Therefore, we will often speak of the domain and range of6T(tu). Furthermore, this reducibility is not reflexive, which suggests that the notation <T(tu) would be more appropriate. However, since the reducibility is not irreflexive, we will keep the notation 6T(tu) and simply note for the reader that the only sets reducible to themselves with tiny use are the recursive sets (Proposition 2.8). When the context excludes the possibility of B being recursive, we will writeA <T(tu)B.
The relation 6T(tu) yields a lowness notion in a very simple way: we consider the domain of the relation, i.e. the collection of sets Afor which there is some B such that A6T(tu)B. An immediate analysis of6T(tu)shows that this collection is invariant in the weak truth-table degrees and induces an ideal in these degrees.
This ideal can be characterised in three other ways, for which we make a sequence of definitions.
Recall that for their work characterising lowness for Schnorr randomness as re- cursive traceability, extending a fundamental result of Terwijn and Zambella [33], Kjos-Hanssen, Merkle and Stephan [16] defined a set A to becomplex if there is an order function f such that C(A f(n)) > n for all n (here C denotes plain Kolmogorov complexity1). They showed that a setAis complex if and only if there
1Recall that amachineis a partial recursive functionM:{0,1}∗→ {0,1}∗. IfMis a machine, then theM-complexity of a stringσ in the range ofM, denoted byCM(σ), is the length of the
is some diagonally nonrecursive function f 6wtt A. As an analogue, we make the following definition:
Definition 1.2. A set A ∈ {0,1}ω is anti-complex if for every order function f, for almost alln,C(Af(n))6n.
Thus anti-complexity is a mirror image of complexity: complexity indicates incom- pressibility in that one can effectively find locations of high complexity, whereas anti-complexity denotes a high level of compressibility and hence low information content. We note that the concept does not actually depend on the choice of Kol- mogorov complexity; by Lemma4.2, we could also use prefix-free complexity.
Traceability, in both its recursive and r.e. versions, is a notion which has turned out to be extremely useful in algorithmic randomness and classical recursion theory.
Recent work of Franklin and Stephan [11] has indicated that it is also useful in the context of strong reducibilities. They have shown that the class of Schnorr trivial sets is invariant in the truth table degrees and that a set is Schnorr trivial if and only if its truth-table degree is recursively traceable (this means that only the functions which are truth-table reducible to the set receive a recursive trace, all with a uniform bound of some order). Since the natural environment for6T(tu) is the weak truth-table degrees, we find that traceability in these degrees plays a role here. The characterisation theorem is as follows.
Theorem 1.3. The following are equivalent for a setA.
(1) There is a setB such thatA6T(tu)B.
(2) A is anti-complex.
(3) degwtt(A)is r.e. traceable.
(4) A is weak truth-table reducible to a Schnorr trivial set.
We note that the equivalence of (3) and (4), together with Franklin and Stephan’s result, yields a theorem which has no explicit connection to effective randomness, and yet we currently do not know of any direct proof that does not involve6T(tu)
and Kolmogorov complexity: a weak truth-table degree a is r.e. traceable if and only if there is some weak truth-table degree b>awhich contains a set B whose truth-table degree is recursively traceable.
As the existence of an order function witnessing r.e. traceability implies that every order function is such a witness (see Lemma 3.3), it follows that a Turing degreeais r.e. traceable if and only if every weak truth-table degree contained in a is r.e. traceable. Theorem 1.3then implies the following characterisation of r.e.
traceability in the Turing degrees.
Theorem 1.4. The following are equivalent for a Turing degreea.
(1) a is r.e. traceable.
(2) Every setA∈ais anti-complex.
(3) Every setA∈ais weak truth-table reducible to a Schnorr trivial set.
Among r.e. degrees, we note that the equivalence between array recursiveness and r.e. traceability holds in the weak truth-table degrees. Recall that a very strong array F¯ =hFnin<ω consists of a recursive sequence of pairwise disjoint finite sets
shortest stringτ∈M−1{σ}. Ifσis not in the range ofM, then we writeCM(σ) =∞. A machine U isoptimal if for every machine M there is some constant csuch that for all σ ∈ {0,1}∗, CU(σ)6CM(σ) +c. ThenCdenotesCU for some fixed optimal machineU.
such that for alln,|Fn+1|>|Fn|, and that an r.e. setAis ¯F-ANR if for every r.e.
set B there are infinitely manynsuch that A andB coincide on Fn. Most of the equivalences in the following theorem are known, but we prove the equivalence of (4) and (5) in Section4.
Theorem 1.5. The following are equivalent for a weak truth-table degree a con- taining an r.e. set.
(1) For no very strong array F¯ doesa contains an F-ANR set.¯ (2) For some very strong arrayF¯,a contains noF¯-ANR set.
(3) There is anω-r.e. function that dominates all functions in a.
(4) a is r.e. traceable.
(5) For allA∈a,A <T(tu)K (here K={e:ϕe(e)↓}is the halting set).
This result implies the result from [7] that the array recursive r.e. wtt-degrees form an ideal.
Together with6T(tu), we also investigate a uniform version6uT(tu), where a single reduction witnesses the relation6T(tu). This relation is, in general, much stronger than 6T(tu) (for example, if A is nonrecursive andA 6uT(tu) B, then B is high, which we show does not hold for6T(tu)), but their domains are the same, and so the condition “there is a set B such that A 6uT(tu) B” can be added as a fifth equivalent condition in Theorem 1.3. An even stronger version of this theorem which bounds the complexity of suchB is Theorem3.8. We prove Theorem1.3 in Section 3. In Section4 we investigate the distribution of the anti-complex sets in the Turing degrees, discuss high and random degrees, prove Theorems1.4and1.5, and investigate anti-complexity and tiny use in the r.e. degrees. One corollary of our investigations is an answer to Question 7.5.13 from Nies’s book [23].
Theorem 1.6. There is a high Turing degree which does not contain a partial- recursively random set.
The motivation behind this question is to find an exact boundary between weaker notions of randomness, such as Schnorr randomness and recursive randomness, which occur in every high Turing degree, and stronger notions of randomness, such as Martin-L¨of randomness, which do not. We provide a proof of Theorem 1.6 in Section4.
In Section5, we investigate the dual highness notions: the setsBfor which there is a nonrecursive setAsuch thatA <T(tu)B (or the more stringentA <uT(tu)B).
We investigate the situation in both the hyperimmune-free (0-dominated) degrees and in the r.e. and ∆02degrees. For example, we show that every high Turing degree contains setsA andB such thatA <uT(tu)B and that for every nonrecursive r.e.
setB there is some nonrecursive r.e. set Asuch thatA <T(tu)B.
Throughout the paper, we also mention strong reducibilities (such as truth-table and many-one) with tiny use. In particular, in Theorem 3.11 we use truth-table reducibility with tiny use to obtain a new characterisation of Schnorr triviality:
a set A is Schnorr trivial if and only if it is truth-table reducible to some set B with tiny use. This result strengthens the intuition, arising from Franklin and Stephan’s characterisation of Schnorr triviality in terms of recursive traceability in the truth-table degrees, that strong reducibilities have deep connections with weak randomness notions. Along this vein, Day [1] has recently given characterisations of both Schnorr randomness and computable randomness as the complements of
the domains of relations weaker than truth-table reducibility with tiny use. For example, he showed that a setAis not Schnorr random if and only if there is some set B such thatA6ttB with use function which does not dominate n−h(n) for some order functionh.
In the following section we supply the rest of the basic definitions and make some basic observations.
2. Basics We first define the uniform reducibility.
Definition 2.1. Let A, B ∈ {0,1}ω. We say that A is uniformly reducible to B with tiny use(and writeA6uT(tu)B) if there is a Turing reduction ΦB =Awhose use function is dominated by every order function.
Observation 2.2.
(1) If A6uT(tu)B, thenA6T(tu)B.
(2) If A6T(tu)B, thenA6wttB.
Remark 2.3. Despite the fact that our reductions imply weak truth-table reduc- tions, we prefer the notation6T(tu)to6wtt(tu). This is because a weak truth-table reduction first marks the use, then queries the oracle and finally computes the value, whereas Turing reductions with tiny use would — at least in the uniform case — not do the operations in this order, as otherwise the use is automatically bounded from below by an order function.
Next, we see that our relations are invariant in the wtt-degrees.
Observation 2.4. If A 6wtt E and E 6T(tu) B, then A 6T(tu) B; if A 6T(tu)
E and E 6wtt B, then A 6T(tu) B. Thus the relation 6T(tu) is invariant on weak truth-table degrees and is preserved by increasing the degree on the range and decreasing the degree on the domain. The same holds for6uT(tu).
Observation 2.5. For a fixed B ∈ {0,1}ω, the classes {A : A 6T(tu) B} and {A:A6uT(tu)B} are wtt-ideals.
Another formulation for our notions uses not the use functions but their discrete inverses. If ΦB =A is a Turing reduction, then for everyn < ω we let Φ(B n) be the longest initial segment ofAwhich is calculated by Φ querying the oracleB only on numbers smaller thann.
In general, if f: ω → ω is a nondecreasing and unbounded function but not necessarily recursive, we let f−1, the discrete inverse of f, be defined by letting f−1(k) be the greatestnsuch thatf(n)6k(let us assume thatf(0) = 0, as it is for every use function, sof−1is total; otherwisef−1is defined for almost all numbers).
That is, iff(n+ 1)> f(n), then the interval [f(n), f(n+ 1)) gets mapped byf−1 ton. We note that iff is recursive (and is thus an order function), then so isf−1. According to this definition, if ΦB =A with use ϕ, then for alln, Φ(B n) = Aϕ−1(n).
Observation 2.6. Let f andg be nondecreasing and unbounded.
(1) If f boundsg, theng−1 boundsf−1. (2) f−1−1
boundsf. If f grows more slowly than the identity function, that is, if for alln,f(n+ 1)6f(n) + 1, then f−1−1
=f.
This observation suffices for the following corollary, noting that when investigating slow-growing recursive orders, we may assume that the orders grow slower than the identity function.
Corollary 2.7. Let A, B∈ {0,1}ω.
(1) A 6T(tu) B if and only if for every order function g, there is a Turing reductionΦB=A such that the mapn7→ |Φ(Bn)| boundsg.
(2) A 6uT(tu) B if and only if there is a Turing reduction ΦB =A such that the map n7→ |Φ(B n)| dominates every recursive function. (A function which dominates every recursive function is called dominant.)
Some other basic results follow.
Proposition 2.8. Let A, B∈ {0,1}ω. (1) If A6T(tu)A, then Ais recursive.
(2) If Ais recursive, then A6uT(tu)B.
Proof. Letf(n) =n+ 1. If ΦA =A and for allnwe have Φ(An)⊇A n+ 1, then we can recursively compute A(n) by applying Φ toA n, which we already computed. For (2), use a reduction ΦB=Awhose use function is a constant 0.
Corollary 2.9. IfA6T(tu)B andAis nonrecursive, thendegwtt(A)<degwtt(B).
As a result, if degwtt(B) is minimal, then everyA6T(tu)B is recursive.
Proposition 2.10. Let B ∈ {0,1}ω. If there is some nonrecursive A such that A6uT(tu)B, thenB is high.
Recall that a setB is high ifB0 >T ∅00.
Proof. For any Turing reduction, if ΦB is total, then the map n 7→ |Φ(B n)| is computable in B (indeed, weak truth-table reducible to B). The map Φ which witnesses A 6uT(tu) B dominates every recursive function. By Martin [21], this
map has high Turing degree.
We will review the situation in Proposition2.10in greater detail in Section 5.
3. Sets bounded by other sets with tiny use
In this section we prove Theorem1.3. It will follow from Theorem3.8and Propo- sitions3.4,3.9and3.10.
3.1. Anti-complexity and traceability. For functions f, g: ω → ω, we write f 6+gif there is some constantc such thatg+cboundsf.
Lemma 3.1. A set Ais anti-complex if and only if for every f 6wttA, C(f(n))6+n.
This lemma shows that the notion of anti-complexity (like its analogue notion, complexity) is wtt-degree invariant.
Proof. We first note thatA is anti-complex if and only if for every order function f, C(A f(n)) 6+ n. One direction is immediate from Definition 1.2. For the other direction, suppose that for every order functionf,C(Af(n))6+n. Letf be an order function. Applying the hypothesis twice to the functions n 7→f(2n) andn7→f(2n+ 1), there is a constantc such that for alln,C(Af(2n))6n+c
andC(Af(2n+ 1))6n+c. If n>c, then C(Af(2n)) andC(Af(2n+ 1)) are less than or equal to 2n, so Definition1.2holds.
Assume that for everyg6wttA,C(g(n))6+ n. Letf be an order function and let g(n) be a natural number code for A f(n). Then g 6wtt A, so as we just observed,Ais anti-complex.
Now assume thatAis anti-complex. Letf 6wttAand letgbe a recursive bound for the use function for the reduction of f toA. Using this reduction, we see that C(f(n))6+C(Ag(n)). Again, as we just observed,C(Ag(n))6+n.
We show that anti-complexity can also be characterised as a weak truth-table ana- logue of a very useful concept in the Turing degrees, that of r.e. traceability. Recall that anr.e. trace for a functionf is a uniformly recursively enumerable sequence hTniof finite sets such that for all n, f(n)∈Tn, and that a tracehTniisbounded by an order functionhif the functionn7→ |Tn|is bounded byh.
Definition 3.2. A weak truth-table degreea∈ Dwtt isr.e. traceable if there is an order functionhsuch that everyf 6wttahas an r.e. trace which is bounded byh.
The standard argument of Terwijn and Zambella [33] shows that the choice of order doesn’t matter:
Lemma 3.3. A weak truth-table degreea is r.e. traceable if and only if for every order functionh, everyf 6wttahas an r.e. trace which is bounded by h.
Proof. Suppose thathis an order function which witnesses that a weak truth-table degreeais r.e. traceable. Let ˆhbe any other order function and letf 6wtta.
Let g(n) be the least k such that ˆh(k) > h(n). This function is well defined because ˆh is unbounded and is recursive. Hence the map n 7→ f (g(n+ 1)) is weak truth-table belowa, and so it has a tracehTniwhich is bounded byh.
The functiong is unbounded becausehis unbounded. Let g−1 be the discrete inverse ofg, so g−1(k) is the greatest n such that h(n)6 ˆh(k) (note that g−1 is defined on almost every number). Then|Tg−1(k)|6ˆh(k) andg(g−1(k) + 1)> k, so f l is an element ofTg−1(k)for somel > k. Hence we can letSk be the collection of all valuesσ(k) for allσ∈Tg−1(k)of length greater thank. ThenhSniwill be an
r.e. trace forf which is bounded by ˆh.
Proposition 3.4. A setAis anti-complex if and only ifdegwtt(A)is r.e. traceable.
Proof. Suppose that Ais anti-complex and letf 6wtt A. By Lemma 3.1, there is some constantcsuch that for alln,C(f(n))6n+c. Then letting
Tn={y : C(y)6n+c},
hTniis an r.e. trace forf and for alln,|Tn|62n+c+1. Hence (by changing finitely many entries for every function), degwtt(A) is r.e. traceable, witnessed by the order functionh(n) = 22n.
The other direction follows an idea of Kummer’s, who showed that every array recursive r.e. Turing degree contains only sets of low complexity [18] (see also [4]).
Suppose that degwtt(A) is r.e. traceable and let f 6wtt A. By Lemma 3.3, let hTnibe an r.e. trace for f which is bounded by the order function h(n) = n. We can construct a machineM which on inputσ, first computesU(σ), interprets the result as a pair (n, m) and, ifm < n, outputs themth element enumerated intoTn.
Then for alln, iff(n) is themth element enumerated intoTn, then M shows that C(f(n))6+C(n, m).
Now the standard coding of pairs as numbers is polynomial; so there is some constant c such that for alln and all m6n,hn, mi6nc. For allx, the identity machine witnesses thatC(x)6+log2x. Hence for allnand allm6n,
C(n, m)6+log2(hn, mi)6log2nc=clog2n6+n.
Thus we see that the condition of Lemma3.1holds.
Porism 3.5. If A is anti-complex and c > 1 any rational constant, then for all f 6wttAit holds that C(f(n))6+clog2n.
3.2. Tiny use. Given A∈ {0,1}ω, the functionn7→C(An) is far from mono- tone. Nevertheless, we are interested in some form of inverse, which is possible because limnC(An) =∞. We let gA(k) be the leastnsuch that for allm>n, C(Am)> k.
Observation 3.6. For all A ∈ {0,1}ω, gA 6T A⊕K. As before, K =∅0 is the halting problem.
For any stringx, we letx∗be the least element ofU−1{x}(whereU is the universal machine we use for plain complexity), soC(x) =|x∗|. We also let
A∗=n
AgA(k)∗
: k < ωo . Once again, we getA∗6T A⊕K.
Lemma 3.7. For everyA∈ {0,1}ω, the mapk7→(AgA(k))∗is bounded by some recursive function.
Proof. There is a constantcsuch that for allτ∈ {0,1}∗,C(τ0) andC(τ1) are both less than or equal toC(τ) +c(consider the machine which on inputσi, fori= 0,1, outputsU(σ)i).
For anyk < ω, letτk be a binary string andi∈ {0,1}be such thatAga(k) = τki. By the definition of gA(k), C(τk)6k, and so C(A gA(k))6k+c. Hence (AgA(k))∗<2k+c+1.
To ensure the last inequality, we need some agreement about the coding of strings by numbers. This coding is obtained by some ω-ordering of all binary strings; we order binary strings by length first. We let |x| denote the length of the string identified with the numberx, so for allx, 2|x|6x <2|x|+1. Theorem 3.8. The following are equivalent for A∈ {0,1}ω.
(1) There is some setB such thatA6T(tu)B.
(2) A is anti-complex.
(3) gA is dominant.
(4) A6uT(tu)A∗.
We remark that we are not aware of a shorter proof of the equivalence of (2) and (3).
This suggests that the study of the relation 6T(tu) is important for the seemingly independent study of anti-complexity in the wtt-degrees.
Proof. (1) implies (2): Assume that A6T(tu)B. For any functional Φ such that ΦB=A, for alln,C(Φ(Bn))6+C(B n). Also, for allx,C(x)6+|x|, so for all n, C(Φ(Bn))6+ n. Suppose thatf 6wttA, so there is some functional Γ such
that ΓA =f and the use of this computation is bounded by a recursive function g. We can find some Φ such that for all n, Φ(B n) is longer than A g(n), so C(f(n))6+n. By Lemma3.1, Ais anti-complex.
(2) implies (3): Suppose that A is anti-complex and let f be an increasing recursive function. By definition, for almost all n, C(A f(n)) 6n. Hence, for almost alln,gA(n)> f(n). It follows thatgAdominates every recursive function.
(3) implies (4): For everyA∈ {0,1}ω we haveA6T A∗ because A=[
{U(σ) : σ∈A∗}
(in other words, A(x) = U(σ)(x) for any σ ∈ A∗ such that x < |U(σ)|, and for everyxthere is indeed someσ∈A∗such that |U(σ)|> x).
IfgAis dominant, then this reduction witnesses thatA6uT(tu)A∗. To see this, let Φ code the described reduction and let f be an increasing recursive function;
we see thatn7→ |Φ(A∗n)|dominatesf.
Letg be a recursive function which dominates k7→(AgA(k))∗ (Lemma 3.7), and letn be given. Since gA is dominant, for almost all k, gA(k) > f(g(k+ 1)).
Suppose that k is large enough that (AgA(k))∗ < n 6(AgA(k+ 1))∗. Then n6g(k+ 1) and sogA(k)> f(n). Then|Φ(A∗n)|>gA(k) so|Φ(A∗n)|>f(n) as required.
(4) implies (1): This is clear from the definitions.
3.3. Schnorr triviality. Franklin and Stephan [11] characterise the Schnorr trivial sets (defined by Downey and Griffiths in [5]) as those sets whosetruth-table degree isrecursively traceable, that is, there is some order functionhwhich bounds traces for all functionsf truth-table reducible to the degree a, but where the trace hTni is required to be given recursively (as a sequence of finite sets) rather than merely uniformly recursively enumerably. In other words, there is a recursive function g such that for all n, g(n) is the canonical index for the finite set Tn (in Soare’s [32] notation,Tn =Dg(n)). Again, the Terwijn-Zambella argument shows that any order would do.
Schnorr triviality is not invariant in the weak truth-table degrees [11, Theorem 4.2]. However, the downward closure of the wtt-degrees containing Schnorr trivial sets is familiar.
Proposition 3.9. Every Schnorr trivial set is anti-complex.
Proof. LetAbe Schnorr trivial. Fix an order functionh. Let Φ be a weak truth- table functional with a recursive boundgon the use function of Φ. Since the map n 7→ A g(n) is truth-table reducible to A, by the characterisation mentioned above, there is a recursive tracehTnifor this map which is bounded byh. If ΦA is total, then we can enumerate a traceSnforfwith boundhby outputting Φσ(n) for thoseσ∈Tn for which Φσconverges with domain greater thann. Hence degwtt(A) is r.e. traceable; by Proposition3.4,A is anti-complex.
Proposition 3.10. LetA∈ {0,1}ω. IfgA is dominant, thenAis weak truth-table reducible to some Schnorr trivial set.
Proof. Letf0, f1, . . . be a sequence of (total) recursive functions such that
• eachfi is strictly increasing,
• the range offi+1 is contained in the range offi, and
• every recursive function is bounded by somefi.
(Note that the halting problemK can compute such a sequence.)
By Lemma 3.7, let g be a recursive function which bounds the function k 7→
(AgA(k))∗.
For each k > 0, let qk =
(AgA(k))∗, fi(k)
, where i is the greatest number such thathg(k), fi(k)i6gA(k−1). Then for allk >0,qk 6gA(k−1).
LetB={qk : k >0}. We claim thatB is Schnorr trivial and thatA6wttB.
To see the latter, letn < ω. Let k =gA−1(n) (that is, the greatestk such that gA(k)6n). Thenqk+16gA(k)6nand AgA(k+ 1) can be effectively obtained fromqk+1. This procedure allows us to generateAneffectively fromB(n+ 1).
To see that B is Schnorr trivial, we appeal to the characterisation mentioned above. Here is where we use the fact that gA is dominant. The point is that for everyi, all but finitely many elements of B are pairs whose second coordinate is contained in the range of fi. This is because the map k 7→ hg(k), fi(k)i is recursive and thus dominated by gA, so for all but finitely many k we will have qk=
(AgA(k))∗, fi0(k)
for some i0>i, and the range offi0 is contained in the range offi.
Now let Ψ be a truth-table functional; there is somei such thatfi bounds the use function of Ψ. After specifying a fixed initial segment ofB(specifying thoseqk0
whose second coordinate is not in the range offi), there are at most 2kg(k) many possibilities for B fi(k) because, apart from the finitely many fixed elements, there are only kg(k) many numbers below fi(k) which can be elements of B, as they all have the form hp, fi(m)i for some p < g(k) and m < k. After applying Ψ, we get a recursive trace for Ψ(B) whose kth element has size at most 2kg(k). Hence degtt(B) is recursively traceable (in the tt-degrees), so as quoted above, B
is Schnorr trivial.
3.4. Truth-table reductions with tiny use. Another connection between tiny use and Schnorr triviality is obtained by examining truth-table reducibility. Recall thatA6ttB if and only if there is a Turing reduction Φ for which ΦX is total for allX and ΦB =A. We say that A6tt(tu) B if for every order functionhthere is such a functional whose use function is bounded byh. Equivalently, for every order functionh, there is a truth-table reduction ofA toB for which the size of thenth truth table is bounded byh(n). This notion is invariant in the truth-table degrees.
Since the use function for a total Turing functional is recursive (equivalently, the size of thenthtruth-table of a tt-reduction is recursive), there is no uniform notion in this context.
The class of all A such that there is a B with A 6tt(tu) B gives us a new characterisation of the Schnorr trivial sets.
Theorem 3.11. Let A∈ {0,1}ω. There is a setB such that A6tt(tu) B if and only ifA is Schnorr trivial.
Proof. We begin by assuming thatA6tt(tu)B. Lethbe an order function. There is a total reduction Φ such that ΦB =A whose use function is bounded by n7→
log(h(n)). Then a recursive trace forn7→Anwith boundhcan be obtained by applying Φ. Hence degtt(A) is recursively traceable.
Now suppose that A is Schnorr trivial. Again the point is that degtt(A) is recursively traceable, so for any recursive functionf, the function A 7→A f(n) has a recursive trace bounded by the identity function.
Lethfiibe an enumeration of all increasing total recursive functions. For each i < ω, let
Dni
n<ω be a recursive trace for the function A7→Afi(n) such that for alln,|Dni|=n.
We let B be the collection of triples (i, n, m) such that A fi(n) is the mth element ofDin.
Leti < ω. Let Φibe the following truth-table functional: given an oracleX and inputx∈[fi(n−1), fi(n)), find the leastm6nsuch that (i, n, m)∈X; if themth element of Dni is a stringσ of length fi(n), output σ(x). If not, or if there is no m6nsuch that (i, n, m)∈X, output 0. It is clear that for alli < ω, ΦBi =A.
The standard coding of triples of natural numbers by natural numbers grows polynomially. Hence, ifgis, say, an exponentially growing recursive function, then for almost all i, for all n and m 6 n, (i, n, m) < g(n). Hence for almost all i,
|Φi(Bg(n))|>fi(n), whence the functionn7→ |Φi(Bn)|dominatesfi◦g−1. Of course every recursive function is dominated by somefi◦g−1, so A6tt(tu)B.
4. The distribution of anti-complex sets
In this section we investigate how the anti-complex sets are distributed in the Turing degrees and among certain classes of sets. Three question are natural:
• Which Turing degrees contain anti-complex sets?
• Which Turing degrees contain only anti-complex sets?
• What kind of sets can be anti-complex?
The answer to the second question was mentioned in the introduction:
Proposition 4.1. A Turing degree a contains only anti-complex sets if and only if ais r.e. traceable.
Proof. A Turing degreeais r.e. traceable if and only if for every order functionh, every f ∈a has an r.e. trace bounded by h. Since a Turing degreea is the union of the weak truth-table degrees contained ina, by Lemma3.3, a Turing degreeais r.e. traceable if and only if every weak truth-table contained ina is r.e. traceable.
The result now follows from Theorem1.3.
Theorem1.4now follows from Theorem1.3.
The rest of this section will be dedicated to answering the other two questions.
We will see that every high degree contains an anti-complex set, which leads us to a discussion of which types of randomness are compatible with anti-complexity. Then, after we show that there is an r.e. Turing degree that contains no anti-complex sets, we study the properties of r.e. andω-r.e. sets that are anti-complex.
4.1. High and random anti-complex sets. Franklin [10] shows that every high degree contains a Schnorr trivial set. It follows from Proposition 3.9 that every high degree contains an anti-complex set. We improve this result in Corollary5.5.
Nies [24] constructed a ∆02perfect tree, all of whose branches are jump-traceable and thus have r.e. traceable Turing degree. Every perfect ∆02 tree contains a high path, and so there is a high r.e. traceable Turing degree. It follows from Proposition 4.1 that there is a high Turing degree that has only anti-complex elements. Note that such a high degree cannot be ∆02, as every r.e. traceable Turing degree is GL2. Now every high degree contains Schnorr random and recursively random sets [26].
Hence there is a recursively random, anti-complex set. On the other hand, sufficient
randomness precludes anti-complexity: Kuˇcera [17] has shown that every Martin- L¨of random set weak truth-table computes a diagonally nonrecursive function, so every Martin-L¨of random set is complex and thus certainly not anti-complex. This result can be strengthened to show that partial-recursively random sets are not anti-complex.
Now we are ready to prove Theorem 1.6 and we repeat the statement of the theorem for the reader’s convenience.
Theorem 1.6. There is a high Turing degree which does not contain a partial- recursively random set.
Proof. LetAbe an anti-complex set. By Porism3.5, there is some constantc < ω such thatC(An)6+clog2n; so for almost alln,C(An)6(c+1) log2n. Hence Theorem 7 of [22] shows that no Mises-Wald-Church stochastic set is anti-complex.
Every partial-recursively random set is Mises-Wald-Church stochastic (see Section 7.4 of [3]), and so no partial-recursively random set is anti-complex. As we just discussed, there is a high Turing degree all of whose elements are anti-complex, and so such a degree cannot contain a partial-recursively random set.
4.2. Anti-complex-free Turing degrees. As outlined in Subsection5.3below, there are many natural examples of Turing degrees which do not contains anti- complex sets; however, these are not r.e. Turing degrees. In the following, we prove that there is also an r.e. degree not containing anti-complex sets (which does not follow directly from known results). Note that this r.e. Turing degree cannot be very low, as all array recursive (and hence superlow) r.e. degrees are r.e. traceable.
This result extends the result of Downey, Griffiths and LaForte [6] that there is an r.e. degree that contains no Schnorr trivial sets and utilizes their techniques.
These techniques involve prefix-free complexity. Recall that a machine M is prefix-free if its domain is an antichain of {0,1}∗, that is, for all distinct σ, τ ∈ domM, σ is not an initial segment of τ. There is a prefix-free machine, optimal among all prefix-free machines, and soprefix-free Kolmogorov complexity, which is often denoted byK, but which we denote byH (to differentiate from the halting setK=∅0), equalsCV for some optimal prefix-free machineV.
Lemma 4.2. If A ∈ {0,1}ω is anti-complex, then for every order function f, H(Af(n))6+n.
Proof. We follow the proof of Proposition3.4. IfAis anti-complex andf is an order function, then since degwtt(A) is r.e. traceable, there is an r.e. tracehTni, bounded by the identity function, for the functionn7→Af(n). The same argument in the proof of Proposition3.4shows that for allnthere is somem6nsuch that
H(Af(n))6+H(m, n).
It is no longer true thatH(x)6+log2x, but even a crude bound such asH(n)6+ 2 log2nwould do to show that for some constantcwe haveH(m, n)6+clog2n6+
nas required.
Theorem 4.3. There is an r.e. Turing degree that contains no anti-complex sets.
Proof. For any prefix-free subsetD of{0,1}∗, we let µ(D) =X
τ∈D
2−|τ|
be the measure of the subset of the Cantor space defined byDby taking all infinite extensions of elements ofD.
Theorem 9 of [6] states that there is an r.e. setAsuch that for allB≡T Athere is a prefix-free machine M such that µ(dom(M)) is a recursive real and such that for infinitely manym,H(Bm)>CM(m).
The r.e. degree we seek is the Turing degree ofA. Let B ≡T A; we show that B is not anti-complex. Let M be a machine for B as described in the previous paragraph.
We first note that dom(M) is a recursive subset of {0,1}∗: If hMsi is a some recursive enumeration of M, then dom(M) {0,1}6n = dom(Ms) {0,1}6n for any stagessuch thatµ(dom(M))−µ(dom(Ms))<2−n; such a stagescan be found effectively fromn. Now the range ofM may not be recursive, butCM range(M) is a partial recursive function.
We can compute a strictly increasing recursive functionf such that for alln, X
m>f(n) m∈rangeM
2−CM(m)62−3n
by finding some s(n) such that µ(dom(M))−µ(dom(Ms(n))) 62−3n and letting f(n) be greater than any number in the range ofMs(n). Let
L=
(CM(m)−2f−1(m), m) : m∈rangeM .
The set L is recursively enumerable. Recall that for any set D ⊆ ω2, the weight wt(D) ofD isP
(n,m)∈D2−n. We have wt(L) = X
m∈rangeM
22f−1(m)−CM(m)=X
n
22n X
m∈rangeM m∈[f(n),f(n+1))
2−CM(m)6
X
n
22n X
m∈rangeM m>f(n)
2−CM(m)6X
n
22n2−3n=X
n
2−n<∞.
The Kraft-Chaitin Theorem (see [3,19,23]) now ensures that for allm, H(m)6+CM(m)−2f−1(m)
(recall that form /∈rangeM, we letCM(m) =∞).
Suppose that B is anti-complex. Then by Lemma 4.2, H(B f(n)) 6+ n.
Let m < ω and let n = f−1(m). We can uniformly compute B m if we are given bothm andBf(n+ 1). SinceH measures prefix-free complexity, we have H(B m)6+ H(m) +H(B f(n+ 1)) (a description for B m is a description formconcatenated with a description forB f(n+ 1)). Overall we get, for allm,
H(Bm)6+H(m) +f−1(m)6+CM(m)−f−1(m).
Since f is increasing, f−1 is unbounded, which would make it impossible to have infinitely manym∈rangeM such that H(Bm)>CM(m). Hence B cannot be
anti-complex.
4.3. Anti-complex r.e. andω-r.e. sets. The results so far show that ifAis anti- complex, then there is some set B 6T A⊕K such that A6uT(tu) B. In general, as we will see shortly, one cannot improve this toB6wttA⊕K. However, if Ais r.e., then we get an improved bound as follows.
Proposition 4.4. If Ais an anti-complex r.e. set, then A <uT(tu)K.
Proof. We claim that ifA is r.e., thenA∗ 6wttK; the rest follows from Theorem 3.8. Fix a recursive enumeration hAsi ofA and let, at stage s, gs(k) be the least numbernsuch that no initial segment ofAsof length at leastnhas aU-description of length at mostk. Thengsconverges togAand is anω-r.e. approximation ofgA. We can havegs+1(k)6=gs(k) only in three cases:
• there is someσ∈domUs+1\domUsof length at mostkandU(σ)⊂As+1;
• there is some σ ∈ domUs of length at most k such that U(σ) 6⊂ As but U(σ)⊂As+1; or
• there is some σ ∈ domUs of length at most k such that U(σ) ⊂ As but U(σ)6⊂As+1.
For each σ, each case can happen at most once, and the first two cannot both happen at different stages. Hence our approximation for gs(k) changes at most 2·2k+1 many times.
Hence gA 6wtt K, and it is straightforward to see that A∗ 6wtt gA⊕K⊕A for any setAbecause once we knowgA(k), we only need to query Kabout strings belowg(k) (whereg(k)>(AgA(k))∗is recursive) to find (AgA(k))∗ and hence
A∗.
Theorem 1.5 now follows from Proposition 4.4 and the techniques of Downey, Jockusch and Stob [7, 8] and Ishmukhametov [14]. The fact that the array re- cursive r.e. wtt-degrees form an ideal now follows from Observation2.5.
One would perhaps hope that the previous result could be extended to classes wider than the class of r.e. sets and their weak truth-table degrees. Of course, if A <T(tu)K, thenA6wtt K and soA is ω-r.e.; however, we now show that there areω-r.e. setsAwhich are anti-complex and yetA66T(tu)K. This shows that the condition B 6T A⊕K for the bound for A with tiny use cannot in general be improved toB 6wttA⊕K.
We first need a lemma which again is not new, but which is not found in standard references (an approximation, insufficient for our purposes, is Theorem 9.14.6 in [3]).
Let Ω be the halting probability.
Lemma 4.5. For any r.e. setA, there is a reduction of A toΩwith use bounded below 2 logn.
Indeed, we can even get a bound ofh(n) where his such thatP
n2−h(n)is finite, such as logn+ 2 log logn.
Proof. Let hΩsibe an effective, increasing approximation of Ω and, similarly, let hAsi be an effective enumeration of A. Let h be a recursive function such that P
n2−h(n) is finite.
Ifnis the smallest number which entersAat stages, we enumerate the interval [Ωs,Ωs+2−h(n)] into a Solovay testGwhich we enumerate. SincenentersAat most once, the total measure ofGis at mostP
n2−h(n), which is finite by assumption.
Ω is random, so it belongs to only finitely many of the intervals inG. To compute A(n) from Ω h(n), find a stage t at which Ωt h(n) = Ω h(n); we claim that A(n) = At(n). If n enters A at a later stage s, then [Ωs,Ωs+ 2−h(n)] is in G, but Ω−Ωt 62−h(n) and Ωt 6Ωs 6Ω, so we conclude that Ω is in the interval [Ωs,Ωs+ 2−h(n)]. Thus we can get a wrong answer for only finitely many numbers n, and we can find a reduction as required.
Proposition 4.6. There is an anti-complex ω-r.e. set which is not reducible toK with tiny use.
Indeed, as the proof shows, there is such a set which is also the difference of two left-r.e. reals. (We cannot get a left-r.e. real, because every left-r.e. real is weak truth-table equivalent to an r.e. set.)
Proof. By [11, Theorem 4.1], there is a coinfinite r.e. setAsuch that every superset of A is Schnorr trivial (indeed, any dense simple set would do). LetB =A∪Ω.
B is Schnorr trivial and thus anti-complex. B is alsoω-r.e., since it is a Boolean combination of two sets which are wtt-reducible toK.
Now assume for a contradiction thatB6T(tu)K. Then there is some reduction ΓΩ=B such that for all n,|Γ(Ωn)|> nbecause Ω has the same wtt-degree as K. By Lemma4.5, there is a reduction ∆Ω=A with the same property, as there is a reduction fromAto Ω with use below 2 logn.
We use the functionals Γ and ∆ to define a partial recursive martingale which will succeed on Ω, contradicting the fact that Ω is random. The martingale d is defined by induction on the length of the binary strings which form its domain. We start with the value 1. If d(σ) is defined, we first calculate ∆(σ)(n) and Γ(σ)(n), where n = |σ| (if either |Γ(σ)| 6 n or |∆(σ)| 6 n, then we know that σ cannot be an initial segment of Ω, so we can stop all betting). If ∆(σ)(n) = 1, then we hedge our bets, that is, we let d(σ0) =d(σ1) =d(σ). Otherwise, we put all of the capital we have on the outcome Γ(σ)(n), because in this case, ifσ = Ω n, then A(n) = 0 and so B(n) = Ω(n). Thus we let d(σi) = 2d(σ) and d(σ(1−i)) = 0, wherei= Γ(σ)(n).
SinceAis coinfinite, there are infinitely many nat which we double our money betting along Ω, so limnd(Ωn) =∞as required for the contradiction.
5. Sets bounding nonrecursive sets with tiny use
We now turn to investigate the ranges of the relations6T(tu)and6uT(tu)(where the domain is restricted to the class of nonrecursive sets to avoid triviality). Unlike their domains, these ranges are not equal, because as we observed earlier, ifA6uT(tu)B and A is nonrecursive, then B is high, whereas we will shortly see that there are nonhigh sets which bound nonrecursive sets with tiny use. First, we prove some results on the range of6uT(tu).
5.1. High degrees. Unlike for Turing reducibility, with weak truth-table reducibil- ity we have to be careful when we deal with functions (elements of the Baire space ωω) and sets (elements of the Cantor space{0,1}ω). For example, a function is al- ways Turing equivalent to its graph, but if it is not bounded by a recursive function, it may not be wtt-equivalent to its graph. Our primary interest is to investigate 6T(tu)onsets, and so far we have not treated functions as oracles in computations with recursive or tiny use. However, as a technical tool, we can extend the defi- nitions of6T(tu) and 6uT(tu) to include functions as oracles in the standard way;
weak truth table invariance still holds. In this context we have the following result.
Observation 5.1. Let G(f) be the graph of f. If f is a dominant function, then G(f)6uT(tu)f.
This allows us to characterise the range of6uT(tu).
Lemma 5.2. Let B ∈ {0,1}ω. There is some nonrecursive set A such that A <uT(tu)B if and only if there is some dominant function f 6wttB.
Proof. In the proof of Proposition2.10we noticed that if there is some nonrecur- sive set A such that A 6uT(tu) B witnessed by some reduction Φ, then the map n7→ |Φ(B n)| is dominant and is weak truth-table reducible toB. In the other direction, suppose thatf is dominant and thatf 6wttB. LetAbe the graph off. ThenA 6uT(tu)f; together with f 6wtt B we get A6uT(tu)B from Observation
2.4.
We know that every high Turing degree contains a dominating function, but the weak truth-table degree of that function may not contain any set. This lets us see that there is a high set that is not in the range of6uT(tu).
Lemma 5.3. Let f be a function such that n 7→ C(f(n)) is bounded by some recursive function. Then f is wtt-equivalent to some set.
Proof. Let g be a recursive function which bounds C(f(n)). Let A be the set of pairs (n, u) where uis the first number belowg(n) which is discovered in some effective enumeration of the universal machineU to be mapped byU tof(n). Then
A≡wttf.
Proposition 5.4. Every high Turing degree contains a dominant function fˆsuch that C( ˆf(n))6+n.
Proof. Let g be a dominant function; we first find an f 6T g with the desired properties.
Once again, lethΩsibe an effective increasing approximation of Ω. Definef by lettingf(n) be the leasts6g(n) such that Ωsn= Ωg(n)n. It is certainly true thatf 6T g.
First we show that C(f(n))6+ n. Let M be a machine that on an inputσ of lengthnoutputs the least stagessuch thatσ= Ωsnif such a stage exists. Then for alln,M(Ωg(n)n) =f(n), soCM(f(n))6nas required.
Next, let hbe an order function. We first note that H(Ωh(n) n)6H(n) (as before,H denotes prefix-free Kolmogorov complexity), and since Ω is random, for almost alln, Ωh(n) n6= Ωn, as H(Ω n)>+ n. Thus we can let ˆh(n) be the leasts > h(n) such that Ωsn6= Ωh(n)n; this too is a recursive function, defined on almost every input.
Since g is dominant, for almost all n, g(n) >ˆh(n), which implies that Ωg(n) n6= Ωh(n)nsince the approximation Ωsndoes not return to old values, and so f(n)>h(n)ˆ > h(n) for almost alln. Thusf is dominant.
Next, we code a set A in the Turing degree of g into f to get a function which is Turing equivalent to g. We let ˆf(n) = 2f(n) +A(n). Then A 6T fˆ and fˆ6T f ⊕A6T g, so ˆf ≡T g. Since ˆf bounds f, ˆf is dominant, andC( ˆf(n))6+
C(f(n))6+n.
Corollary 5.5. Every high Turing degree contains sets A and B such that A
<uT(tu)B.
Proof. Leta be a high Turing degree. By Proposition5.4and Lemma5.3, there is some dominant f ∈a which is wtt-equivalent to some set B, so of course B ∈a.
By Lemma5.2, there is some setAsuch thatA6uT(tu)B. Indeed, we can takeA to be the graph off. A is thus Turing equivalent tof, so A∈a.
We can improve on the corollary in case, for example, the high degree is also generalised low.
Theorem 5.6. Ifais a Turing degree such thata∨00>T 000, then for everyB ∈a there is someA∈a such thatA <uT(tu)B.
The point is that under the assumption that everyB∈ais wtt-equivalent to some dominant functionf, we can letAbe the graph off. This means that we can prove the following equivalent fact instead.
Proposition 5.7. Ifais a Turing degree such thata∨00>T 000, then everyB ∈a is wtt-equivalent to some dominating function.
Proof. LetB∈a, and lethϕeibe an enumeration of all partial recursive functions.
Then Tot, the collection of all indicesesuch thatϕeis total, has Turing degree000, so there is some Turing reduction ΦB⊕K= Tot.
We show that there is a set E⊆Tot which is recursively enumerable inB and such that for every (total) recursive function g there is some e ∈ E such that g=ϕe. The setEis enumerated as follows: at stages, if ΦB⊕Ks(e)↓= 1, then we enumerate g(e, σ) intoE with use B u, where uis the use of the computation, σ=Ksuand the instructions for calculatingϕg(e,σ) are as follows. We emulate ϕeas long asσis an initial segment ofKtfor stagest>s, waiting for computations to converge, but if at some stage we observe thatσis no longer an initial segment of K, we makeϕg(e,σ)total by immediately converging on all inputs for which we have not yet given an output and giving the answer 0. The functiong is thus recursive.
NowE is used to construct a dominant functionf 6wtt B: we letf(n) be the maximum of the valuesϕe(n) for theethat are enumerated intoE by stagenwith B-use at mostn.
Again, we can modifyf to be a dominant function ˆf ≡wttB by codingB into
fˆ, say again by letting ˆf(n) = 2f(n) +B(n).
We do not know much in general about the range of6T(tu). We give some partial results in the following subsections. First, we show that every nonrecursive r.e. set is in the range of 6T(tu). Then we consider the hyperimmune-free case and show that there is a hyperimmune-free set in the range of 6T(tu), even though not all hyperimmune-free sets are.
5.2. Recursively enumerable degrees. The techniques of the previous subsec- tion can be improved to yield the following result.
Theorem 5.8. For every nonrecursive r.e. setB there is a nonrecursive r.e. set A such thatA <T(tu)B.
In order to prove this theorem, we take dominant functions which have decent approximations. Let hbe a high r.e. Turing degree. By standard manipulations, we can get a dominant functionf 6T hwith an approximation with the following
“nice” properties.
• The approximation is increasing: for allnands,fs(n)>fs−1(n).
• Iffs(n)6=fs−1(n), thenfs(n) =s.
• For allsthere is at most onensuch thatfs(n) =s(this is done by delaying changes in the approximation).
We now procede to the proof of the theorem.
Proof of Theorem 5.8. Let B be a nonrecursive r.e. set. By a standard cone- avoiding addition to the Sacks jump inversion theorem, there is a high r.e. de- gree hwhich does not compute B. Let f 6T hbe a dominant function with an approximationhfsias described above.
Enumerate a setA as follows: for alln∈B, ifnentersB at stages, enumerate fs(n) into A.
Suppose that we want to compute A from B. To find out ift ∈A, we first go to stage t and see if ft(n) =t for some n6t — if not, thent is certainly not in A. If so, thentis inAif and only if for the uniquen=n(t) such thatft(n) =t,n entersB at a later stage sbeforefs(n) changes. This gives a reduction ofAto B with identity use.
In fact,A6T(tu)B. The idea is the following. Suppose again that we want to find out whethertis inAand that we find thatft(n) =t. If we knew thatf(n)> t, in other words, that there is a later stage sat which we havefs(n)6=ft(n), then we could wait for that stage and see if n enteredB before that stage or not. Of course, we cannot always do this, because it may happen thatt=ft(n) =f(n) (or elseAwould be recursive, whereas later we show it is not). But now suppose that his an order function and that we want to reduceAto B with use bounded byh.
Then if n=n(t)< h(t), then we can consult B(n) as before to computeA(t). If h(t)6n, thenh−1(n)>t; sincef is dominant, f(n)> texcept for finitely many n, so we can employ the second tactic of waiting for fs(n) to change in order to computeA(t). In the second case we do not consult B at all, so overall we get a reduction with use bounded byh.
Finally, to show thatAis not recursive, we see thatB6T A⊕f and recall that B 66T f. To findB(n), we calculate the least stage t at which ft(n) = f(n); if
n /∈Bt, thenn∈B if and only if t∈A.
Just as we did for6tt, we can apply the “tiny use” operator to many-one reducibility and say thatA6m(tu)Bif for every order functionhthere is a recursive functionf dominated byhsuch thatA=f−1B. The previous proof can be slightly modified to show that for every nonrecursive r.e. set B, there are an r.e. set ˆB which is wtt-equivalent toBand a nonrecursive r.e. setAsuch thatA6m(tu)B. We simplyˆ enumerate (n, m) into ˆB ifnis enumerated intoB at stagesandfs(n) is themth value we see forft(n) by stages, that is,m=|{ft(n) : t6s}|. Then, givent, we can findnandm; thent∈Aif and only if (n, m)∈Bˆand, as described above, this can be done with tiny use. To get B ≡wtt Bˆ rather than just Turing equivalence, we use a function f which is ω-r.e., the existence of which is guaranteed by the proof of Proposition5.4.
Theorem 5.8 cannot be extended to all ∆02 sets, as Downey, Ng and Solomon [9]
constructed a ∆02set which has minimal wtt-degree.
Finally, there is an r.e. set B which has minimal tt-degree [20]. For such B, there can be no nonrecursive A6tt(tu)B. Thus we cannot improve6T(tu) in the theorem to 6tt(tu), or, in the comments after the proof, get ˆB ≡tt B rather than Bˆ≡wttB.
5.3. Hyperimmune-freeness. Note that most hyperimmune-free Turing degrees do not contain any setBfor which there is a nonrecursiveAsuch thatA <T(tu)B.
For example, a Turing degree which is both minimal and hyperimmune-free does not contain such sets because if degT(X) is hyperimmune-free and minimal, then degwtt(X) is also minimal, as every nonrecursiveY 6wttX is Turing equivalent to X and thus also wtt-equivalent to X. Similarly, if X is Martin-L¨of random and degT(X) is hyperimmune-free, then every nonrecursive Y 6wtt X is truth-table equivalent to a Martin-L¨of random set and so cannot be anti-complex, so again we get that everyA6T(tu)X is recursive.
Thus in the realm of the hyperimmune-free degrees, generic sets (in the sense of either recursive Sacks forcing or forcing with sets of positive measure) do not compute nonrecursive sets with tiny use.
On the other hand, there is a hyperimmune-freeBwith a nonrecursiveA <T(tu) B. This follows from the hyperimmune-free basis theorem and the following theo- rem.
For putting the next result into its context, we remark that it is already known that there is a Π01-class with no recursive elements which consists of anti-complex sets; for example, there is one which consists of Schnorr trivial sets [11] and one which consists of setsAsuch that degT(A) is r.e. traceable.
Theorem 5.9. There is aΠ01-class with no recursive elements consisting of setsB for which there are nonrecursive setsA such thatA <m(tu)B.
Proof. We imitate part of the the proof of Theorem5.8. Again, lethfsibe anω-r.e.
approximation for a dominant functionf with the properties discussed above; sayg is a recursive function which bounds the number of possible valuesm(n) =|{fs(n) : s < ω}|.
Forn < ωandk6m(n), letπ(n, k) be thekthvalue offs(n). Thusπ(n, m(n)) = f(n). Now let D = {(n, k) : k < m(n)} and E = π[D]; both are r.e. sets.
Furthermore, E is nonrecursive as f 6T D 6T E: for each n, we find π(n, k) recursively inkand so, consultingE, determine ifk < m(n) or not.
We can thus splitE into a pair E0 andE1 of recursively inseparable r.e. sets.
Let P be a Π01-class of sets which separateD0 =π−1E0 from D1 =π−1E1 (sets that contain D0 and are disjoint from D1). Let B be any element of P and let A = π[B]. Then A separates E0 and E1, so A is not recursive. We claim that A6T(tu)B, indeed thatA6m(tu)B.
The argument is similar to that of the proof of Theorem5.8. For anyt, ift∈A thent=π(n, k) for some nand somek6m(n). The pair (n, k) is unique and we can effectively decide if such a pair exists, and if so, find it. Suppose such a pair (n, k) is found. We havet∈Aif and only if (n, k)∈B.
Leth be an order function. For all but finitely manyt, either (n, k) < h(t) or t6h−1(n, k)6h−1(n, g(n))< f(n), whencek < m(n). As before, in the first case we consult B about (n, k). In the latter case, (n, k) ∈ D, so we do not need to consultB. For recall thatB is a separator ofD0andD1, and thatD0andD1form a partition ofD; and that bothD0 andD1 are r.e., so which one of them contains
(n, k) is revealed to us with sufficient patience.
References
[1] Adam R. Day. Process and truth-table characterizations of randomness. Theoretical Com- puter Science, to appear.
