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 being6^{LR}, 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 as6^{C} and6^{H}. 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 writeA6^{T}^{(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 complexity^{1}). 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 6^{wtt} 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 for6^{T(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) deg_{wtt}(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¯ =hF_{n}i_{n<ω} 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 6^{uT}^{(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 ∆^{0}_{2}degrees. 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 thatA6^{tt}B 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 writeA6^{uT}^{(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^{−1}is total; otherwisef^{−1}is 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, thendeg_{wtt}(A)<deg_{wtt}(B).

As a result, if deg_{wtt}(B) is minimal, then everyA6T(tu)B is recursive.

Proposition 2.10. Let B ∈ {0,1}^{ω}. If there is some nonrecursive A such that
A6^{uT}^{(tu)}B, thenB is high.

Recall that a setB is high ifB^{0} >^{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 everyg6^{wtt}A,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 6^{wtt}ahas 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 6^{wtt}ahas 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 6^{wtt}a.

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|T_{g}−1(k)|6ˆh(k) andg(g^{−1}(k) + 1)> k, so
f l is an element ofT_{g}−1(k)for somel > k. Hence we can letSk be the collection
of all valuesσ(k) for allσ∈T_{g}−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 ifdeg_{wtt}(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

T_{n}={y : C(y)6n+c},

hTniis an r.e. trace forf and for alln,|Tn|62^{n+c+1}. Hence (by changing finitely
many entries for every function), deg_{wtt}(A) is r.e. traceable, witnessed by the order
functionh(n) = 2^{2n}.

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 deg_{wtt}(A) is r.e. traceable and let f 6^{wtt} 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 them^{th} element enumerated intoT_{n}.

Then for alln, iff(n) is them^{th} 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, mi6n^{c}. For allx, the identity
machine witnesses thatC(x)6^{+}log_{2}x. Hence for allnand allm6n,

C(n, m)6^{+}log_{2}(hn, mi)6log_{2}n^{c}=clog_{2}n6^{+}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 6^{wtt}Ait holds that C(f(n))6^{+}clog_{2}n.

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 lim_{n}C(An) =∞. We let g_{A}(k) be the leastnsuch that for allm>n,
C(Am)> k.

Observation 3.6. For all A ∈ {0,1}^{ω}, g_{A} 6^{T} 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

Ag^{A}(k)^{∗}

: k < ωo
.
Once again, we getA^{∗}6T A⊕K.

Lemma 3.7. For everyA∈ {0,1}^{ω}, the mapk7→(Ag_{A}(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 thatAg_{a}(k) =
τ_{k}i. By the definition of g_{A}(k), C(τ_{k})6k, and so C(A g_{A}(k))6k+c. Hence
(AgA(k))^{∗}<2^{k+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,g_{A}(n)> f(n). It follows thatg_{A}dominates 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,T_{n} =D_{g(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 tracehT_{n}ifor 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 deg_{wtt}(A)
is r.e. traceable; by Proposition3.4,A is anti-complex.

Proposition 3.10. LetA∈ {0,1}^{ω}. Ifg_{A} is dominant, thenAis weak truth-table
reducible to some Schnorr trivial set.

Proof. Letf_{0}, f_{1}, . . . be a sequence of (total) recursive functions such that

• eachfi is strictly increasing,

• the range off_{i+1} is contained in the range off_{i}, and

• every recursive function is bounded by somef_{i}.

(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 q_{k} =

(Ag_{A}(k))^{∗}, f_{i}(k)

, where i is the greatest number
such thathg(k), fi(k)i6g_{A}(k−1). Then for allk >0,q_{k} 6g_{A}(k−1).

LetB={q_{k} : k >0}. We claim thatB is Schnorr trivial and thatA6wttB.

To see the latter, letn < ω. Let k =g_{A}^{−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 g_{A} 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 f_{i}. This is because the map k 7→ hg(k), f_{i}(k)i is
recursive and thus dominated by g_{A}, so for all but finitely many k we will have
qk=

(AgA(k))^{∗}, fi^{0}(k)

for some i^{0}>i, and the range offi^{0} 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 thoseqk^{0}

whose second coordinate is not in the range off_{i}), there are at most 2^{kg(k)} many
possibilities for B f_{i}(k) because, apart from the finitely many fixed elements,
there are only kg(k) many numbers below f_{i}(k) which can be elements of B, as
they all have the form hp, f_{i}(m)i for some p < g(k) and m < k. After applying
Ψ, we get a recursive trace for Ψ(B) whose k^{th} element has size at most 2^{kg(k)}.
Hence deg_{tt}(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
thatA6^{tt}B 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 then^{th}
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 then^{th}truth-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 deg_{tt}(A) is recursively traceable.

Now suppose that A is Schnorr trivial. Again the point is that deg_{tt}(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

D_{n}^{i}

n<ω be a recursive trace for the function A7→Afi(n) such that
for alln,|D_{n}^{i}|=n.

We let B be the collection of triples (i, n, m) such that A fi(n) is the m^{th}
element ofD^{i}_{n}.

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 them^{th}
element of D_{n}^{i} 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 < ω, Φ^{B}_{i} =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 somef_{i}◦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 ∆^{0}_{2}perfect tree, all of whose branches are jump-traceable
and thus have r.e. traceable Turing degree. Every perfect ∆^{0}_{2} 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 ∆^{0}_{2}, 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^{+}clog_{2}n; so for almost alln,C(An)6(c+1) log_{2}n. 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}), equalsC_{V} 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 deg_{wtt}(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^{+}log_{2}x, but even a crude bound such asH(n)6^{+}
2 log_{2}nwould do to show that for some constantcwe haveH(m, n)6^{+}clog_{2}n6^{+}

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)>C_{M}(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}^{6}^{n} = dom(Ms) {0,1}^{6}^{n} 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^{−C}^{M}^{(m)}62^{−3n}

by finding some s(n) such that µ(dom(M))−µ(dom(M_{s(n)})) 62^{−3n} and letting
f(n) be greater than any number in the range ofM_{s(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

2^{2f}^{−1}^{(m)−C}^{M}^{(m)}=X

n

2^{2n} X

m∈rangeM m∈[f(n),f(n+1))

2^{−C}^{M}^{(m)}6

X

n

2^{2n} X

m∈rangeM m>f(n)

2^{−C}^{M}^{(m)}6X

n

2^{2n}2^{−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^{+}C_{M}(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 6^{T} A⊕K such that A6^{uT}^{(tu)} B. In general,
as we will see shortly, one cannot improve this toB6^{wtt}A⊕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^{∗} 6^{wtt}K; 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 ofA_{s}of length at leastnhas aU-description
of length at mostk. Theng_{s}converges tog_{A}and is anω-r.e. approximation ofg_{A}.
We can haveg_{s+1}(k)6=g_{s}(k) only in three cases:

• there is someσ∈domU_{s+1}\domU_{s}of length at mostkandU(σ)⊂A_{s+1};

• there is some σ ∈ domU_{s} of length at most k such that U(σ) 6⊂ A_{s} but
U(σ)⊂A_{s+1}; or

• there is some σ ∈ domU_{s} of length at most k such that U(σ) ⊂ A_{s} 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·2^{k+1} many times.

Hence gA 6^{wtt} K, and it is straightforward to see that A^{∗} 6^{wtt} 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, thenA6^{wtt} K and soA is ω-r.e.; however, we now show that there
areω-r.e. setsAwhich are anti-complex and yetA66^{T(tu)}K. This shows that the
condition B 6^{T} 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 thatB6^{T(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 6^{wtt}B.

Proof. In the proof of Proposition2.10we noticed that if there is some nonrecur-
sive set A such that A 6^{uT}^{(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 6^{wtt}B. 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Ω_{s}ibe an effective increasing approximation of Ω. Definef by
lettingf(n) be the leasts6g(n) such that Ω_{s}n= Ω_{g(n)}n. It is certainly true
thatf 6^{T} 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ˆ6^{T} f ⊕A6^{T} 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 thatA6^{uT}^{(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∨0^{0}>^{T} 0^{00}, 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∨0^{0}>^{T} 0^{00}, then everyB ∈a
is wtt-equivalent to some dominating function.

Proof. LetB∈a, and lethϕ_{e}ibe an enumeration of all partial recursive functions.

Then Tot, the collection of all indicesesuch thatϕeis total, has Turing degree0^{00},
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⊕K}^{s}(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 ≡_{wtt}B 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,f_{s}(n)>f_{s−1}(n).

• Iff_{s}(n)6=f_{s−1}(n), thenf_{s}(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
f_{s}(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 f_{s}(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 thatB6^{T} A⊕f and recall that
B 66^{T} 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 for6^{tt}, 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^{−1}B. 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 them^{th}
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 ∆^{0}_{2} sets, as Downey, Ng and Solomon [9]

constructed a ∆^{0}_{2}set 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 A6^{tt(tu)}B. Thus we cannot improve6^{T}^{(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 deg_{T}(X) is hyperimmune-free and minimal, then
deg_{wtt}(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
deg_{T}(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 Π^{0}_{1}-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 deg_{T}(A) is r.e. traceable.

Theorem 5.9. There is aΠ^{0}_{1}-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 thek^{th}value off_{s}(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 Π^{0}_{1}-class of sets which separateD0 =π^{−1}E0 from D1 =π^{−1}E1 (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 ofD_{0}andD_{1}, and thatD_{0}andD_{1}form
a partition ofD; and that bothD_{0} andD_{1} 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.