Turing degrees and Muchnik degrees of recursively bounded DNR functions^{∗}

Stephen G. Simpson Department of Mathematics Vanderbilt University Nashville, TN 37240, USA http://www.math.psu.edu/simpson sgslogic@gmail.com

First draft: January 7, 2015 This draft: August 24, 2016

To be published in a Festschrift in honor of Rod Downey’s 60th birthday.

Contents

1 Introduction  1
2 When ∑_{i} p(i)^{−1} < ∞  2
3 When ∑_{i} p(i)^{−1} = ∞  3
4 Linear universality  5
5 Some Muchnik degrees in E_{w}  7
References  8

1 Introduction

Let φ_{i}, i ∈ ℕ be a standard enumeration of the 1-place partial recursive functions φ : ⊆ ℕ → ℕ. A function Y : ℕ → ℕ is said to be diagonally nonrecursive (with respect to the given enumeration), abbreviated DNR, if ∀i (Y (i) ≠ φ_{i}(i)). Such a Y is said to be recursively bounded if there exists a recursive function p : ℕ → ℕ such that ∀i (Y (i) < p(i)). In this situation it is known that the growth rate of p has a strong influence on the Turing degree of Y. For example, it follows from [1] (see also [15, §10]) that the Turing degrees of elementaryrecursively bounded DNR functions form a proper subclass of the Turing degrees of primitive-recursively bounded DNR functions. Additional results in this vein may be found in [11, Chapter 3], and still other results may be obtained by translating theorems about partial randomness [8, 9] into the context of recursively bounded DNR functions [12, 13].

∗This research was partially supported by Simons Foundation Collaboration Grant 276282.

In this note we exposit two striking results along these lines due to Joseph S. Miller. Roughly speaking, the results are as follows. Let p : ℕ → ℕ be a nondecreasing recursive function such that p(0) ≥ 2.

1. If ∑_{i} p(i)^{−1} < ∞, then every Martin-Löf random real computes a pbounded DNR function.

2. If ∑_{i} p(i)^{−1} = ∞, then no Martin-Löf random real computes a p-bounded DNR function unless it is Turing complete.

Note that 2 may be viewed as a vast generalization of a theorem of Stephan [20]. Combining results 1 and 2, we see that ∑_{i} p(i)^{−1} < ∞ if and only if the Turing upward closure of the set of p-bounded DNR functions is of full measure.

In order to formulate results 1 and 2 precisely, we find it convenient to replace the class DNR by the closely related class LDNR of linearly DNR functions. As a by-product of this move, we use LDNR to identify some specific, natural Muchnik degrees in E_{w} which are associated with 1 and 2.

In our exposition of Miller’s results, we draw heavily on the ideas of Bienvenu and Porter [3]. Of course [3] contains many other interesting results concerning other topics such as shift-complexity. Our intention here is to break down the proofs of Miller’s results into easily manageable components.

2 When ∑_{i} p(i)^{−1} < ∞

Let ℕ = {0, 1, 2, , …} = the natural numbers. Let MLR = {X ∈ {0, 1}^{ℕ} | X is Martin-Löf random}. The following theorem is a slight generalization of [3, Theorem 7.6(i)]. See also Kurtz’s earlier result in [10, Proposition 3].

Definition 2.1. Given a function p : ℕ → ℕ, we write

∏ p = ∏_{i=0}^{∞}{j | j < p(i)} = {Y ∈ ℕ^{ℕ} | ∀i (Y (i) < p(i))}

denoting the set of p-bounded functions.

Theorem 2.2 (Miller). Let p : ℕ → ℕ be a recursive function such that ∀i (p(i) ≥ 2) and ∑_{i=0}^{∞} p(i)^{−1} < ∞. Let ψ : ⊆ ℕ → ℕ be a partial recursive function. Then (∀X ∈ MLR) (∃Y ≤_{T} X) (Y ∈ ∏ p and Y ∩ ψ = ∅).

Proof. For each i let q(i) be such that 2^{q(i)} ≤ p(i) < 2^{q(i)+1}. Note that q : ℕ → ℕ is recursive and ∀i (q(i) ≥ 1). For all X ∈ {0, 1}^{ℕ} define Ψ^{X} : ℕ → ℕ by Ψ^{X}(i) = ∑_{j<q(i)} X(j)2^{j} < 2^{q(i)}. Let U_{i} = {X | Ψ^{X}(i) = ψ(i)}, and let λ be the fair coin probability measure on {0, 1}^{ℕ}. Clearly U_{i} is uniformly Σ_{1}^{0} and λ(U_{i}) ≤ 2^{−q(i)}, hence ∑_{i} λ(U_{i}) ≤ ∑_{i} 2^{−q(i)} = 2 ∑_{i} 2^{−q(i)−1} < 2 ∑_{i} p(i)^{−1} < ∞. Hence by Solovay’s Lemma [16, Lemma 3.5] we have (∀X ∈ MLR) ∃n (∀i ≥ n) (X ∉ U_{i}), i.e., (∀X ∈ MLR) ∃n (∀i ≥ n) (Ψ^{X}(i) ≠ ψ(i)). Given X ∈ MLR, fix such an n and define Y : ℕ → ℕ by

Y (i) = \{ \begin{matrix}1 & if i < n and ψ(i) = 0, \\ 0 & if i < n and ψ(i) ≠ 0, \\ Ψ^{X}(i) & if i ≥ n. \end{matrix}

Then Y differs at most finitely from Ψ^{X}, hence Y ≤_{T} X, and it is also clear that ∀i (Y (i) < 2^{q(i)} ≤ p(i) and Y (i) ≠ ψ(i)).

Definition 2.3. Let DNR = {Y ∈ ℕ^{ℕ} | ∀i (Y (i) ≠ φ_{i}(i))} where φ_{e}, e ∈ ℕ is some fixed standard enumeration of the 1-place partial recursive functions. Given p : ℕ → ℕ, let DNR_{p} = DNR ∩ ∏ p, and let DNR_{REC} = {Y | Y ∈ DNR_{p} for some recursive function p}.

Corollary 2.4. Let p : ℕ → ℕ be a recursive function such that ∀i (p(i) ≥ 2) and ∑_{i=0}^{∞} p(i)^{−1} < ∞. Then (∀X ∈ MLR) (∃Y ∈ DNR_{p}) (Y ≤_{T} X).

Proof. This is the special case of Theorem 2.2 with ψ(i) ≃ φ_{i}(i).

3 When ∑_{i} p(i)^{−1} = ∞

The following definition and theorem are slight generalizations of [3, Definition 4.1(i), Theorem 5.3].

Definition 3.1.

1. We write ℕ^{∗} = ⋃_{n=0}^{∞} ℕ^{n} denoting the set of finite sequences of natural numbers. We use σ as a variable ranging over ℕ^{∗}. Let [0, 1] denote the unit interval in the real line, and let ℚ denote the set of rational numbers.

2. A continuous semimeasure on ℕ^{∗} is a function M : ℕ^{∗} → [0, 1] such that ∀σ (M(σ) ≥ ∑_{i∈ℕ} M(σ^{⌢}⟨i⟩)).

3. A continuous semimeasure M on ℕ^{∗} is said to be left recursively enumerable, abbreviated left r.e., if there exists a recursive function (s, σ) ↦ M_{s}(σ) : ℕ × ℕ^{∗} → ℚ such that ∀σ (M(σ) = lim_{s} M_{s}(σ) and ∀s (0 ≤ M_{s}(σ) ≤ M_{s+1}(σ))). We may safely assume that ∀s (M_{s} is a continuous semimeasure on ℕ^{∗} and {σ | M_{s}(σ) > 0} is finite).

4. A left r.e. continuous semimeasure M on ℕ^{∗} is said to be universal if for all left r.e. continuous semimeasures \overline{M} on ℕ^{∗} we have ∃c ∀σ (\overline{M}(σ) < c · M(σ)). It is straightforward to prove the existence of such an M.

5. Throughout this note we let M denote a fixed universal left r.e. continuous semimeasure on ℕ^{∗}, and we fix M_{s}(σ) as above. Our definitions and results will not depend on the choice of M and M_{s}(σ).

6. Given Q ⊆ ℕ^{ℕ} and n ∈ ℕ, let Q↾n = {Y ↾n | Y ∈ Q}. Note that Q↾n is a subset of ℕ^{n}, which is a prefix-free subset of ℕ^{∗}. For any prefix-free set S ⊆ ℕ^{∗} let M(S) = ∑_{σ∈S} M(σ).

7. A set Q ⊆ ℕ^{ℕ} is said to be deep if there exists a recursive function r : ℕ → ℕ such that ∀n (M(Q↾r(n)) ≤ 2^{−n}).

Theorem 3.2 ([3, Theorem 5.3]). Let p : ℕ → ℕ be a recursive function, and let Q ⊆ ∏ p be deep and Π_{1}^{0}. Then (∀X ∈ MLR) (∀Y ∈ Q) (Y ≤_{T} X ⇒ 0′ ≤_{T} X).

Proof. A difference test is a pair of sequences U_{n}, V_{n}, n ∈ ℕ of uniformly Σ_{1}^{0} subsets of {0, 1}^{ℕ} such that ∀n (λ(U_{n} \V_{n}) ≤ 2^{−n}). A real X ∈ {0, 1}^{ℕ} is said to be difference random [6] if for all such difference tests we have ∃n (X ∉ U_{n} \V_{n}). We shall use the following result of Franklin and Ng [6]: X is difference random if and only if X is Martin-Löf random and ≱_{T} 0′.

Let p and Q be as in the hypothesis of Theorem 3.2. Let r be a recursive function such that ∀n (M(Q↾r(n)) ≤ 2^{−n}). Since p and r are recursive and Q is a Π_{1}^{0} subset of ∏ p, it follows by König’s Lemma that Q↾r(n) is Π_{1}^{0} uniformly in n. Given a partial recursive functional Φ, consider the left r.e. continuous semimeasure M_{Φ} on ℕ^{∗} given by M_{Φ}(σ) = λ({X ∈ {0, 1}^{ℕ} | Φ^{X}↾|σ| = σ}). Since M is a universal left r.e. continuous semimeasure on ℕ^{∗}, let c_{Φ} be a constant such that ∀σ (M_{Φ}(σ) ≤ c_{Φ} · M(σ)). Let

U_{n} = {X ∈ {0, 1}^{ℕ} | (∀i < r(n)) (Φ^{X}(i) ↓)}

and let V_{n} = {X ∈ U_{n} | Φ^{X}↾r(n) ∉ Q↾r(n)}. Then U_{n} and V_{n} are uniformly Σ_{1}^{0} and λ(U_{n} \ V_{n}) = M_{Φ}(Q↾r(n)) ≤ c_{Φ} · M(Q↾r(n)) ≤ c_{Φ} · 2^{−n}. We now see that if Φ^{X} ∈ Q then X is not difference random, so by [6] X ∈ MLR implies 0′ ≤_{T} X. Since Φ is an arbitrary partial recursive functional, Theorem 3.2 is proved.

Theorem 3.3 ([3, Theorem 7.6(ii)]). Let p be a recursive function such that ∑_{i=0}^{∞} p(i)^{−1} = ∞. Then, we can effectively find a partial recursive function ψ : ⊆ ℕ → ℕ such that the Π_{1}^{0} set Q = {Y ∈ ∏ p | Y ∩ ψ = ∅} is deep.

Proof. We may safely assume that p(i) > 0 for all i, because otherwise Q = ∅. Since p is recursive and ∑_{i} p(i)^{−1} = ∞, let r : ℕ → ℕ be recursive such that ∑_{r(n)≤i<r(n+1)} p(i)^{−1} > 2^{n} holds for all n. We shall have ψ = ⋃_{s} ψ_{s} where ψ_{s} is defined recursively by stages, as follows.

Stage 0. Let ψ_{0} = ∅.

Stage s + 1. Let Q_{s} = {Y ∈ ∏ p | Y ∩ ψ_{s} = ∅} and let n = (s + 1)_{0} = the largest n such that 2^{n} is a divisor of s + 1. There are three cases.

Case 1. If M_{s}(Q_{s}↾r(n + 1)) ≤ 2^{−n} then do nothing, i.e., ψ_{s+1} = ψ_{s}.

Case 2. Otherwise, if {i | r(n) ≤ i < r(n + 1)} ⊆ dom(ψ_{s}) then again do nothing, i.e., ψ_{s+1} = ψ_{s}.

Case 3. Otherwise, pick an i such that r(n) ≤ i < r(n + 1) and i ∉ dom(ψ_{s}). For each j < p(i) let Q_{s}^{j} = {X ∈ Q_{s} | X(i) = j}. Thus Q_{s} = ⋃_{j<p(i)} Q_{s}^{j} and Q_{s}↾r(n + 1) = ⋃_{j<p(i)} Q_{s}^{j}↾r(n + 1) and these unions are disjoint unions. Since M_{s}(Q_{s}↾r(n + 1)) > 2^{−n}, there is at least one j < p(i) such that M_{s}(Q_{s}^{j}↾r(n + 1)) > 2^{−n}p(i)^{−1}. Pick such a j and let ψ_{s+1} = ψ_{s} ∪ {⟨i, j⟩}.

In Case 3 we have Q_{s+1} = Q_{s} \ Q_{s}^{j}, hence Q_{s+1}↾r(n + 1) = Q_{s}↾r(n + 1) \ Q_{s}^{j}↾r(n + 1), hence

\begin{matrix}M(Q_{s+1}↾r(n + 1)) = M(Q_{s}↾r(n + 1)) − M(Q_{s}^{j}↾r(n + 1)) \\ ≤ M(Q_{s}↾r(n + 1)) − M_{s}(Q_{s}^{j}↾r(n + 1)) \\ < M(Q_{s}↾r(n + 1)) − 2^{−n}p(i)^{−1}. \end{matrix}  (1)

But M(Q_{0}↾r(n + 1)) ≤ 1 < ∑_{r(n)≤i<r(n+1)} 2^{−n}p(i)^{−1}, so from (1) we see that for each n Case 3 holds at fewer than r(n + 1) − r(n) many stages s + 1 with (s + 1)_{0} = n, and Case 2 never holds. Hence Case 1 holds at stage s + 1 for all sufficiently large s such that (s + 1)_{0} = n, hence M_{s}(Q_{s}↾r(n + 1)) ≤ 2^{−n} for all such s, so letting Q = ⋂_{s} Q_{s} we have M(Q↾r(n + 1)) ≤ 2^{−n}, Q.E.D.

Theorem 3.4 (Miller). Let p be a recursive function such that ∑_{i=0}^{∞} p(i)^{−1} = ∞. Then, we can find a partial recursive function ψ : ⊆ ℕ → ℕ such that (∀X ∈ MLR) (∀Y ∈ ∏ p) (if Y ∩ ψ = ∅ and Y ≤_{T} X then 0′ ≤_{T} X).

Proof. This is immediate from Theorems 3.2 and 3.3.

Corollary 3.5 (Stephan [20]). If X ∈ MLR is of PA-degree, then 0′ ≤_{T} X.

Proof. Applying Theorem 3.4 with p(i) = 2 for all i, we obtain a disjoint pair of recursively enumerable sets A_{0} = {i | ψ(i) = 0} and A_{1} = {i | ψ(i) = 1} with the following property: (∀Y ∈ {0, 1}^{ℕ}) (if Y separates A_{0} from A_{1} then (∀X ∈ MLR) (Y ≤_{T} X ⇒ 0′ ≤_{T} X)). The corollary follows, because any X which is of PA-degree computes a separating function for any disjoint pair of recursively enumerable sets.

4 Linear universality

Despite Theorems 3.2 and 3.4, it is not clear whether the following holds:

If p : ℕ → ℕ is nondecreasing and recursive and ∑_{i=0}^{∞} p(i)^{−1} = ∞,
then (∀X ∈ MLR) (∀Y ∈ DNR_{p}) (Y ≤_{T} X ⇒ 0′ ≤_{T} X).

The difficulty here is that, depending on our choice of a standard enumeration of the partial recursive functions, there may or may not exist a one-to-one recursive function r : ℕ → ℕ such that ∀i (ψ(i) ≃ φ_{r(i)}(r(i))) and ∑_{i=0}^{∞} p(r(i))^{−1} = ∞. See also the remarks of Bienvenu and Porter concerning their [3, Definition 7.5].

However, as we shall explain in this section and the next, the statement displayed above holds if we replace DNR functions by linearly DNR functions.

Definition 4.1. Let ψ : ⊆ ℕ → ℕ be a partial recursive function. We say that ψ is universal if for all partial recursive functions φ : ⊆ ℕ → ℕ there exists a recursive function r : ℕ → ℕ such that ∀i (φ(i) ≃ ψ(r(i))). We say that ψ is linearly universal if it is “universal via linear functions,” i.e., for all partial recursive functions φ : ⊆ ℕ → ℕ there exist constants a, b ∈ ℕ such that ∀i (φ(i) ≃ ψ(ai + b)).

Example 4.2. Let φ_{e}, e ∈ ℕ be a standard enumeration of the 1-place partial recursive functions. The partial recursive function ψ defined by ψ(i) ≃ φ_{i}(i) is universal. The partial recursive function ψ defined by ψ(2^{e}(2i + 1)) ≃ φ_{e}(i) is linearly universal.

Lemma 4.3. If a partial recursive function ψ : ⊆ ℕ → ℕ is linearly universal, then it is “uniformly linearly universal.” More precisely, there exist primitive recursive functions a, b : ℕ → ℕ \ {0} such that ∀e ∀i (φ_{e}(i) ≃ ψ(a(e)i + b(e))).

Proof. Fix an index ê such that ∀e ∀i (φê(2^{e}(2i+1)) ≃ φ_{e}(i)). Since ψ is linearly universal, fix constants â, b̂ ∈ ℕ such that ∀i (φê(i) ≃ ψ(âi + b̂)). For all e and all i we have φ_{e}(i) ≃ φê(2^{e}(2i + 1)) ≃ ψ(â2^{e}(2i + 1) + b̂), so we may take a(e) = 2^{e+1}â and b(e) = 2^{e}â + b̂. Since φê is not a constant function, we have â > 0, hence a(e) > 0 and b(e) > 0 for all e.

The next two theorems improve the conclusions of Theorems 3.3 and 3.4 by saying that they hold for any ψ which is linearly universal.

Theorem 4.4 ([3, Theorem 7.6(ii)]). Let p be a nondecreasing recursive function such that ∑_{i=0}^{∞} p(i)^{−1} = ∞. Let ψ be a partial recursive function which is linearly universal. Then the Π_{1}^{0} set Q = {Y ∈ ∏ p | Y ∩ ψ = ∅} is deep.

Proof. Let \overline{e} ∈ ℕ be given. Since ψ is linearly universal, let \overline{a} = a(\overline{e}) and \overline{b} = b(\overline{e}) where a, b : ℕ → ℕ are fixed primitive recursive functions as given by Lemma 4.3. Thus we have φ\overline{e}(i) ≃ ψ(\overline{a}i + \overline{b}) for all i. Define \overline{p} : ℕ → ℕ by \overline{p}(i) = p(\overline{a}i+\overline{b}). Since p is recursive and nondecreasing with ∑_{i} p(i)^{−1} = ∞, we claim that \overline{p} is likewise recursive and nondecreasing with ∑_{i} \overline{p}(i)^{−1} = ∞. To see this, note that for all i and j we have \overline{a}i+\overline{b} ≤ \overline{a}i+\overline{b}+j, hence \overline{p}(i) = p(\overline{a}i+\overline{b}) ≤ p(\overline{a}i+\overline{b}+j), hence \overline{p}(i)^{−1} ≥ p(\overline{a}i+\overline{b}+j)^{−1}, hence \overline{a} \overline{p}(i)^{−1} ≥ ∑_{j<\overline{a}} p(\overline{a}i+\overline{b}+j)^{−1}, hence \overline{a} ∑_{i} \overline{p}(i)^{−1} ≥ ∑_{i} ∑_{j<\overline{a}} p(\overline{a}i + \overline{b} + j)^{−1} = ∑_{j≥\overline{b}} p(j)^{−1} = ∞, hence ∑_{i} \overline{p}(i)^{−1} = ∞ as claimed. But then, applying Theorem 3.3 to \overline{p}, we can effectively find a partial recursive function \overline{ψ} : ℕ → ℕ such that the Π_{1}^{0} set \overline{Q} = \{\overline{Y} ∈ ∏ \overline{p} | \overline{Y} ∩ \overline{ψ} = ∅\} is deep.

Our construction of \overline{ψ} given \overline{e} is uniform in the following sense: there is a primitive recursive function which maps an arbitrary \overline{e} to an index of the corresponding partial recursive function \overline{ψ}. Therefore, by the Recursion Theorem (a.k.a., the Recursion-Theoretic Fixed Point Theorem, see [14, §11.2]) we can find an \overline{e} which is an index of the corresponding \overline{ψ}. For this \overline{e} and for all i we have \overline{ψ}(i) ≃ φ\overline{e}(i) ≃ ψ(\overline{a}i + \overline{b}). Thus the recursive functional Y ↦ \overline{Y} given by \overline{Y} (i) = Y (\overline{a}i + \overline{b}) maps Q into \overline{Q}. Since \overline{Q} is deep, it follows by [3, Theorem 6.4] that Q is deep, Q.E.D.

Theorem 4.5 (essentially due to Miller). Let p : ℕ → ℕ be a nondecreasing recursive function such that ∑_{i=0}^{∞} p(i)^{−1} = ∞. Let ψ : ⊆ ℕ → ℕ be a partial recursive function which is linearly universal. Then

(∀X ∈ MLR) (∀Y ∈ ∏ p) (if Y ∩ ψ = ∅ and Y ≤_{T} X then 0′ ≤_{T} X).

Proof. This is immediate from Theorems 3.2 and 4.4.

5 Some Muchnik degrees in E_{w}

Recall from [17, 18, 19] that E_{w} is the lattice of Muchnik degrees of nonempty Π_{1}^{0} subsets of {0, 1}^{ℕ}. Recall also from [15, 17, 18, 19] that r_{1} = deg_{w}(MLR) ∈ E_{w} and 0 < r_{1} < 1, where 0 and 1 are the bottom and top Muchnik degrees in E_{w}. The purpose of this section is to define and discuss some specific, natural Muchnik degrees in E_{w} which are associated with Theorems 2.2 and 4.5.

Definition 5.1. A function Y : ℕ → ℕ is said to be linearly DNR if Y ∩ ψ = ∅ for some linearly universal partial recursive function ψ : ⊆ ℕ → ℕ. We write LDNR = {Y ∈ ℕ^{ℕ} | Y is linearly DNR} and LDNR_{REC} = {Y ∈ LDNR | Y ∈ ∏ p for some recursive function p}. Given p : ℕ → ℕ let d_{p} = deg_{w}(LDNR_{p}) be the Muchnik degree of LDNR_{p} = LDNR ∩ ∏ p.

Remark 5.2.

1. It is easy to see that deg_{w}(LDNR) = deg_{w}(DNR) = d and deg_{w}(LDNR_{REC}) = deg_{w}(DNR_{REC}) = d_{REC}, and by [1, 15, 17] these Muchnik degrees belong to E_{w} and we have 0 < d < d_{REC} < r_{1}. Moreover d = inf_{p} d_{p} where p ranges over all functions, and d_{REC} = inf_{p} d_{p} where p ranges over all recursive functions.

2. Note that LDNR and LDNR_{REC} are independent of the choice of a standard enumeration of the partial recursive functions. Moreover, LDNR_{p} and d_{p} are also independent of this choice, provided p is nondecreasing. In particular, the Muchnik degree d_{p} is specific and natural^{1} provided p is specific, natural, and nondecreasing. This would not be the case if we had based our definition of d_{p} on DNR instead of LDNR. By using LDNR instead of DNR, we can now sharpen the observations in [15, §10].

3. Let p be nondecreasing and unbounded such that p(0) ≥ 2. Let ψ be a linearly universal partial recursive function. Is the Muchnik degree of Q = {Y ∈ ∏ p | Y ∩ ψ = ∅} independent of the choice of ψ? If so, then we could define d_{p} more simply as d_{p} = deg_{w}(Q). Our actual definition of d_{p} circumvents this question, at the cost of extra complication.

4. Clearly ∀i (p(i) ≤ q(i)) implies d_{q} ≤ d_{p}. There are many open questions here concerning specific, natural Muchnik degrees in E_{w}. For instance, letting p(i) = max(i^{2}, 1) and q(i) = max(i^{3}, 1), do we have d_{q} < d_{p}?

1For an explanation of what we mean by specific and natural, see [19, footnote 2].

Lemma 5.3. The predicates “φ_{e} is linearly universal” and “Y is linearly DNR” are Σ_{3}^{0}.

Proof. Fix an index ê such that φê is linearly universal. Then for all e, φ_{e} is linearly universal if and only if ∃a ∃b ∀i (φê(i) ≃ φ_{e}(ai + b)). A Tarski/Kuratowski computation [14, §14.3] shows that this predicate is Σ_{3}^{0}. Moreover, Y ∈ LDNR if and only if ∃e (φ_{e} is linearly universal and Y ∩φ_{e} = ∅), which is again Σ_{3}^{0}.

Theorem 5.4. Let p : ℕ → ℕ be a nondecreasing recursive function such that p(0) ≥ 2. Then d_{p} ∈ E_{w}. Moreover, d_{p} ≤ r_{1} if and only if ∑_{i=0}^{∞} p(i)^{−1} < ∞, and d_{p} ≥ r_{1} if and only if p is bounded, in which case d_{p} = 1.

Proof. Lemma 5.3 implies that LDNR_{p} is Σ_{3}^{0}, and our assumption ∀i (p(i) ≥ 2) implies that LDNR_{p} includes a nonempty Π_{1}^{0} subset of {0, 1}^{ℕ}. It follows by the Σ_{3}^{0} Embedding Lemma (see [17, Lemma 3.3] or [18, §3.3]) that LDNR_{p} ≡_{w} D_{p} for some nonempty Π_{1}^{0} set D_{p} ⊆ {0, 1}^{ℕ}. Thus d_{p} = deg_{w}(D_{p}) ∈ E_{w}. Theorem 2.2 tells us that ∑_{i} p(i)^{−1} < ∞ implies d_{p} ≤ r_{1}. Theorem 4.5 tells us that ∑_{i} p(i)^{−1} = ∞ implies d_{p} ≰ r_{1}. A theorem of Jockusch [10, Theorem 5] says that if p is bounded then d_{p} = 1. A theorem of Greenberg and Miller [7] says that if p is unbounded then d_{p} ≱ r_{1}.

Definition 5.5. An order function is an unbounded nondecreasing recursive function p : ℕ → ℕ such that p(0) ≥ 2. Let us say that p is slow-growing if ∑_{i} p(i)^{−1} = ∞, otherwise fast-growing. Define LDNRslow = ⋃_{p} LDNR_{p} and dslow = deg_{w}(LDNRslow) = inf_{p} d_{p} where p ranges over all slow-growing order functions. We could define LDNRfast and dfast similarly, but this would give us nothing new, because we would have LDNRfast = LDNR_{REC} and dfast = d_{REC}.

Theorem 5.6. For each slow-growing order function p, we have d_{p} ∈ E_{w} and d_{REC} < d_{p} < 1 and d_{p} is incomparable with r_{1}. And similarly, we have dslow ∈ E_{w} and d_{REC} < dslow < 1 and dslow is incomparable with r_{1}.

Proof. The statements concerning d_{p} follow directly from Theorem 5.4. To obtain the same conclusions for dslow, first imitate the proof of Lemma 5.3 to show that LDNRslow is Σ_{3}^{0}, then imitate the proof of Theorem 5.4.

Remark 5.7. Given an order function p, Khan [11, Theorems 3.13 and 3.15] has shown how to construct order functions p^{+} and p^{−} such that d_{p^{+}} < d_{p} < d_{p^{−}}. If p is a slow-growing order function, it should be possible to construct a slow-growing order function p^{+} such that d_{p^{+}} < d_{p}. This would imply that dslow < d_{p} for all slow-growing order functions p.

References

[1] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman. Comparing DNR and WWKL. Journal of Symbolic Logic, 69(4):1089–1104, 2004. 2, 7 [2] A. Beckmann, V. Mitrana, and M. Soskova, editors. Evolving Computabil-

ity, Proceedings of CiE 2015 (Bucharest). Number 9136 in Lecture Notes in Computer Science. Springer, 2015. XV + 363 pages. 10

[3] Laurent Bienvenu and Christopher P. Porter. Deep Π_{1}^{0} classes. Bulletin of Symbolic Logic, 22(2):249–286, 2016. 2, 3, 4, 5, 6

[4] Z. Chatzidakis, P. Koepke, and W. Pohlers, editors. Logic Colloquium ’02: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic and the Colloquium Logicum, held in Münster, Germany, August 3–11, 2002. Number 27 in Lecture Notes in Logic. Association for Symbolic Logic, 2006. VIII + 359 pages. 10

[5] J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors. Logic, Methodology and Philosophy of Science VIII. Number 126 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989. XVII + 702 pages. 9

[6] Johanna N. Y. Franklin and Keng Meng Ng. Difference randomness. Proceedings of the American Mathematical Society, 139(1):345–360, 2011. 4

[7] Noam Greenberg and Joseph S. Miller. Diagonally non-recursive functions and effective Hausdorff dimension. Bulletin of the London Mathematical Society, 43(4):636–654, 2011. 8

[8] Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson, and Keita Yokoyama. Propagation of partial randomness. Annals of Pure and Applied Logic, 165(2):742–758, 2014. http://dx.doi.org/10.1016/j.apal.2013.10.006. 2

[9] W. M. Phillip Hudelson. Mass problems and initial segment complexity. Journal of Symbolic Logic, 79(1):20–44, 2014. 2

[10] Carl G. Jockusch, Jr. Degrees of functions with no fixed points. In [5], pages 191–201, 1989. 2, 8

[11] Mushfeq Khan. Some results on algorithmic randomness and computabilitytheoretic strength. PhD thesis, University of Wisconsin, 2014. VII + 93 pages. 2, 8

[12] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. Transactions of the American Mathematical Society, 363(10):5465–5480, 2011. 2

[13] Bjørn Kjos-Hanssen and Stephen G. Simpson. Mass problems and Kolmogorov complexity. 4 October 2006. Preprint, 1 page. 2

[14] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages. 6, 8

[15] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11(1):1–27, 2005. 2, 7 [16] Stephen G. Simpson. Almost everywhere domination and superhighness.

Mathematical Logic Quarterly, 53(4–5):462–482, 2007. 3

[17] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75(2):287–297, 2007. 7, 8

[18] Stephen G. Simpson. Mass problems associated with effectively closed sets. Tohoku Mathematical Journal, 63(4):489–517, 2011. 7, 8

[19] Stephen G. Simpson. Degrees of unsolvability: a tutorial. In [2], pages 83–94, 2015. 7

[20] Frank Stephan. Martin-Löf random and PA-complete sets. In [4], pages 341–347, 2006. 2, 5