Jump to ContentJump to Main Navigation
Computability and Randomness$

André Nies

Print publication date: 2009

Print ISBN-13: 9780199230761

Published to Oxford Scholarship Online: May 2009

DOI: 10.1093/acprof:oso/9780199230761.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. Subscriber: null; date: 21 October 2021

Diagonally noncomputable functions

Diagonally noncomputable functions

Chapter:
(p.144) 4 Diagonally noncomputable functions
Source:
Computability and Randomness
Author(s):

André Nies

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780199230761.003.0004

Abstract and Keywords

This chapter motivates the interaction from randomness to computability. As an example of this interaction it shows how to use Martin–Löf randomness to give a simple injury-free solution to Post's problem as a result of Kucera. The chapter studies diagonally noncomputable (d.n.c.) functions and looks closely at two valued d.n.c. functions. The former can be used for a more general solution of Post's problem and an injury free proof of the Friedberg–Muchnik theorem. The chapter then matches n-randomness with n-fixed point freeness.

Keywords:   diagonally noncomputable function, initial segment complexity, Post's problem, Friedberg–Muchnik theorem, injury freeness, PA completeness, n-randomness

We discuss the interactions between computability and randomness. Traditionally the direction is from computability to randomness. In this direction, two types can be distinguished.

Interaction 1a: computability theoretic notions are used to obtain mathematical definitions for the intuitive concept of a random set.

For instance, in Chapter 3 we introduced ML-randomness and its variants using test notions which are based on computable enumerability and other concepts.

Interaction 1b: computational complexity is used to analyze randomness properties of a set.

An example is the result on page 135 that Z is weakly 2-random iff Z is ML-random and Z, ∅′ form a minimal pair.

The interaction also goes the opposite way.

Interaction 2: concepts related to randomness enrich computability theory.

We have already seen examples of this in Chapter 3: the real number Ω and the operator X ↦ ΩX. In Section 5.2 we will study K-triviality, a property of sets that means being far from random. This property turns out to be equivalent to the lowness property of being low for ML-randomness. The class of K-trivial sets has interesting properties from the computability-theoretic point of view. For instance, each K-trivial set is superlow. Many equivalent definitions are known, and all touch in some way upon randomness-related concepts.

In the spirit of Interaction 2, in this chapter we study diagonally noncomputable functions. They arise naturally when one studies ML-random sets. We have briefly considered d.n.c. functions in Remark 1.8.30.

4.0.1 Definition.

  1. (i) A function f: ℕ ↦ ℕ is diagonally noncomputable, or d.n.c. for short, if f (e) ≠ J (e) for any e such that J (e)↓.

  2. (ii) A set D has d.n.c. degree if there is a d.n.c. function fT D.

A d.n.c. function f is incomputable, for otherwise f = Φe for some e, and hence f (e) = Φe(e) = J (e). We think of f as far from computable since it effectively provides the value f (e) as a counterexample to the hypothesis that f = Φe.

If Z is ML-random, a finite variant of the function λn.Zn is diagonally non-computable, because Ze = J(e) implies K (Ze) ≤+ 2 log e. In Section 4.1 we study the sets of d.n.c. degree, or, equivalently, the sets that compute a fixed point free function g (namely W g(x)Wx for each x).

(p.145) To be of d.n.c. degree is a conull highness property (intuitively speaking, it is weak). Sets of d.n.c. degree are characterized by a property stating that the initial segment complexity grows somewhat fast. Thus the highness property to be of d.n.c. degree can also be interpreted as to be “somewhat random”. This characterization is an analog of Schnorr's Theorem 3.2.9. As a consequence, the sets of d.n.c. degree are closed upwards with respect to the preordering ≤K which compares the degree of randomness of sets (Definition 5.6.1 below.)

In Section 4.2 we discuss Kučera's injury-free solution to Post's problem, a further instance of Interaction 2. It is based on a d.n.c. function f <T ∅′, but takes a particularly simple form when f is a finite variant of the function λn. Zn for a ML-random Δ 2 0 set Z. We use that f is d.n.c. to build a promptly simple set AT f. To make f permit changes of A we threaten that f(k) = J(k) for appropriate numbers k. These methods can be extended to an injury-free construction of a pair of Turing incomparable c.e. sets.

In Section 4.3 we strengthen the concept of a d.n.c. function in various ways. We use the stronger concepts to gain a better understanding of the computational complexity of n-random sets (this is Interaction 1b). Firstly, we show that if a set Z is ML-random and computes a {0, 1}-valued d.n.c. function, then Z already computes the halting problem. Secondly, we introduce a hierarchy of properties of functions strengthening fixed point freeness, and show that an n-random set computes a function at level n of that hierarchy.

4.1 D.n.c. functions and sets of d.n.c. degree

We characterize the sets of diagonally noncomputable degree via a growth condition on the initial segment complexity. Thereafter, we show that the only c.e. sets of diagonally noncomputable degree are the Turing complete ones.

Basics on d.n.c. functions and fixed point freeness

4.1.1 Proposition.

  1. (i) No d.n.c. function f is computable.

  2. (ii) ∅′ has d.n.c. degree via some function ftt ∅′.

Proof.

  1. (i) If f = Φe is total, then f (e) = J (e), so f is not d.n.c.

  2. (ii) A {0, 1}-valued d.n.c. function ftt∅′ was given in Remark 1.8.30□.

The following provides further examples of d.n.c. functions.

4.1.2 Proposition.

  1. (i) There is c ∈ ℕ such that

    n K ( Z n ) > K ( n ) + c Z h a s d . n . c . d e g r e e
    via a function f that agrees with λn. Zn on almost all n (hence ftt Z).

  2. (ii) Each ML-random set Z has d.n.c. degree via a function ftt Z.

Proof. (i) Recall from page 12 that we identify strings in {0, 1} with numbers. Let c be a constant such that, for each σ, if y = J(U(σ))↓ then K (y)≤ |σ| + c. (p.146) If Zn = J (n) and σ is a shortest U-description of n, then J(U(σ)) = Zn and hence K (Zn)≤ |σ| + c = K (n) + c. Thus Zn = J (n) fails for almost all n□.

(ii) If Z is ML-random then there is b such that ∀nK (Zn) ≥ nb. Since K (n)≤+ 2 log n, this implies K (Zn) > K (n) + c for almost all n.

Actually, by 8.3.6, every infinite subset of a ML-random set has d.n.c. degree.

By the Recursion Theorem 1.1.5, for each computable function g there is x such that Wx = W g (x). The functions of the following type are far from computable in the sense that this fixed point property fails.

4.1.3 Definition. A function g is fixed point free (f.p.f.) if ∀ x W g (x)Wx.

The two notions of being far from computable coincide up to Turing degree.

4.1.4 Proposition. Let D ⊆ ℕ. Then D has d.n.c. degreeD computes a fixed point free function. The equivalence is uniform.

Proof. It suffices to show that each d.n.c. function computes a fixed point free function and vice versa.

⇒: Suppose that the function f is diagonally noncomputable. We construct a fixed point free function gT f. Let

α ( x ) the first element enumerated into W x .
Let p be a reduction function for α (see Fact 1.2.15). Thus α (x) ≃ J (p (x)) for each x. Let gT f be a function such that g (x) is a c.e. index for {f (p (x))}. Then WxWg(x) unless # Wx = 1. If # Wx = 1, then Wx = {α (x)} = {J (p (x))}. Because f is d.n.c., J (p (x)) ≠ f (p (x)), so WxW g (x).

⇐: Suppose that the function g is fixed point free. Let h be a computable function such that

W h ( x ) = { W J ( x ) if J ( x ) , otherwise .
If J (x)↓ then W g (h(x))W J (x) and hence g (h (x)) ≠ J (x). So f = gh is d.n.c. and fT g.

In Definition 4.3.14 we will introduce the hierarchy of n-fixed point free functions (n ≥ 1). The lowest level n = 1 consists of the functions of Definition 4.1.3. The extendability of this definition to higher levels is one of the reasons why we do not define fixed point freeness of a function g by the weaker condition that Φg (x) ≠ Φx.

By Exercise 8.3.6, A has d.n.c. degree iff A computes an infinite subset of a ML-random set.

Exercises. Show the following.

4.1.5. Let f be a d.n.c. function. For each partial computable function ψ, there is a function f ˜ T f such that f ˜ ( e ) ψ ( e ) for any e such that ψ (e)↓.

4.1.6. No 1-generic set G (see Definition 1.8.51) is of d.n.c. degree. In particular, no 1-generic set computes a ML-random set.

(p.147) By the following, the properties of functions introduced above are independent of the particular choice of a jump operator, or a universal uniformly c.e. sequence, as far as the Turing degree of the function is concerned.

4.1.7. Suppose that J ^ is a universal partial computable function (Fact 1.2.15). Then each d.n.c. function f is Turing equivalent to a d.n.c. function f ^ with respect to J ^ , and vice versa.

4.1.8. Suppose that ( W ^ e ) e is a universal uniformly c.e. sequence with the padding property, as in Exercise 1.1.12. Then each f.p.f. function g is Turing equivalent to an f.p.f. function g ^ with respect to ( W ^ e ) e , and vice versa.

The initial segment complexity of sets of d.n.c. degree

Schnorr's Theorem 3.2.9 states that the ML-random sets are the ones with a nearly maximal growth of the initial segment complexity in the sense of K. The following result of Kjos-Hanssen, Merkle and Stephan 2006 characterizes the sets of d.n.c. degree by a growth condition stating that the initial segment complexity grows somewhat quickly. This yields a further proof besides the one in Exercise 4.1.7 that the property to be of d.n.c. degree does not depend of the somewhat arbitrary definition of the universal partial computable function J.

4.1.9 Theorem. The following are equivalent for a set Z.

  1. (i) Z has d.n.c. degree.

  2. (ii) There is a nondecreasing unbounded function gT Z such thatn [g(n) ≤ K(Zn)].

It is useful to think of the function g in (ii) as slowly growing. By 2.4.2 KC, so we could equivalently take the initial segment complexity of Z via C.

Proof. (ii) ⇒ (i): The idea is the same as in the proof of Proposition 4.1.2. Suppose (ii) holds via gT Z, and let h (r) = min {m: g (m)≥ r}. (Think of h as a function that grows quickly.) Note that Z computes the function f (r) = Zh (r). If Zh (r) = J (r) and σ is a shortest description of r then J (U(σ)) = Zh (r) and hence K (Zh (r))≤+ K (r) = |σ| ≤+ 2 log r. However, by the definition of h we have K (Zh (r))≥ r. Thus Zh (r) = J (r) fails for almost all r.

(i) ⇒ (ii): Suppose that (ii) fails. Let Γ = Φi be a Turing functional such that ΓZ is total. We show that ΓZ is not a d.n.c. function, namely, ΓZ(e) = J (e) for some e. For each σ, one can effectively determine an e (σ) such that Φe (σ)(y) ≃ ΓU(σ)(y): the number e (σ) encodes a Turing program implementing a procedure that on input y first runs U on the input σ in case of convergence it takes the output ρ as an oracle string and attempts to compute Γρ(y). Let

h ( r ) = max ( { r } { use Γ Z ( e ( σ ) ) : | σ | r } ) .
The function g given by g(m) = max {r: h (r)≤ m} is computable in Z, nondecreasing and unbounded. If (ii) fails, there is an m such that r ¯ = g ( m ) > K ( Z m ) . So U(σ) = Zm for some σ such that | σ | < r ¯ . Let e = e(σ). Since (p.148) h ( r ¯ ) m we have use ΓZ(e) ≤ m. Thus J (e) = Φe(e) = ΓU (σ)(e) = ΓZ(e).

With a minor modification, the foregoing proof yields a characterization of the sets Z such that there is a d.n.c. function fwtt Z. The characterizing condition is that K (Zn) be bounded from below by an order function, i.e., a nondecreasing unbounded computable function.

4.1.10 Theorem. The following are equivalent for a set Z.

  1. (i) There is a d.n.c. function fwtt Z.

  2. (ii) There is an order function g such thatn [g (n)≤ K (Zn)].

  3. (iii) There is a d.n.c. function ftt Z.

Proof. (ii) ⇒ (iii) is proved in the same way as the implication (ii) ⇒ (i) in Theorem 4.1.9. Notice that if g is computable then ftt Z.

For (i) ⇒ (ii), note that in the proof of (i) ⇒ (ii) above, if there is a computable bound on the use of Γ, we can choose h and hence g computable.

A completeness criterion for c.e. sets

The only c.e. sets of d.n.c. degree are the Turing complete ones. This result of Arslanov 1981 builds on work of Martin (1966a) and Lachlan 1968.

4.1.11 Theorem. (Completeness Criterion) Suppose the set Y is c.e.

  1. (i) There is a d.n.c. function fT YY is Turing complete.

  2. (ii) There is a d.n.c. function fwtt YY is wtt-complete.

The result can be viewed as a generalization of the Recursion Theorem 1.1.5 when stated in terms of fixed point free functions: for every function g <T∅′ of c.e. degree there is an x such that W g (x) = Wx. For instance, if A <T∅′ is c.e., then the function p A ¯ has such a fixed point.

Proof idea. If Y is a Turing complete set then Y has d.n.c. degree by Proposition 4.1.1. If Y is wtt-complete then there is a d.n.c. function fwtt Y by the same proposition.

Now suppose there is a Turing functional Φ such that f = ΦY is a d.n.c. function. For an appropriate reduction function p (see 1.2.15), when e enters ∅′ at a stage s such that Φ s Y s ( p ( e ) ) , we threaten that this value equal J(p(e)). Then Ys is forced to change below the use of Φ s Y s ( p ( e ) ) . So, once Φ s Y s ( p ( e ) ) stable at stage s(e), e cannot enter ∅′ any more. Since Y is c.e., s (e) is the first stage where Φ s Y s ( p ( e ) ) converges and Ys(x) = Y (x) for each x less than the use. So Y can compute such a stage, and ∅′ ≤T Y. If the use of Φ is bounded by a computable h, then the use of the reduction procedure is bounded by h(p(e)) on input e, hence ∅′ ≤wtt Y.

Proof details. We define an auxiliary partial computable function α. By the Recursion Theorem we may assume that we are given a computable reduction function p such that α (e)≃ J (p (e)) for each e (see Remark 4.1.12 below).

(p.149) Construction of α.

Stage s. If e s + 1 s and y = Φ s Y s ( p ( e ) ) , let α (e)= y.

We show that ∅′ ≤T Y. Given an input e, using Y as an oracle, we compute the first stage s = s (e) such that y = Φ s Y s ( p ( e ) ) and Y is stable below the use of this computation. If e enters ∅′ at a stage ≥ s(e), we define α (e) = J (p (e)) = f (p (e)), so f is not a d.n.c. function. Thus e e s ( e ) .

4.1.12 Remark. We justify the seemingly paradoxical argument where we assume the reduction function p for α is given, even though we are actually constructing α. By Fact 1.2.15, from an index e for a partial computable function Φe one obtains a reduction function p. Based on p, in our construction we build a partial computable function Φg (e). By the Recursion Theorem 1.1.5, there is a fixed point i, namely a partial computable α = Φi such that Φg (i) = α. So in the interesting case that the given e is such a fixed point, p is a reduction function for Φg (e) = Φe.

We provide two applications of the Completeness Criterion.

Application 1. By Theorem 3.2.11 the halting probability ΩR is ML-random for each optimal prefix-free machine R, and by Proposition 3.2.30, ΩR is wtt- complete (we identify ΩR with its binary representation). We give an alternative proof of the second fact: Since ΩR is ML-random, a finite variant f of the function λn. ΩRn is d.n.c., and fwtt ΩR. Also, ΩR is left-c.e., namely, the set {q ∈ ℚ2: 0 ≤ q < ΩR} is c.e. Thus ∅′ ≤wtt {q ∈ ℚ2: 0 ≤ q < ΩR} ≡tt ΩR.

Theorem 4.3.9 below shows that ∅′ ≰tt ΩR. Thus {q ∈ ℚ2: 0 ≤ q < ΩR} is a c.e. set that is weak truth-table complete but not truth-table complete. By Theorem 4.1.10 there is a d.n.c. function ftt ΩR. Thus the Completeness Criterion 4.1.11 has no analog for truth-table reducibility.

The truth-table degree of ΩR depends on the particular choice of the optimal prefix-free machine: Figueira, Stephan and Wu 2006 have shown that there is a sequence (Ri)i ∈ℕ of such machines such that Ω R i | t t Ω R j for each pair ij.

Application 2. Recall from page 32 that a co-infinite c.e. set A is called effectively simple if there is a computable function g such that # Weg (e) ↦ WeA ≠ ∅′.

4.1.13 Proposition. An effectively simple set A is Turing complete.

Proof. By Proposition 4.1.4 it suffices to show that A computes a fixed point free function f. Since A is co-infinite, on input e, with A as an oracle one can compute a c.e. index f (e) for the set consisting of the first g (e) elements of ℕ − A. If W f(e) = We then WeA = ∅ while #Weg (e). Hence f is fixed point free.

Exercises.

4.1.14. Derive Prop. 3.4.10 from the Completeness Criterion 4.1.11 relativized to A.

4.1.15. (Friedberg and Rogers, 1959) Each hypersimple set is wtt-incomplete.

4.1.16. If A is effectively simple and not hypersimple then A is wtt-complete.

(p.150) 4.2 Injury-free constructions of c.e. sets

One can solve Post's problem and even prove the Friedberg-Muchnik Theorem 1.6.8 avoiding the priority method with injury. These results of Kučera 1986 are interesting because injury makes sets artificial due to the fact that one first fulfills tasks and then gets them undone. This does not happen in Kučera's constructions, even if they are a bit more involved.

The most direct injury-free solution to Post's problem relies on ML-randomness.

Step 1. Begin with Ω0, the set given by the bits of Ω in the even positions, which is Turing incomplete by Corollary 3.4.8 (and even low by 3.4.11).

Step 2. Build a promptly simple set A (Definition 1.7.9) Turing below Ω0.

The construction of Kučera 1986 in step 2 works for any Δ 2 0 ML-random set in place of Ω0; see Remark 4.2.4 below.

There is no injury because in step 1 there are no requirements, and in step 2 we merely meet the prompt simplicity requirements, which cannot be injured. The injury-free solution to Post's problem as it is commonly thought of nowadays is somewhat different. Step 1 uses the Low Basis Theorem. Step 2 is a more general result of independent interest. Its proof needs the Recursion Theorem.

Step 1. Use the Low Basis Theorem 1.8.37 to produce a low set of d.n.c. degree. For instance, take the 1 0 class 2ω − ℛ1, which by Theorem 3.2.9 consists entirely of ML-random, and hence d.n.c. sets. Or take the 1 0 class of {0, 1}-valued d.n.c. functions in Fact 1.8.31. The construction in the proof of Theorem 1.8 is relative to ∅′. One satisfies the requirements one by one in order. Hence they are not injured.

Step 2. Show that Turing below each Δ 2 0 set Y of d.n.c. degree one can build a promptly simple set.

The original proof in Kučera (1986) uses the Low Basis Theorem in Step 1, but avoids the Recursion Theorem in Step 2, as above. It has been criticized that in the proof of Theorem 1.8.37, injury is merely hidden using ∅′. Indeed, the effective version of the proof in Theorem 1.8.38 has injury to lowness requirements. This criticism does not apply when we avoid the Low Basis Theorem altogether and rather use Ω0 as the low set of d.n.c. degree.

Initially Kučera's motivation was to disprove the conjecture in Jockusch and Soare (1972a) that each nonempty 1 0 class without computable members contains a set Y <T∅′ such that each c.e. set AT Y is computable. Jockusch then pointed out that Kučera's proof leads to an injury-free solution to Post's problem.

For the injury-free proof of the Friedberg-Muchnik Theorem 1.6.8, Kučera developed his ideas further. Instead of carrying out two independent steps, he let the construction relative to ∅′ and the effective construction interact via the Double Recursion Theorem 1.2.16. This bears some similarity to the worker's method of Harrington. A so-called level n argument involves interacting priority constructions relative to ∅, ∅′, …, ∅ (n) (that is, workers at level i for each in), and uses an (n + 1)-fold Recursion Theorem. See Calhoun (1993).

(p.151) Each Δ 2 0 set of d.n.c. degree bounds a promptly simple set

We construct a promptly simple set Turing below any given Δ 2 0 set of d.n.c. degree. In the next subsection we describe the orginal argument in Kučera 1986, where the Recursion Theorem is avoided when the given Δ 2 0 -set is in fact ML-random. However, the more powerful method of the present construction is used for instance in the injury-free proof of the Friedberg-Muchnik Theorem. The hypothesis that Y be Δ 2 0 is necessary because, say, a weakly 2-random set has d.n.c. degree but forms a minimal pair with ∅′ (page 135).

4.2.1 Theorem. (Kučera) Let Y be a Δ 2 0 set of d.n.c. degree. Then there is a promptly simple set A such that AT Y.

Proof idea. The Completeness Criterion 4.1.11 fails for Δ 2 0 sets because there is a low set of d.n.c. degree. The construction of A can be seen as an attempt to salvage a bit of its proof in the case that Y is Δ 2 0 . Where does the proof go wrong? As before, suppose that f = ΦY is a d.n.c. function. A Δ 2 0 set Y cannot compute a stage s (e) such that Φ s Y s ( p ( e ) ) is stable from s(e) on, only a stage where it has the final value for the first time. The problem is that it may change temporarily after such a stage.

On the other hand, we do not have to code the halting problem into Y. It suffices to code the promptly simple set A we are building. For each e we meet the prompt simplicity requirement from the proof of Theorem 1.7.10

P S e : # W e = s x [ x W e , s W e , s 1 & x A s ]
.

At stage s we let x enter A for the sake of a requirement PSe only if ΦY (p(e)) has been stable from stage x to s. If we now threaten that J(p(e)) = ΦY(p(e)) then Y has to change to a value not assumed between stage x and s. This allows us to compute A from Y. It also places a strong restriction on PSe: whenever ΦY (p(e)) changes another time at t, then PSe cannot put any numbers less than t into A at a later stage.

We work with the effective approximation fs(x) = ΦY (x) [s]. (Thus, in contrast to 4.1.11, we actually consider changes of the value fs(x) rather than changes of the oracle Y.) For an appropriate computable function p, when we want to put a candidate xWe into A for the sake of PSe, we threaten that f (p (e)) equal J (p (e)). We only put x into A at stage s if ft(p (e)) has been constant since stage x. (Since ft(p (e)) settles, this holds for large enough x. Thus, PSe is still able to choose a candidate.) To show AT f, if f (p (e)) = ft(p(e)), then after stage t a number x cannot go into A for the sake of PSe. See Fig. 4.1.

Proof details. As in the proof of Theorem 4.1.11, we define an auxiliary partial computable function α. By the Recursion Theorem we are given a reduction function p for α, namely, ∀e α(e)≃J(p(e)).

(p.152)

                   Diagonally noncomputable functions

Fig. 4.1 Proof of Kučera's Theorem.

Construction of A and α. Let A 0 = ∅.

Stage s. For each e < s, if PSe is not satisfied yet, see whether there is an x, 2ex < s, such tha

(4.1)
x W e , s W e , s 1 & t x < t < s f t ( p ( e ) ) = f s ( p ( e ) )
.

If so, put x into As. Define α (e) = fs(p(e)). Declare PSe satisfied.

Verification. Clearly A is co-infinite. Choose s 0 such that ∀ ss 0 fs(p(e)) = f(p(e)). If xs 0, x ≥ 2e appears in We at stage s then x can be used to satisfy PSe. Next, we show that AT f. Given an input x, using f compute t > x such that for all e, if 2ex then ft(p (e)) = f (p (e)). Then xAxAt, for if we put x into A at a stage s > t, then, as we required that ∀t x<t<s ft(p(e))=fs(p(e)), the value α(e)=J(p(e)) = fs(p(e)) we define at stage s equals f(p(e)). Thus f is not a d.n.c. function, contradiction.

Variants of Kučera's Theorem

We modify the proof of Kučera's Theorem 4.2.1 in four ways. Firstly, we prove a version for wtt-reducibility. Secondly, we work under two stronger hypotheses on the given Δ 2 0 set Y, namely that Y is a {0, 1}-valued d.n.c. function, or that Y is ML-random. In both cases we obtain a uniform version of Kučera's Theorem. Thirdly, we combine the construction with permitting, and finally, in an exercise, we consider the case of two given Δ 2 0 sets Y 0 and Y 1.

4.2.2 Corollary. Suppose Y Δ 2 0 and there is a d.n.c. function fwtt Y (for instance, if Y is ML-random). Then there is a promptly simple set Awtt Y.

Proof. Suppose that h is a computable use bound for the procedure computing f with oracle Y. Then, at the end of the proof of Theorem 4.2.1, to compute A (x) we only need to query Y on numbers less than h (p (x))□.

Uniformity considerations for Kučera's Theorem will be important for the injury-free proof of the Friedberg–Muchnik Theorem: given an index k such that Y = Φ k , can we obtain a c.e. index for A in an effective way? Actually, to build A, we also need to know how to compute the d.n.c. function from Y. This is certainly the case when Y itself is a {0, 1}-valued d.n.c. function:

4.2.3 Corollary. There is a computable function r such that, for each k, if Y = Φ k is total and Y is a {0, 1}- valued d.n.c. function, then A = W r (k)wtt Y and A is promptly simple. An index for the reduction for Awtt Y can be obtained effectively as well.

(p.153) 4.2.4 Remark. If Y is Δ 2 0 and ML-random, then a somewhat simpler argument suffices to obtain a promptly simple set Awtt Y (and in fact the use equals the input in the reduction procedure). We do not need the Recursion Theorem or a reduction function. To ensure that Awtt Y we can directly force Ye to change by including the string Ye in an interval Solovay test G (that is, a certain effective listing of strings defined in 3.2.22). In other words, if Y is ML-random we may let Ye play the role of f (p(e)) before, so the reduction function p is not needed any longer. Since the procedure to compute the d.n.c. function λn. Yn is fixed we obtain A effectively. The reduction procedure to compute A from Y is effectively given by the above, but now it is only correct for almost all inputs because σY merely holds for almost all σ in G.

Construction of A and G. Let A 0 = ∅.

Stage s > 0. For each e < s, if PSe is not satisfied yet, check whether there is an x, 2ex < s, such that

(4.2)
x W e , s W e , s 1 & t x < t < s Y t e = Y s e
.

If so put x into A. Put the string Yse into G. Declare PSe satisfied.

Verification. Given e, choose t 0 such that ∀st 0 Yse = Ye. If xt 0 is enumerated into We at a stage s then x can be used to satisfy PSe, so PSe is met. G is a Solovay test because the requirement PSe contributes at most one interval, and this interval has length 2e.

To see that Awtt Y, choose s 0 such that σY for any σ enumerated into G after stage s 0. Given an input xs 0, using Y as an oracle, compute t > x such that Ytx = Yx. Then xAxAt, for if we put x into A at a stage s > t for the sake of PSe then x > e, so we list σ in G where σ = Yse = Ye. This contradicts the fact that σY.

We have obtained a further uniform version of Theorem 4.2.1 without using the Recursion Theorem.

4.2.5 Corollary. There is a computable r such that for each e, if Y = Φ e is total and ML-random, then A = W r (e)wtt Y and A is promptly simple□.

As mentioned at the beginning of this section, combining Corollary 3.4.11 (the bits of Ω in an odd position form a Turing incomplete ML-random set Y) with the construction in Remark 4.2.4 (to build a promptly simple set Awtt Y), we obtain an injury-free solution to Post's problem that is the simplest known when one also counts the proof that the constructed set is Turing incomplete (or, in fact, low). In comparison, the direct construction of a promptly simple K-trivial set (5.3.11 below) is easier, but it is much harder to verify that the constructed K-trivial set is even Turing incomplete (see from page 201 on). We already compared these construction briefly when we discussed natural solutions to Post's problem on page 34.

We provide two further variants of Kučera's Theorem 4.2.1.

4.2.6 Corollary. If Y Δ 2 0 has d.n.c. degree and C is an incomputable c.e. set, there is a simple set AT Y such that Awtt C.

(p.154) Proof. Instead of the prompt simplicity requirements PSe we now merely meet the requirements Re: #We = ∞ ⇒ AWe ≠ ∅. To ensure Awtt C, we ask that C permit the enumeration of x. Thus, at stage s of the construction, for each e < s, if Re is not satisfied yet, see if there is an x, 2ex < s, such that

x W e , s & C s x C s + 1 x & t x < t < s f t ( p ( e ) ) = f s ( p ( e ) ) .
If so then put x into A and define α (e) = fs(p(e)).

If We is infinite, then, because C is incomputable, infinitely many numbers x are permitted by C after they enter We. So each requirement Re is met□.

4.2.7 Exercise. No two Δ 2 0 d.n.c. sets form a minimal pair by Kučera 1988. In fact, the proof of 4.2.1 can be adapted to show that there is a promptly simple set below both of them: show that, if Y 0 and Y 1 are Δ 2 0 sets of d.n.c. degree, then there is a promptly simple set AT Y 0, Y 1.

On the other hand, a set that is Turing below all the Δ 2 0 ML-random sets is computable by Theorem 1.8.39.

An injury-free proof of the Friedberg–Muchnik Theorem ⋆

By Theorem 1.6.8 there are Turing incomparable c.e. sets A, B. An injury-free proof of this result was announced in Kučera 1986 and circulated, but not published.

Proof idea. Let P a nonempty 1 0 class, and r be a computable function, such that, if Y = Φ e is total and YP, then A = W r (e)wtt Y and A is not computable. Such a function exists either by Corollary 4.2.3 or 4.2.5. To use 4.2.3 recall that the {0, 1}-valued d.n.c. functions form a 1 0 class by Fact 1.8.31; to use 4.2.5 let P = 2ω − ℛ1.

The following attempt looks promising. The Low Basis Theorem, in the version with upper cone avoidance 1.8.39, implies that from any c.e. incomputable set B one may effectively obtain YT B ⊕∅′ ≡T∅′ such that YP and BT Y. We start with a pair of Δ 2 0 sets Y, ZP, given by indices a, b of reductions from ∅′, and, applying the function r to these indices we obtain c.e. sets A w t t Y ˜ and B w t t Z ˜ . Now by 1.8.39 we effectively obtain Δ 2 0 sets Y, ZP such that YT B and ZT A. By the Double Recursion Theorem 1.2.16 with oracle ∅′ we may assume that Y = Y ˜ and Z = Z ˜ , so that in fact AT Y and BT Z. In particular AT B (since not even YT B), and similarly BT A.

In this proof, the letters Y, Z denote either finite strings or infinite sequences of zeros and ones. In the latter case we say that Y (or Z) is total. The problem with the attempt outlined above is that in the proof of Theorem 1.8.39 we needed to know in advance that B is incomputable in order to argue that the parallel search at a stage 2 e + 2 (to suitably extend Y or to find a number n such that P 2 e + 1 { X : Φ e X ( n ) } ) terminates. The concern is that B might be computable, in which case the search may fail to terminate. Then Y remains a finite string, and P 2 e + 2 remains undefined. The solution here is to keep extending Z while the search proceeds. If it proceeds forever then Z is an infinite sequence over {0, 1} (that is, a set) which is in P, so B is in fact incomputable. Then the search terminates after all, contradiction.

(p.155) Proof details. Numbers a, b are given (think of them as Δ 2 0 -indices for Y and Z). Let A = W r (a) and B = W r(b). In a construction relative to ∅′, we build Δ 2 0 sets Y, Z and descending sequences of nonempty 1 0 classes (P e)e ∈ℕ and (Q e)e ∈ℕ (they correspond to the 1 0 classes in the proof of Theorem 1.8.39 defined at even stages). We need to be more specific as to how the parallel search is to be carried out. To do so, we divide stages i = 0, 1, … into substages t.

Construction relative to ∅′ of 1 0 classes P i, Q i and strings σ i on P i, τ i on Q i. Let σ 0 =τ 0 = ∅ and P 0 = Q 0 = P.

Stage i + 1, i = 2e. Let Q i + 1 = Q i, t = |τ i|, and τ i + 1, t = τ i. Go to substage t + 1. Substage t + 1. Check whether

  1. (a) there are σ, k such that |σ|, k<t, σ iσ, σ on P i and B ( k ) Φ e σ ( k ) , or

  2. (b) there is n < t such that P i { X : Φ e X ( n ) } .

If neither case applies, or this is the first substage of the current stage, then let τ i + 1, t + 1 be the leftmost extension of τ i + 1, t of length t + 1 which is on Q i. Increment t and proceed to the next substage.

Otherwise, let τ i + 1 = τ i,t. If (a) applies let σ i + 1 = σ and P i + 1 = P i. If (b) applies let σ i + 1 = σ i and P i + 1 = P i { X : Φ e X ( n ) } . . Increment i and proceed to the next stage.

Stage i + 1, i = 2 e + 1. Proceed in a similar way with the roles of σ i, τ i as well as of P i, Q i interchanged.

Verification. The construction only needs queries to ∅′, so it (implicitly) defines computable functions g, h such that

Y = Φ g ( a , b ) = i , t σ i , t , and Z = Φ h ( a , b ) = i , t τ i , t .
No matter what a, b are, at least one of Y, Z is total and in P. For Z is extended at the odd stages, and Y at the even stages, both during the first substage. If we get to stage i + 1 for each i, then both Y and Z are total. Otherwise, say stage i + 1 is not terminated where i = 2 e. This makes Z total, hence ZQ i + 1P.

By the Double Recursion Theorem 1.2.16 there is a pair of fixed points a, b, and therefore

Φ g ( a , b ) = Φ a and Φ h ( a , b ) = Φ b
We claim that in this case, actually both Y and Z are total. Consider again the case where stage i + 1, i = 2e, is not terminated, whence only Z = Φ b is total. Then, since B = W τ(b), B is incomputable. By the same argument as in the proof of Theorem 1.8.39, we finish stage i + 1, contradiction.

Since all stages are terminated, AT Z and BT Y. Hence A|T B.

4.3 Strengthening the notion of a d.n.c. function

The computational complexity of a set is related in various ways to its degree of randomness (a summary will be given in Section 8.6). Here we only consider one aspect of the computational complexity: the set computes a function with a fixed point freeness condition.

(p.156) Sets of PA degree

A highness property of a set D stronger than having d.n.c. degree is obtained when one requires that there be a d.n.c. function fT D that only takes values in {0, 1}. In a typical argument involving a d.n.c. function f (such as the proof of Theorem 4.1.11) we build a partial computable α and have a reduction function p for α; when we define α (e) = 0, say, we know that f(p(e)) ≠ J(p(e)) = α(e). If f is {0, 1}-valued, we may in fact conclude that f (p (e)) = 1. Thus we may prescribe the value f (p (e)), while before we could only avoid a value. Since f = ΦD for a given Turing reduction Φ, we can indirectly restrict D.

Up to Turing degree, the {0, 1}-valued d.n.c. functions coincide with the completions of Peano arithmetic PA; see Exercise 4.3.7. This justifies the following terminology.

4.3.1 Definition. We say that a set D has PA degree if D computes a {0, 1}-valued d.n.c. function.

The set ∅′ has PA degree by Remark 1.8.30. Exercise 5.1.15 shows that the class of sets of PA degree is null, so this highness property is indeed much stronger than having d.n.c. degree. Recall from Example 1.8.32 that the {0, 1}-valued d.n.c. functions form a 1 0 class. Thus, by the basis theorems of Section 1.8, there is a set of PA degree that is low, and also a set of PA degree that is computably dominated. These examples show that a set can be computationally strong in one sense, but weak in another.

We give two properties that are equivalent to being of PA degree. Both assert that the set is computationally strong in some sense.

4.3.2 Theorem. The following are equivalent for a set D.

  1. (i) D has PA degree.

  2. (ii) For each partial computable {0, 1}-valued function ψ, there is a total function gT D that extends ψ, namely, g (x) =ψ(x) whenever ψ (x)↓. Moreover, one may choose g to be {0, 1}- valued.

  3. (iii) For each nonempty 1 0 class P, there is a set ZP such that ZT D. In other words, the sets Turing below D form a basis for the 1 0 classes.

Proof. (i)⇒(ii): Suppose fT D is a {0, 1}-valued d.n.c. function. Let p be a reduction function for ψ, that is, ∀x ψ(x) ≃ J(p(x)). Then ∀x ¬f(p(x)) = J(p(x)). So, if ψ (x) converges, then f (p (x)) = 1− ψ(x). Let gT D be the {0, 1}-valued function given by g (x) = 1− f (p (x)), then g extends ψ.

(ii)⇒(iii): Let P = ∩s Ps be an approximation of P by a descending effective sequence of clopen sets; see (1.17) on page 52. For a number x (viewed as a binary string), if s is least such that [xi] ∩ Ps = ∅ for a unique i ∈ {0, 1}, then define ψ (x) = 1− i. (If we see that the extension xi is hopeless, then ψ dictates to go the other way.) On many strings x, the function ψ makes no decision. So let g be a total extension as in (ii), and define Z recursively by Z (n) = g (Zn). Then ZT D and Z is in P.

(p.157) (iii)⇒(i): This holds because the {0, 1}-valued d.n.c. functions form a 1 0 class□.

Exercises.

4.3.3. The equivalence (i) ⇔ (ii) above fails for d.n.c. sets without the restriction that the function computed by D is {0, 1}-valued: show that the following are equivalent for a set D. (i) ∅′ ≤T D. (ii) Each partial computable function ψ can be extended to a (total) function gT D.

4.3.4. (Kučera) Show that for each low set Z there is a promptly simple set A such that ZA is low.

4.3.5.◇ (Jockusch, 1989) In Definition 4.3.1, the condition that D computes a d.n.c. function with range bounded by a constant would be sufficient: suppose that f is a d.n.c. function with bounded range. Show that there is a {0, 1}-valued d.n.c. function gT f.

The next two exercises assume familiarity with Peano arithmetic (see Kaye 1991). The sentences in the language of arithmetic L ( +, ×, 0, 1) are effectively encoded by natural numbers, using all the natural numbers. Let α n be the sentence encoded by n. Let n ˙ be the effectively given term in the language of arithmetic that describes n.

4.3.6. (Scott) Show that a set D has PA degree ⇔ there is a complete extension B of Peano arithmetic such that BT D.

4.3.7.◇ (Scott) Improve the result of previous exercise: D has PA degree ⇔ Peano arithmetic has a complete extension BT D.

Martin-Löf random sets of PA degree

The following theorem of Stephan 2006 shows that there are two types of ML-random sets: the ones that are not of PA degree and the ones that compute the halting problem. However, such a dichotomy only applies for the particular highness property of having PA degree. A ML-random set can satisfy other highness properties, such as being high, without computing ∅′ (see 6.3.14).

4.3.8 Theorem. If a ML-random set Z has PA degree then ∅′ ≤T Z.

Proof. If the proof seems hard to follow, read the easier proof of Theorem 4.3.9 first, where a similar technique is used.

Let Φ be a Turing functional such that ΦX(n) is undefined or in {0, 1} for each X, n, and ΦZ is a d.n.c. function. If ∅′ ≤T Z we build a uniformly c.e. sequence (Cd)d ∈ℕ of open sets such that λ C d≤ 2d and ZCd for infinitely many d, so Z fails this Solovay test.

We define an auxiliary {0, 1}-valued partial computable function α. By the Recursion Theorem (see Remark 4.1.12) we may assume we are given a reduction function p for α, namely, a computable strictly increasing function p such that α(e)≃J(p(e)) for each e. Since ΦZ is {0, 1}-valued, for r ∈ {0, 1}, if we define α (x) = 1 − r, we enforce that ΦZ(p (x)) = r.

Let (nd)d>0 be defined recursively by n 1 = 0 and n d + 1 = nd + d. The values of α on the interval Id = [nd, n d + 1) are used to ensure that λ C d≤ 2d. When d enters ∅′ at stage s, consider the set B of strings σ such that Φ s σ p ( n d + 1 ) converges.

(p.158) Informally we let Cd be the set of oracles Y ∈ [B] for which ΦY seems to be a {0, 1}-valued d.n.c. function on p (Id), namely, for all xId ΦY (p (x)) ≠ J (p (x)) = α (x). Now define α in such a way that λ C d is minimal. Then λ C d ≤ 2 d because there are 2d ways to define α on Id. If ∅′ ≰T Z then for infinitely many d, Φ Z p ( n d + 1 ) converges before d enters ∅′, so ZCd.

Construction of a uniformly c.e. sequence of open sets (Cd)d >0 and a partial computable function α.

Stage s. Do nothing unless a number d > 0 (unique by convention) enters ∅′ at s. In that case let B = { σ : Φ s σ p ( n d + 1 ) } . Let τ d be a string of length d such that λC d becomes minimal, where

C d = [ { σ B : i < d Φ s σ ( p ( n d + i ) ) = τ d ( i ) } ]
.

(Thus λ C d ≤ 2d. Note also that Cd is in fact clopen, but we only obtain a c.e. index for it, as we never know whether d will enter ∅′.) For i < d define α (nd + i) = 1 − τ d(i).

Verification. We show ∃ d ZCd. Let g ( d ) = μ s . Φ s Z p ( n d + 1 ) . Since ∅′ ≰T Z and gT Z, there are infinitely many d ∈ ∅′ such that d g ( d ) . If d is such a number then for each i < d, ΦZ(p(nd + i)) ≠ J(p(nd + i)) = α (nd + i) since ΦZ is d.n.c., so since ΦZ is {0, 1}-valued, ΦZ(p(nd + i)) = 1 − α (nd + i) = τ d(i). Thus ZCd.

By Proposition 3.2.30 we have ∅′ ≤wtt ΩR for each optimal prefix-free machine R. The following result of Calude and Nies 1997 shows that this cannot be improved to a truth-table reduction□.

4.3.9 Theorem. Let Φ be a truth-table reduction procedure such that ΦZ is a {0, 1}- valued d.n.c. function. Then Z is not ML-random. In particular, no ML-random set Z satisfies ∅′ ≤tt Z.

Proof. The setting is the same as in the proof of Theorem 4.3.8: we define a partial computable function α, and are given a reduction function p such that α (e) ≃ J (p (e)). The reduction Φ is total for each oracle Y, and we may also assume ΦY is {0, 1}-valued. Therefore we may for each d > 0 compute a string τ d of length d such that λCd is minimal, where

C d = [ { σ : i < d Φ σ ( p ( n d + i ) ) = τ d ( i ) } ] .
For i < d, we define α (nd + i) = 1 − τ d(i). Clearly λC d≤ 2 d. Moreover, ZCd for each d because ΦZ is {0, 1}-valued d.n.c.

Note that (Cd)d ∈ℕ is a Kurtz test (see Definition 3.5.1). Thus, in fact no weakly random set is truth-table above ∅′.

Demuth 1988 proved that if Z is ML-random and ∅ <T Ytt Z, then some Y ˜ T Y is ML-random. This also shows that there is no ML-random set Ztt∅′.

4.3.10 Exercise. There is a set A such that A and ∅′ form a minimal pair, but no weakly 2-random set Z computes A.

(p.159) Turing degrees of Martin-Löf random sets *

We consider ML-randomness in the context of Turing degree structures. Let 𝓓 denote the partial order of all Turing degrees, and let ML ⊆ 𝓓 denote the degrees of ML-random sets. We know from Theorem 3.3.2 that the degree of A ⊕ ∅′ contains a ML-random set for each A. However, ML is not closed upwards in 𝓓:

4.3.11 Proposition. For each degree c, {x: xc} ⊆ ML ⇔ c ≥ 0′.

Proof. ⇐: This follows from 3.3.2 because each degree d0′ is in ML.

⇒: Suppose that CT∅′. Let P be the 1 0 ( C ) class of {0, 1}-valued d.n.c. functions f relative to C (i.e.,∀e ¬ f(e) = J C(e)). We relativize Theorem 1.8.39 to C. Avoiding the cone above ∅′, we obtain a set YP such that YCT ∅′. Since YC has PA degree, it is not in the same Turing degree as a ML-random set, for otherwise YCT ∅′ by Theorem 4.3.8.

This yields a natural first-order definition of 0′ in the structure consisting of the partial order 𝒟 with an additional unary predicate for ML. Shore and Slaman 1999 proved that the jump operator is first-order definable in the partial order 𝒟. Their definition uses metamathematical notions and codings of copies of ℕ with first-order formulas. Even though later on, Shore 2007 found a proof that does not rely on metamathematics, we still do not know a natural first-order definition of the jump operator (or even of 0′) in 𝒟.

Next, we study ML within 𝒟T (≤0′), the Turing degrees of Δ 2 0 sets. By Exercise 4.2.7, there is an incomputable c.e. set Turing below any pair of ML-random Δ 2 0 sets. So no pair of degrees in ML ∩ 𝒟T (≤0′) has infimum 0.

4.3.12 Proposition. ML ∩ 𝒟T (≤0′) is not closed upwards in 𝒟T (≤0′) Also, ML ∩ L is not closed upwards in L, the set of low degrees.

Proof. The {0, 1}-valued d.n.c. functions form a 1 0 class, which has a low member D by Theorem 1.8.37. Then the degree of D is not in ML by 4.3.8. On the other hand, by Theorem 4.3.2(iii) there is a ML-random set ZT D.

4.3.13 Remark. Kučera 1988 proved that there is a minimal pair of sets of PA degree. In fact,

0 = inf { a b : a,b PA degrees & a b = 0 } .
Thus there also is a natural first-order definition of 0′ in the structure consisting of the partial order 𝒟 with an additional unary predicate for being a PA degree. To show that ABT∅′ for each minimal pair A, B of sets of PA degree, one builds a nonempty 1 0 class P without computable members such that XYT∅′ whenever X, YP and X Y. Since there are X, YP such that XT A and YT B, this implies ABT∅′. To obtain P, take a c.e. set ST∅′ such that ℕ − S is introreducible. Say, S is the set of deficiency stages for a computable enumeration of ∅′ (see the comment after Proposition 1.7.6). Let S = UV be a splitting of S into computably inseparable sets (Soare 1987, (p.160) Thm. X.2.1) and let P={Z: UZ & VZ=∅}. If X, Y are as above, then XY is an infinite subset of ℕ − S, so that ∅′ ≤T XY.

Next, one shows that each Σ 2 0 set C >T∅′ bounds a minimal pair A, B of PA sets by a technique similar to the one in the solution to Exercise 1.8.46. Now let C 0, C 1 >T∅′ be a minimal pair of Σ 2 0 sets relative to ∅′, and let Ai BiT Ci be minimal pairs of sets of PA degree for i ∈ {0, 1}. Then 0′=(a0∨b0)∧(a1∨b1).

Relating n-randomness and higher fixed point freeness

Definition 4.0.1 can be relativized: a function f is d.n.c. relative to C if f (e) ≠ J C(e) for any e such that J (e)↓. For n ≥ 1, we say that f is n-d.n.c. if f is d.n.c. relative to ∅ (n−1). For example, if n > 0 then ∅(n) computes a {0, 1}-valued n- d.n.c. function, by relativizing Remark 1.8.30 to ∅(n −1).

By Proposition 4.1.2 relativized to ∅(n −1), each n-random set computes an n- d.n.c. function. Thus, for this particular aspect of the computational complexity, a higher degree of randomness implies being more complex. The result is not very satisfying yet because we would prefer highness properties that are not obtained by mere relativization of a highness property to ∅(n −1). For this reason we introduce the hierarchy of n-fixed point free functions. It turns out to coincide up to Turing degree with the hierarchy of n-d.n.c. functions. For sets A, B, let A1 B if A = B and A2 B if A = B. For n ≥ 3, let An B if A (n −3)T B (n −3).

4.3.14 Definition. Let n ≥ 1. We say that a function g is n-fixed point free (n-f.p.f. for short) if W g(x)n Wx for each x.

For instance, let gT ∅″ be a function such that W g (x) = ∅ if Wx is infinite and W g (x) = ℕ otherwise, then g is 2-f.p.f. (By Exercise 4.1.7 in relativized form and a slight modification of Exercise 4.1.8, these properties are independent of the particular choice of jump operator or universal uniformly c.e. sequence, as far as the Turing degree of the function is concerned. In Kučera's notation the hierarchies begin at level 0, but here we prefer notational consistency with the hierarchy of n-randomness for n ≥ 1.)

We will need the Jump Theorem of Sacks (1963c). It states that from a 2 0 set S one may effectively obtain a 1 0 set A such that A′ ≡T S ⊕∅(m). (In fact one can also achieve that CT A for a given incomputable Δ 2 0 set C.) For a proof see Soare (1987, VIII.3.1). In fact we need a version of the theorem for the m-th jump.

4.3.15 Theorem. Let m ≥ 0. From a m + 1 0 set S one may effectively obtain a 1 0 set A such that A (m)T S ⊕∅ (m).

Proof. The case m = 0 is trivial, and the case m = 1 is the Jump Theorem itself. For the inductive step, suppose that m ≥ 1 and S is m + 1 0 . Then S is a m 0 ( ) set. By the result for m relative to ∅, using ࢝ we may obtain a 1 0 ( ) set B such that (B ⊕∅′)(m)T S ⊕∅ (m + 1). Then by the Limit Lemma we may in fact effectively obtain a 2 0 index for B. By the Jump Theorem, we (p.161) may effectively obtain a c.e. set A such that A′ ≡T B ⊕∅′, and hence A (m + 1)T S ⊕∅(m + 1).

The main result of this subsection is due to Kučera.

4.3.16 Theorem. Let n ≥ 1. Each n-d.n.c. function computes an n-f.p.f. function, and vice versa.

Proof. The case n = 1 is covered by the proof of Proposition 4.1.4, so we may assume that n ≥ 2. For each set E ⊆ ℕ and each i ∈ ℕ, let

( E ) i = { n : < n , i > E }
.

1. If an n-d.n.c. function f is given, we define an n-f.p.f. function gT f.

Case n = 2. Since the index set {e: We is finite} is c.e. relative to ∅′, there is a Turing functional Φ such that, for each input x, Φ ( x ) is the first i in an enumeration relative to ∅′ such that (Wx)i is finite if there is such an i, and Φ ( x ) is undefined otherwise. Let p be a reduction function (Fact 1.2.15) such that Φ ( x ) J ( p ( x ) ) for each x, and let gT f be a function such that W g (x) = {<y, j>: jf (p(x))}. If Φ ( x ) is undefined then (Wx )i is infinite for each i while (W g(x))f (p (x)) = ∅, so W g (x) = Wx. If Φ ( x ) = i then (W g (x) i)= ℕ since f (p (x)) ≠ i, so again W g (x) Wx

Case n = 3. We modify the foregoing proof. For each set B and each i ∈ ℕ, let [B]i = {< n, j > ∈ B: ji}. By the finite injury methods of Theorems 1.6.4 and 1.6.8, there is a low c.e. set B such that (B)iT [B]i for each i. Since B is low, the relation {<x, i>: WxT [B]i} is 3 0 (see Exercise 1.5.7, which is uniform), so there is a Turing functional Φ as follows: on input x, Φ∅″(x) is the first i in an enumeration relative to ∅″ such that WxT [B]i if there is such an i, and Φ∅″ (x) is undefined otherwise. Let p be a reduction function such that Φ∅″J ∅′(p(x)) for each x, and let gT f be a function such that W g(x) = [B]f (p (x)). If Φ∅″(x) is undefined then WxT [B]i for each i and hence WxT W g(x). If Φ∅″ (x) = i then WxT [B]i. Since f (p (x)) ≠ i we have (B)iT W g (x), and hence W g (x)T Wx because (B)iT [B]i.

Case n ≥ 4. Let m = n − 3 and R = ∅(m). We run a finite injury construction of the kind mentioned in the foregoing proof relative to R, and code R into each (B)i. In this way we obtain a set B that is c.e. in R such that B′ ≡T R′, RT (B)i and (B)iT [B]i for each i.

There is a computable function h such that W x ( m ) = W h ( x ) R , so the relation { < x , i > : W x ( m ) T [ B ] i } . Since B′ ≡T R′, there is a Turing functional Φ as follows: on input x, ΦR(x) is the first i in an enumeration relative to R″ such that W x ( m ) T [ B ] i if there is such an i, and ΦR(x) is undefined otherwise. Let p be a reduction function such that ΦR(x) ≃ J R (p (x)) for each x, and let g ˜ T f be like g before, namely W g ˜ ( x ) R = [ B ] f ( p ( x ) ) . As before one shows that W g ˜ ( x ) R T W x ( m ) for each x. Now, by the uniformity of Theorem 4.3.15, (p.162) there is a function g T g ˜ such that ( W g ( x ) ) ( m ) T W g ˜ ( x ) R R for each x. Since R T W g ˜ ( x ) R , this implies that W g ( x ) ( m ) T W x ( m ) for each x. (This proof actually works for n = 3 as well, in which case we re-obtain the previous one.)

2. If an n-f.p.f. function g is given, we define an n-d.n.c. function fT g. We use a result of Jockusch, Lerman, Soare and Solovay 1989 which can also be found in Soare (1987, pg. 273): if ψ is partial computable relative to ∅(n −1) then there is a (total) computable function r such that W ψ(x)n W r (x) whenever ψ(x) is defined. (Say, if n = 2, fix a Turing functional Φ such that ψ = Φ∅′, and let ψ s (x) ≃ Φ∅′(x)[s]. As long as e = ψ s (x), W r (x) follows the enumeration of We.)

Now let ψ = J ( n 1 ) . If ψ (x) ↓ then

W ψ ( x ) ~ n W r ( x ) n W g ( r ( x ) ) , so ψ ( x ) g ( r ( x ) )
.

Hence f = gr is n-d.n.c. and fT g□.

As a consequence we obtain the following result of Kučera 1990.

4.3.17 Corollary. If Z is n-random then there is an n-f.p.f. function gT Z.

Proof. By Proposition 4.1.2 relative to ∅(n −1), a finite variant f of the function λn.Zn is n-d.n.c. There is an n-f.p.f. function gT f□.

The converse fails because the n-random degrees are not closed upwards. For n = 1 this follows from Proposition 4.3.11, and for n ≥ 2 it follows because each 2-random set forms a minimal pair with ∅′. Also note that for each n > 1 there is an (n − 1)-random set ZT(n −1). Then Z does not compute an n-f.p.f. function.

Our proof of Corollary 4.3.17 is somewhat indirect as it relies on Schnorr's Theorem 3.2.9 relative to ∅(n −1). The proofs in Kučera 1990 are more self-contained (but also longer). The ideas needed in the proof of Theorem 4.3.16 were introduced there. For instance, Kučera's proof of (1.) in the case n = 2 is as follows. Given x ∈ ℕ, using the infinite set Z as an oracle, we may compute nx = μn. # Z ∩ [0, n) = x. Let gT Z be a function such that, for each x, W g (x) = {<y, i>: i < nxiZ}. We will show that Wx W g (x) for almost all x, which is sufficient to establish the theorem.

Since the index set {e: We is finite} is 2 0 , there is a computable function h such that W h ( x ) = { i : ( W x ) i is finite } . We define a ML-test (Gx)x ∈ℕ relative to ∅′, as follows. On input x, initially let Gx = ∅. For x > 0, once distinct elements a 0, …, a x−1 have been enumerated into W h ( x ) , let Gx = {Y: ∀i < x [Y (ai) = 1}. Clearly Gx is 1 0 ( ) uniformly in x, and λG x ≤ 2 x. Then, since Z is 2-random and (Gx)x ∈ℕ is a Solovay test relative to ∅′, there is x 0 such that ZGx for all xx 0. Because # Z ∩ [0, nx) = x,

x x 0 W h ( x ) Z [ 0 , n x )
.

Assume for a contradiction that xx 0 and W g (x) = Wx. Then (W g(x))i = (Wx)i for all i. If inx this implies that i W h ( x ) . If i < nx then

i Z ( W g ( x ) ) i = ( W x ) i is finite i W h ( x ) .
Thus W h (x) = [0, nx) ∩ Z, a contradiction.

4.3.18 Exercise. Show that there is a weakly 2-random set that does not compute a 2-f.p.f. function. Hint. Use Exercise 1.8.46.