Some Questions in Computable Mathematics

Abstract

In honor of Rod Downey’s 60th birthday, this paper discusses a few open problems connected in one way or another with him.

To Rod Downey on his 60th Birthday.

Partially supported by a Collaboration Grant for Mathematicians from the Simons Foundation. I thank Russell Miller, Benoit Monin, and Ludovic Patey for useful comments.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

I had the good fortune to be among Rod Downey’s long and distinguished list of postdocs, in my case in 1999–2000. I recall Rod saying once that he had hoped that his young postdocs would be interested in joining him in his many athletic activities, but ended up with a bunch of drunks instead. I did learn a lot about wine from Rod, but I think I managed to squeeze some learning about mathematics as well while I was in Wellington. In any case, to the extent that I was able to hold my own with Rod at the blackboard and around the decanter, I am proud.

There is no denying that Rod is a theory-builder, parameterized complexity being a shining example, but he is also a problem-solver, problem-creator, and problem-disseminator of the first water. So in honor of his 60th birthday, I have chosen to discuss a few open problems I particularly like, and that are connected in one way or another with his work and my mathematical interactions with him. Most of these problems are well-known to experts in their areas (computable structure theory, reverse mathematics, algorithmic randomness, and asymptotic computability), but I hope there is some value in bringing them together, with some background and a bit of personal history thrown in.

I will assume familiarity with the basics of computability theory throughout, as well as those of reverse mathematics, algorithmic randomness, and model theory in places.

1 The Slaman-Wehner Theorem for Linear Orders

My dissertation was in computable structure theory. Rod’s research in that area was deeply influential, as was his expository work in papers such as [14,15,16, 30]. Russell Miller was working on his dissertation at around the same time as I, and I believe it was Rod who first told me about an exciting result by Russell that answered a couple of questions Rod had asked in [14], while leaving a third tantalizingly open.

In model theory, one identifies isomorphic structures, but in computable mathematics, structures that are isomorphic but not computably isomorphic can be quite different from each other. Thus one of the main concerns of computable structure theory is the study of concrete copies of a countable structure (in a computable language) up to computable isomorphism.

Definition 1.1

A presentation of a countably infinite structure $\mathcal M$ is a structure $\mathcal A \cong \mathcal M$ with universe $\omega$. A structure is computably presentable if it has a presentation whose atomic diagram is computable. More generally, the degree of a presentation $\mathcal A$ is the (Turing) degree of the atomic diagram of $\mathcal A$. The (atomic) degree spectrum of $\mathcal M$ is the set of degrees of presentations of $\mathcal M$.

The degree spectrum of $\mathcal M$ measures the computability-theoretic complexity of obtaining a concrete copy of $\mathcal M$. Knight [67] showed that, except in trivial situations in which the degree spectrum is a singleton, every degree spectrum is closed upwards. Thus nontrivial computably presentable structures all have the same degree spectrum.

The simplest degree spectra are those of the form $\{\mathbf{d}: \mathbf{d} \geqslant \mathbf{a}\}$, and for any degree $\mathbf{a}$, it is not difficult to find a structure $\mathcal M$ with this degree spectrum. In this case, it makes sense to say that $\mathbf{a}$ is the degree of (the isomorphism class of) $\mathcal M$, but not every degree spectrum has this form. For instance, Richter [99] showed that if a linear order is not computably presentable, then its degree spectrum has no least element.

On the other hand, not all upwards-closed sets of degrees are degree spectra of structures. For instance, if $\mathbf{a}$ and $\mathbf{b}$ are incomparable degrees, then the union of the upper cones $\{\mathbf{d}: \mathbf{d} \geqslant \mathbf{a}\}$ and $\{\mathbf{d}: \mathbf{d} \geqslant \mathbf{b}\}$ is not the degree spectrum of any structure, a fact established in unpublished work of Knight and others [personal communication] and by Soskov [110]. Thus it becomes interesting to ask whether certain natural upwards-closed classes of degrees can be degree spectra of structures. (For a broader survey of this general question, see the chapter on computable model theory by Fokina, Harizanov, and Melnikov [35] in a volume dedicated to Turing’s legacy edited by Rod.)

One can think of the set of presentations of a countable structure as a mass problem (i.e., a subset of $\omega ^\omega$) via some suitable encoding. One way to compare the relative complexity of two mass problems is via Muchnik reducibility, also known as weak reducibility. (Medvedev reducibility, or strong reducibility, is the uniform version of Muchnik reducibility.) For two mass problems P and Q, say that P is Muchnik reducible to Q if every element of Q computes some element of P. As usual, this notion leads to a degree structure on mass problems. The least Muchnik degree consists of those mass problems that have a computable member. There is also a least nontrivial Muchnik degree, namely the degree of all mass problems P such that P has no computable member, but has an X-computable member for each noncomputable X. It might seem at first that it would be difficult to find “natural” mass problems living in this degree, but that has turned out not to be the case.

Lempp (see [108, 117]) asked whether there are structures whose degree spectra are in this degree (and Knight (see [108, 117]) asked a closely related question about enumerations of families of sets). A positive answer was given by Slaman [108] and Wehner [117].

Theorem 1.2

(Slaman [108]; Wehner [117]). There is a structure whose degree spectrum consists of all nonzero degrees.

Whenever a structure with a particularly interesting computability-theoretic feature is found, it is natural to ask whether similar structures exist within various well-known classes of structures. For some classes $\mathcal C$, there are general results that show that, for certain kinds of computability-theoretic phenomena, anything that can happen in general can happen within $\mathcal C$. For instance, Hirschfeldt, Khoussainov, Shore, and Slinko [52] gave such results for classes such as partial orders, lattices, integral domains, commutative semigroups, and 2-step nilpotent groups, which in particular imply that the Slaman-Wehner Theorem holds in these classes. That is, each of these classes contains a structure whose degree spectrum consists of all nonzero degrees. (See also the discussion of Miller, Poonen, Schoutens, and Shlapentokh [90] in Sect. 4.)

On the other hand, there are many classes that are not “universal” in the above sense, and in particular do not contain structures realizing all the degree spectra that are possible in general. A well-known example is the class of Boolean algebras. Downey and Jockusch [23] showed that every low Boolean algebra is isomorphic to a computable one, and this result was extended to low$_2$ Boolean algebras by Thurber [114] and then to low$_4$ Boolean algebras by Knight and Stob [68]. Thus if the degree spectrum of a Boolean algebra contains any low$_4$ degree, then it contains all degrees. In particular, there is no Boolean algebra whose degree spectrum consists of all nonzero degrees. It is not known whether every low$_n$ Boolean algebra is isomorphic to a computable one. This question, which goes back to Downey and Jockusch [23], remains a major one in computable structure theory.

Richter’s result mentioned above shows that the class of linear orders is also not universal as far as degree spectra are concerned. On the other hand, unlike Boolean algebras, linear orders can have presentations that are close to being computable without actually being computably presentable. Jockusch and Soare [61] showed that for every nonzero c.e. degree, there is a linear order of that degree that is not isomorphic to any computable linear order. Downey and independently Seetapun (see [14]) extended this result to all nonzero $\Delta ^0_2$ degrees, and finally Knight (see [14]) extended it to all nonzero degrees.

In many ways, linear orders occupy a particularly interesting place in computable structure theory. They are neither so unstructured as to basically be the general case in disguise nor so structured as not to admit any computability-theoretic “pathologies”. When I was in Wellington, Rod and I spent some time thinking about linear orders (and in particular a question about the successivity relation in computable linear orders that Rod finally solved in joint work with Lempp and Wu [29]). As I remember Rod saying several times back then, “Linear orders are hard!”

In light of the results discussed above, it was natural for Rod to ask in [14] whether there are linear orders that are not computably presentable but whose degree spectra contain all nonzero c.e. degrees, or all nonzero $\Delta ^0_2$ degrees, or even all nonzero degrees. The first two of these questions were the ones answered by Russell’s result.

Theorem 1.3

(Miller [87, 88]). There is a linear order whose degree spectrum contains every nonzero $\Delta ^0_2$ degree except $\mathbf{0}$.

The proof consists of modifying the basic module of the Jockusch-Soare construction in [61] and combining it with $\Delta ^0_2$-permitting so that, for any noncomputable $\Delta ^0_2$ set C, the construction produces a C-computable linear order whose order type is independent of C. The resulting order type $\mathcal L$ is of the form $\mathcal S_0 + \mathcal A_0 + \mathcal S_1 + \mathcal A_1 + \cdots$, where each $\mathcal A_n$ is used to diagonalize against the possibility that the nth partial computable linear order is isomorphic to $\mathcal L$, and each $\mathcal S_n$ is a separator of the form $1+\eta +i+\eta +1$, where $\eta$ is the order type of the rationals and $i \in \mathbb N$. The separators keep the individual diagonalization constructions apart.

Chisholm [unpublished] and Downey [unpublished] showed that the degree spectrum of $\mathcal L$ in fact includes all hyperimmune degrees. Barmpalias (see [36]) argued that no hyperimmune-free degree is sufficiently strong to carry out the basic module of the construction of $\mathcal L$, leading to the conjecture that the degree spectrum of $\mathcal L$ consists exactly of the hyperimmune degrees. Of course, even if this conjecture holds, it may still be possible to go beyond the hyperimmune degrees with a different order type, so Rod’s third question remains open.

Open Question 1.4

(Downey [14]). Is there a linear order whose degree spectrum consists of all nonzero degrees?

See Frolov, Harizanov, Kalimullin, Kudinov, and Miller [36] for more on degree spectra of linear orders. In particular, they showed that for every $n \geqslant 2$, there is a linear order whose degree spectrum consists exactly of the nonlow$_n$ degrees. The $n=1$ remains open, however. (Notice that Question 1.4 is the $n=0$ case.)

Open Question 1.5

(Frolov, Harizanov, Kalimullin, Kudinov, and Miller [36]). Is there a linear order whose degree spectrum consists of the nonlow degrees?

As noted by Fokina, Harizanov, and Melnikov [35], analogs of Question 1.4 are also open for other interesting classes of structures, such as abelian groups. In that case, Khoussainov, Kalimullin, and Melnikov [65] proved the analog of Theorem 1.3 (and its extension to hyperimmune degrees), while Melnikov [78] gave a positive answer to the analog of Question 1.5.

Noah Schweber [103] has suggested an approach to giving a positive answer to Question 1.4, which goes through another set of results related to the Slaman-Wehner Theorem.

An alternative measure of the complexity of a structure can be obtained by looking at its full elementary diagram rather than just its atomic diagram.

Definition 1.6

A (presentation of a) structure is decidable if its elementary diagram is computable. The elementary degree spectrum of $\mathcal M$ is the set of degrees of elementary diagrams of presentations of $\mathcal M$.

It is easy to see that the usual Henkin proof of the completeness theorem can be effectivized to show that every complete decidable theory has a decidable model, but things are often different if one wants this model to have certain special properties. For instance, every atomic theory in a countable language has a countable atomic model, but this result does not hold effectively. (Recall that a theory T is atomic if every formula consistent with T is contained in a principal type, and a model is atomic if every type realized in it is principal.) To make this statement more precise and cast it in a form that will be more relevant to Question 1.4, consider the following definition.

A binary tree is a set $\mathcal T$ of finite binary strings such that if $\sigma \in \mathcal T$ and $\tau \prec \sigma$ then $\tau \in \mathcal T$. A string $\sigma \in \mathcal T$ is a dead end if $\sigma 0,\sigma 1 \notin \mathcal T$. A path on $\mathcal T$ is an infinite binary sequence P such that every finite initial segment of P is in $\mathcal T$.

Definition 1.7

A PAC tree is a computable binary tree with no dead ends, each of whose paths is computable.

The motivation behind this definition is that PAC trees are essentially the trees of types of complete decidable theories all of whose types are computable. (See [43, 46] for more details.) Such a theory has only countably many types, and hence is atomic. Goncharov and Nurtazin [42] and Harrington [44] showed that a complete decidable theory T has a decidable atomic model if and only if there is a computable listing of the principal types of T. Millar [85] showed that another sufficient condition for a complete decidable theory T to have a decidable atomic model is that there be a computable listing of all types of T. Thus, in a sense, the simplest possible complete decidable theory with no decidable atomic model would be one such that each type is individually computable, but there is no way to uniformly compute all the types, or even all the principal types. Since isolated paths correspond to principal types, the following result has as a corollary that there exists such a theory. (For more on the computability-theoretic and proof-theoretic aspects of the existence of atomic models, see [47, Sect. 9.3] and the references mentioned there. See also Cholak and McCoy [6] in connection with Open Question 9.47 in that book.)

Theorem 1.8

(Goncharov and Nurtazin [42]; Millar [84]). There is a PAC tree whose isolated paths cannot be computably listed.

Thus the Muchnik degree of the set of listings of the isolated paths of a PAC tree is not always trivial. However, there is only one other possibility for what this degree can be.

Theorem 1.9

(Hirschfeldt [46]). Let $\mathcal T$ be a PAC tree and let . Then the isolated paths on $\mathcal T$ can be X-computably listed.

Combining this result with Theorem 1.8 shows that there is a PAC tree $\mathcal T$ such that the isolated paths on $\mathcal T$ can be X-computably listed if and only if X is not computable. Restated in model-theoretic terms, Theorem 1.9 says that if T is a complete decidable theory all of whose types are computable, then the elementary degree spectrum of the atomic model of T includes all nonzero degrees. This result extends an earlier one of Csima [11, 12], who showed that such a spectrum includes all nonzero $\Delta ^0_2$ degrees.

The translation of trees into theories can be done in such a way that the atomic model of the theory obtained from the PAC tree in Theorem 1.8 not only has no decidable presentation, but does not even have a computable presentation. Thus we have the following fact, which extends the Slaman-Wehner theorem to models of decidable theories.

Corollary 1.10

(Hirschfeldt [46]). There is a structure $\mathcal M$ whose atomic and elementary degree spectra both consist of the nonzero degrees. Furthermore, $\mathcal M$ can be chosen to be the atomic model of a complete decidable theory each of whose types is computable.

Let us now return to Question 1.4. For a tree $\mathcal T$, let $\mathcal L(\mathcal T)$ be the linear order consisting of the isolated paths on $\mathcal T$ with the lexicographic order. Schweber [103] observed that if I is a listing of the isolated paths on $\mathcal T$, then $\mathcal L(\mathcal T)$ has an I-computable presentation, and hence, if $\mathcal T$ is a PAC tree, then the degree spectrum of $\mathcal L(\mathcal T)$ contains all nonzero degrees. Thus a positive answer to the following question would imply a positive answer to Question 1.4.

Open Question 1.11

(Schweber [103]). Is there a PAC tree $\mathcal T$ for which $\mathcal L(\mathcal T)$ has no computable presentation?

Schweber [103] did show that there is no computable way to pass from an index for a PAC tree $\mathcal T$ to one for a computable presentation of $\mathcal L(\mathcal T)$. Nevertheless, both he and I strongly believe that the answer to this question is negative. The linear orders $\mathcal L(\mathcal T)$ arising from PAC trees $\mathcal T$ do not seem sufficiently complex to permit diagonalization against computable presentations. In particular, each such ordering is scattered, i.e., does not contain a suborder of type $\eta$, and hence cannot contain Jockusch-Soare-style separators. Indeed, it seems quite reasonable to conjecture that no scattered linear order can have degree spectrum consisting exactly of the noncomputable degrees, although this has not been shown to be the case.

Incidentally, the following question is also open.

Open Question 1.12

(Schweber [103]). Is every computable scattered linear order isomorphic to $\mathcal L(\mathcal T)$ for some PAC tree $\mathcal T$?

But perhaps a little more life can be injected into this approach by considering more complicated trees. For a tree $\mathcal T$ and $\sigma \in \mathcal T$, let $\mathcal T_\sigma$ be the tree consisting of all $\tau$ such that $\sigma \tau \in \mathcal T$. Let $[\mathcal T]$ be the set of paths on $\mathcal T$.

Definition 1.13

A quasi-PAC tree is a computable binary tree $\mathcal T$ with no dead ends such that for each noncomputable path P of $\mathcal T$, there is a $\sigma \prec P$ for which $[\mathcal T_\sigma ]$ is perfect (i.e., has no isolated elements).

For a quasi-PAC tree $\mathcal T$, let $S(\mathcal T)$ be the set of all $\sigma \in T$ such that $[\mathcal T_\sigma ]$ is either a singleton or perfect. Let $M(\mathcal T)$ be the set of minimal elements of $S(\mathcal T)$ (i.e., nodes $\sigma \in S(\mathcal T)$ such that if $\tau \prec \sigma$ then $\tau \notin S(\mathcal T)$). Let $\mathcal L(\mathcal T)$ be the linear order obtained by first ordering $M(\mathcal T)$ lexicographically, then replacing each $\sigma \in M(\mathcal T)$ such that $[T_\sigma ]$ is perfect by a copy of the rationals. (If $\mathcal T$ is a PAC tree, then this definition agrees with the previous definition of $\mathcal L(\mathcal T)$ up to isomorphism.) Notice that, unlike in the case of PAC trees, this linear order is not necessarily scattered, and indeed can include Jockusch-Soare-style separators.

Proposition 1.14

Let $\mathcal T$ be a quasi-PAC tree. Then the degree spectrum of $\mathcal L(\mathcal T)$ contains all nonzero degrees.

Proof

Let . The idea is to first build an X-computable collection of paths on $\mathcal T$ using the same method as in the proof of Theorem 1.9 above given in [46], then use it to build an X-computable presentation of $\mathcal L(\mathcal T)$.

Let $\sigma _0,\sigma _1,\ldots$ list the nodes of $\mathcal T$, say in length-lexicographic order. For each n, let $f_n$ be the path on $\mathcal T$ defined as follows. Begin at $\sigma _n$, and proceed along $\mathcal T$ until there is a split in $\mathcal T$, i.e., a $\tau \succcurlyeq \sigma _n$ such that $\tau 0$ and $\tau 1$ are both in $\mathcal T$. (Of course, such a split might never be found.) Take the right node of this split if $0 \in X$, and take the left node if $0 \notin X$. Then continue along $\mathcal T$ until there is another split (if ever). Then take the right node of this split if $1 \in X$, and take the left node if $1 \notin X$. Continue in this way, deciding which side of splits to follow depending on successive bits of X.

Now $f_0,f_1,\ldots$ are uniformly X-computable paths on $\mathcal T$, and include all the isolated paths on $\mathcal T$. Let $S=\{n : \forall m<n\, (f_n \ne f_m)\}$. Then S is c.e. Let $n_0,n_1,\ldots$ be an enumeration of S and let $g_i=f_{n_i}$. Then the $g_i$ are uniformly X-computable and list the same paths as the $f_i$, but without repetitions. Let $\mathcal L$ be the X-computable linear order with domain $\omega$ defined by letting $i <_{\mathcal L} j$ if $g_i$ is to the left of $g_j$.

The claim now is that $\mathcal L$ is a presentation of $\mathcal L(\mathcal T)$. Let $M(\mathcal T)$ be as above (i.e., the minimal elements of the set of $\sigma \in T$ such that $[\mathcal T_\sigma ]$ is either a singleton or perfect). If $g_n$ is not isolated then infinitely many splits are encountered in its definition. Which direction $g_n$ takes at each split is determined by successive bits of X, so in this case X can be computed from $g_n$. Thus every $g_n$ is isolated or noncomputable. So, by the definition of quasi-PAC tree, every $g_n$ extends some element of $M(\mathcal T)$. Of course, it is also the case that for every $\sigma \in M(\mathcal T)$, there is a $g_n$ extending $\sigma$, which is unique if $\mathcal T_\sigma$ has only one path. Thus it is enough to show that if $[\mathcal T_\sigma ]$ is perfect, then the set of $g_n$ extending $\sigma$ has the order type of the rationals under the lexicographic order.

Suppose that $g_m$ and $g_n$ both extend such a $\sigma$, for $m \ne n$. Since $g_m \ne g_n$, assume without loss of generality that there is a $\tau \succcurlyeq \sigma$ such that $\tau 0 \prec g_m$ and $\tau 1 \prec g_n$. Since $g_m$ is not isolated, it is not computable, and hence cannot be the rightmost path on $\mathcal T$ extending $\tau 0$ (since $\mathcal T$ has no dead ends, and hence this rightmost path is computable). Thus there is a $\rho \succ \tau 0$ that is to the right of $g_m$. This $\rho$ is to the left of $g_n$, and there must be some $g_k$ extending $\rho$. Now $g_k$ is strictly in between $g_m$ and $g_n$. Similar arguments show that there cannot be a leftmost or a rightmost $g_n$ extending $\sigma$.    $\square$

Thus, as in the case of Question 1.11, a positive answer to the following question would imply a positive answer to Question 1.4.

Open Question 1.15

(Hirschfeldt (see Schweber [103])). Is there a quasi-PAC tree $\mathcal T$ for which $\mathcal L(\mathcal T)$ has no computable presentation?

Some time spent trying to give a positive answer to this question has made me lean toward believing that the answer is actually negative, but with less confidence than in the case of Question 1.11.

2 Linearizing Partial Orders

There are several other intriguing questions involving linear orders. In this section, and the next, I will briefly describe a couple of my favorite ones.

After finishing my dissertation and before going to New Zealand as Rod’s postdoc, I spent a month with him visiting Steffen Lempp and Reed Solomon at Wisconsin. The four of us sat in Steffen’s office for hours on end, day after day. Not exactly Rod’s favorite mode of working, but productive in the event, as it yielded three papers. One of these took a reverse-mathematical look at linear extensions of partial orders.

Szpilrajn [112] showed that every partial order $(X,\leqslant _{\mathcal P})$ has a linear extension, that is, a linear order $(X,\leqslant _{\mathcal L})$ such that if $a \leqslant _{\mathcal P} b$ then $a \leqslant _{\mathcal L} b$. It is natural to ask which properties of a partial order can be preserved by some linear extension. For instance, if a partial order is well-founded, does it have a well-ordered linear extension? This and similar questions can be stated concisely using the following notation.

Definition 2.1

Let $\tau$ be a linear order type. Say that $\tau$ is extendible if every partial order with no suborder of type $\tau$ has a linear extension with no suborder of type $\tau$. Say that $\tau$ is weakly extendible if every countable partial order with no suborder of type $\tau$ has a linear extension with no suborder of type $\tau$.

Characterizations of the extendible and weakly extendible countable order types were obtained by Bonnet [4] and Jullien [62], respectively. For the purposes of reverse-mathematical and computability-theoretic analysis, weak extendibility is the natural notion to study.

Definition 2.2

Let EXT$(\tau )$ be the statement that $\tau$ is weakly extendible.

EXT$(\omega ^*)$, for example, is the statement that every countable well-founded partial order has a well-ordered linear extension, which is indeed true. Downey, Hirschfeldt, Lempp, and Solomon [20] studied the weak extendibility of $\omega ^*$, $\eta$ (which recall is the order type of the rationals), and $\zeta$ (the order type of the integers). Only in the last case did we obtain a full reverse-mathematical characterization, though. (For definitions of RCA$_0$, ATR$_0$, and other systems mentioned here, see Simpson [107].)

Theorem 2.3

(Downey, Hirschfeldt, Lempp, and Solomon [20]). The principle ${{\mathrm{EXT}}}(\zeta )$ is equivalent to ATR$_0$ over RCA$_0$.

For EXT$(\omega ^*)$ (i.e., the principle that every countable well-founded partial order has a well-ordered linearization), we were able to find the following bounds.

Theorem 2.4

(Downey, Hirschfeldt, Lempp, and Solomon [20]). The principle ${{\mathrm{EXT}}}(\omega ^*)$ is provable in $\text {ACA}_0$, and is strictly stronger than $\text {WKL}_0$ over $\text {RCA}_0$.

The following questions remain open, however. Ramsey’s Theorem for pairs (RT$^2_2$) and some related principles will be discussed further below.

Open Question 2.5

(Downey, Hirschfeldt, Lempp, and Solomon [20]; Hirschfeldt [47]). Does $\mathrm{RCA}_0 + {{\mathrm{EXT}}}(\omega ^*) \vdash \mathrm{ACA}_0$? What is the relationship between ${{\mathrm{EXT}}}(\omega ^*)$ and $\mathrm{RT}^2_2$ (and related principles)?

Another way to state ${{\mathrm{EXT}}}(\eta )$ is that every scattered partial order has a scattered linear extension. Becker (see [20]) showed that $\Pi ^1_1\text {-CA}_0 \vdash {{\mathrm{EXT}}}(\eta )$. As part of his analysis of the reverse-mathematical strength of Julien’s classification of the weakly extendible order types, Montalbán [94] improved this result by showing that $\text {ATR}_0 + \text {I}\Sigma ^1_1 \vdash {{\mathrm{EXT}}}(\eta )$. Conversely, Joe Miller [unpublished] showed that ${{\mathrm{EXT}}}(\eta )$ implies WKL$_0$ over RCA$_0$, and implies ATR$_0$ over $\Sigma ^1_1\text {-AC}_0$. The exact strength of ${{\mathrm{EXT}}}(\eta )$ is still unknown, and in particular, the following question is open.

Open Question 2.6

(Montalbán [94]). What is the exact relationship between ATR$_0$ and ${{\mathrm{EXT}}}(\eta )$ over RCA$_0$?

For some further discussion of this and related questions, see [47, Sects. 10.2 and 10.3].

3 The Dushnik-Miller Theorem and Computability Theory

The paper by Downey, Lempp, and Wu [29] mentioned in Sect. 1 introduced a new method for constructing $\Delta ^0_3$ isomorphisms, which was also used by Downey, Kastermans, and Lempp [27] to give a partial answer to the longstanding Effective Dushnik-Miller Conjecture of Downey and Moses (see [15]).

A nontrivial self-embedding of a linear order $\mathcal L$ is an order preserving map from $\mathcal L$ into itself that is not the identity. The Dushnik-Miller Theorem [31] states that every infinite linear order has a nontrivial self-embedding. This theorem does not hold effectively, even for the simplest order type of infinite linear orders: Hay and Rosenstein (see [100]) showed that there is a computable linear order of order type $\omega$ with no computable nontrivial self-embeddings, and Downey and Lempp [28] improved this result by building a computable linear order $\mathcal L$ of order type $\omega$ such that any nontrivial self-embedding of $\mathcal L$ computes $\emptyset '$. They also showed that the latter construction can be turned into a proof that the Dushnik-Miller Theorem is equivalent to ACA$_0$ over RCA$_0$. (See Downey, Jockusch, and Miller [25] for a clarification of that proof.)

Downey, Jockusch, and Miller [25] showed that every computable infinite linear order has an $\emptyset ''$-computable nontrivial self-embedding, but there is a computable infinite linear order with no $\emptyset '$-computable nontrivial self-embeddings.

Open Question 3.1

(Downey, Jockusch, and Miller [25]). Is there a computable infinite linear order $\mathcal L$ such that every nontrivial self-embedding of $\mathcal L$ computes $\emptyset ''$?

As mentioned above, there is a computable presentation of $\omega$ with no computable nontrivial self-embeddings, and the same is true of many order types. There is one known class of computably presentable linear orders for which every computable presentation has a computable nontrivial self-embedding. A linear order $\mathcal L$ is $\eta$-like if the order type of $\mathcal L$ can be obtained from $\eta$ by replacing each point by a nonempty block of finitely many points. A linear order $\mathcal L$ is strongly $\eta$-like if there is an n such that the order type of $\mathcal L$ can be obtained from $\eta$ by replacing each point by a nonempty block of at most n many points. Watnick and Lerman (see [15]) noted that if a computable linear order has a strongly $\eta$-like interval, then it has a computable nontrivial self-embedding.

Since having a strongly $\eta$-like interval is a property of an order type, rather than of its presentations, if a computably presentable linear order $\mathcal L$ has a strongly $\eta$-like interval, then every computable presentation of $\mathcal L$ has a computable nontrivial self-embedding. Downey and Moses (see [15]) conjectured that this is the only situation in which this is the case, that is, that the answer to the following question is positive.

Open Question 3.2

(Downey and Moses (see [15])). If every computable presentation of a computable linear order $\mathcal L$ has a computable nontrivial self-embedding, must $\mathcal L$ contain a strongly $\eta$-like interval?

Downey, Kastermans, and Lempp [27] showed that this conjecture of Downey and Moses holds for all computable $\eta$-like linear orderings. In [15], Rod discussed some of the difficulties involved in proving the full conjecture.

4 Computable Dimension and Relatively Easy Isomorphisms

Another natural question to ask about a computably presentable structure is how many computable presentations it has, up to computable isomorphism. This number is known as the computable dimension of the structure. A structure of computable dimension 1 is said to be computably categorical. There are many examples of computably categorical structures, such as $(\mathbb Q,<)$, and of structures of computable dimension $\omega$, such as $(\mathbb N,<)$. Structures of finite computable dimension greater than 1 do not seem to occur “in nature”, but nevertheless exist, as shown by Goncharov [38]. Indeed, there are structures of any given finite dimension. By the kinds of general encoding results mentioned in Sect. 1, such structures also exist within various familiar classes of structures. A particularly interesting recent result in this direction by Miller, Poonen, Schoutens, and Shlapentokh [90], which resolved a longstanding open question, is that the class of fields has the same universality properties as the ones dealt with by Hirschfeldt, Khoussainov, Shore, and Slinko [52] (as discussed in Sect. 1). In particular, there are fields of any given finite dimension. (Another interesting aspect of [90] is the casting of encoding results such as the ones in [52] in terms of a new kind of computable category theory. This line of research has been further pursued by Harrison-Trainor, Melnikov, Miller, and Montalbán [45].)

There are several situations in which structures of finite computable dimension greater than 1 cannot exist, however. For instance, Goncharov and Dzgoev [41] and Remmel [98] showed that every computably presentable linear order has computable dimension 1 or $\omega$; Goncharov [40] did the same for Boolean algebras (though the result was implicit in earlier work of Goncharov and, independently, LaRoche [70]); and Lempp, McCoy, Miller, and Solomon [71, 72] for trees (as partial orders, or under the meet function). A more computability-theoretic obstruction to the existence of structures of finite computable dimension greater than 1 is given by the following result.

Theorem 4.1

(Goncharov [39]). Let $\mathcal A$ and $\mathcal B$ be computable structures such that there is no computable isomorphism between $\mathcal A$ and $\mathcal B$, but there is a $\Delta ^0_2$ isomorphism between them. Then $\mathcal A$ has computable dimension $\omega$.

Goncharov’s examples in [38] of structures of finite computable dimension greater than 1 are $\Delta ^0_3$ -categorical, i.e., for each such structure $\mathcal M$, there is a $\Delta ^0_3$ isomorphism between any two given presentations of $\mathcal M$. Thus Theorem 4.1 cannot be extended to $\Delta ^0_3$ isomorphisms. But perhaps it can be extended to some class intermediate between $\Delta ^0_2$ and full-blown $\Delta ^0_3$ isomorphisms.

One way to zero in on a potential class of this kind is to consider concrete examples. One such example is given by locally finite connected graphs, where a graph is locally finite if each vertex is on only finitely many edges. (It does not matter here whether the graphs are directed or undirected.) There are several examples of graphs of finite computable dimension greater than 1, and in every case they make essential use of vertices connected to infinitely many other vertices. It seems difficult to modify these constructions to produce locally finite graphs. Nevertheless, the following question, which comes from joint work with Bakh Khoussainov, remains open.

Open Question 4.2

Is there a locally finite connected graph of finite computable dimension greater than 1?

Another interesting example is that of algebraic fields.

Open Question 4.3

(Hirschfeldt, Kramer, Miller, and Shlapentokh [53]). Is there an algebraic field of finite computable dimension greater than 1?

What connects these two classes of structures is that if we take two isomorphic computable structures $\mathcal A$ and $\mathcal B$ in either of these classes, there is a computable infinite, finitely branching subtree of $\omega ^\omega$ each of whose paths is an isomorphism between $\mathcal A$ and $\mathcal B$. (In the sense that for each such path P, the map $n \mapsto P(n)$ is such an isomorphism.) If $\mathcal A$ and $\mathcal B$ are isomorphic computable locally finite connected graphs and we fix $a \in \mathcal A$ and $b \in \mathcal B$ such that $(\mathcal A,a)$ and $(\mathcal B,b)$ are isomorphic, it is easy to build a computable finitely branching tree whose paths are exactly the isomorphisms between $(\mathcal A,a)$ and $(\mathcal B,b)$. If $\mathcal A$ and $\mathcal B$ are isomorphic computable algebraic fields then Miller [89] showed that there is a computable finitely branching tree whose paths are exactly the isomorphisms between $\mathcal A$ and $\mathcal B$.

It is possible that Theorem 4.1 can be extended to cover this general case, giving a positive answer to the following question, which comes from discussions with Russell Miller, and hence negative answers to Questions 4.2 and 4.3.

Open Question 4.4

Let $\mathcal A$ and $\mathcal B$ be computable structures that are not computably isomorphic. Suppose that there is a computable infinite, finitely branching subtree of $\omega ^\omega$ each of whose paths is an isomorphism between $\mathcal A$ and $\mathcal B$. Must the computable dimension of $\mathcal A$ be infinite?

5 Ramsey’s Theorem and Computability-Theoretic Reductions

Another of the papers I worked on with Rod, Steffen, and Reed at Wisconsin introduced me to a question that has continued to preoccupy me off and on since then: determining the exact relationship between Ramsey’s Theorem for Pairs (RT$^2_2$) and its stable version SRT$^2_2$. (Some of this section overlaps with a recent open questions paper by Patey [97], which also contains many questions on the reverse mathematics of Ramsey-type statements not considered here.)

The computability-theoretic and reverse-mathematical analysis of versions of Ramsey’s Theorem has been an important line of research since the work of Specker [111] and Jockusch [59] in the early 1970’s.

Definition 5.1

For a set X, let $[X]^n$ be the collection of n-element subsets of X. A k-coloring of $[X]^n$ is a map $c : [X]^n \rightarrow k$. A set $H \subseteq X$ is homogeneous for c if there is an $i<k$ such that $c(s)=i$ for all $s \in [H]^n$.

Ramsey’s Theorem for n-tuples and k colors RT$^n_k$ is the statement that every k-coloring of $[\mathbb N]^n$ has an infinite homogeneous set. RT$^n_{<\infty }$ is the statement $\forall k\, \text {RT}^n_k$. RT is the statement $\forall n\, \text {RT}^n_{<\infty }$.

It is not difficult to show that RT$^n_k$ is equivalent to RT$^n_2$ over RCA$_0$ for all $k \geqslant 2$, and of course RT$^1_2$ is provable in RCA$_0$. Building on computability-theoretic results of Jockusch [59], Simpson [106] showed that RT$^n_2$ is equivalent to ACA$_0$ over RCA$_0$ for all $n \geqslant 3$. The $n=2$ case has proved to be considerably more interesting. Building on computability-theoretic results of Jockusch [59], Hirst [56] showed that RT$^2_2$ is not provable in WKL$_0$. Seetapun (see [105]) showed that RT$^2_2$ does not imply ACA$_0$ over RCA$_0$. More recently, Liu [75, 76] showed that RT$^2_2$ does not imply WKL$_0$, or even WWKL$_0$ (which will be discussed further below), over RCA$_0$.

Unlike WKL$_0$, there are not many principles equivalent to RT$^2_2$, but there is a whole universe of principles provable from $\text {RCA}_0+\text {RT}^2_2$. (I have told some of this story in considerably more detail in [47].) For instance, Cholak, Jockusch, and Slaman [8] found a highly productive way to split RT$^2_2$ into two principles, called SRT$^2_2$ and COH.

Definition 5.2

A coloring $c : [\mathbb N]^2 \rightarrow k$ is stable if $\lim _y c(x,y)$ exists for all x. Stable Ramsey’s Theorem for Pairs and k colors SRT$^2_k$ is the statement that every stable k-coloring of $[\mathbb N]^2$ has an infinite homogeneous set. SRT$^2_{<\infty }$ is the statement $\forall k\, \text {SRT}^2_k$.

A set C is cohesive for a collection of sets $R_0,R_1,\ldots$ if C is infinite and for each i, either $C \subseteq ^* R_i$ or $C \subseteq ^* \overline{R_i}$ (where $X \subseteq ^* Y$ means that $X \setminus Y$ is finite). The Cohesive Set Principle COH is the statement that every countable collection of sets has a cohesive set.

One direction of the original proof in [8] that RT$^2_2$ is equivalent to ${\text {SRT}^2_2} + {\text {COH}}$ required $\Sigma ^0_2$-induction, but this use of induction was removed by Mileti [83] and Jockusch and Lempp [unpublished].

Theorem 5.3

(Cholak, Jockusch, and Slaman [8]; Mileti [83]; Jockusch and Lempp [unpublished]). RT$^2_2$ is equivalent to $\text {SRT}^2_2 + \text {COH}$ over RCA$_0$.

Cholak, Jockusch, and Slaman [8] showed that COH does not imply RT$^2_2$ over RCA$_0$, but obtaining the analogous statement for SRT$^2_2$ in place of COH proved far more elusive. For well over a decade, many researchers, myself included, tried a variety of approaches to this problem without success.

A frustrating aspect of this problem is that, from the point of view of computability theory, stability does allow us to decrease the complexity of homogeneous sets in general. Jockusch [59] showed that there are computable 2-colorings of $[\mathbb N]^2$ with no $\Delta ^0_2$ infinite homogeneous sets. On the other hand, if the computable coloring ${c}: [\mathbb N]^2 \rightarrow 2$ is stable, then $\emptyset '$ can compute the function $x \mapsto \lim _y c(x,y)$, from which it is easy to obtain an infinite homogeneous set for c effectively. Thus c has a $\Delta ^0_2$ infinite homogeneous set. However, this fact in itself does not help to build a model of SRT$^2_2$ that is not a model of RT$^2_2$, because such a model would have to contain not only an infinite homogeneous set H for c, but one for every H-computable stable 2-coloring of pairs, at which point one might be in the realm of $\Delta ^0_3$ sets (and of course the complexity of homogeneous sets might get even higher as further iterations are considered). What would help would be to find a $\mathcal C \subset \Delta ^0_2$ such that every 2-coloring of pairs $c \in \mathcal C$ has an infinite homogeneous set H such that $c \oplus H \in \mathcal C$. Cholak, Jockusch, and Slaman [8] suggested that the low sets might form such a class, but that turns out not to be the case.

Theorem 5.4

(Downey, Hirschfeldt, Lempp, and Solomon [19]). There is a computable stable 2-coloring of pairs with no low infinite homogeneous sets.

It did not occur to us (or at least to me) to ask whether this theorem holds in nonstandard models of $\Sigma ^0_1$-PA (the first-order part of RCA$_0$). As it turns out, it does not, though it takes a rather intricate construction to establish this fact. Chong, Slaman, and Yang [9] built a model of $\text {RCA}_0 + \text {SRT}^2_2$ (in which $\Sigma ^0_2$-induction fails) whose second-order part consists entirely of low sets, in the sense of the first-order part of the model. As shown by Cholak, Jockusch, and Slaman [8], B$\Sigma ^0_2$ ($\Sigma ^0_2$-bounding) must hold in any model of $\text {RCA}_0 + \text {SRT}^2_2$. Chong, Slaman, and Yang [9] also showed that Jockusch’s result in [59] that there are computable 2-colorings of $[\mathbb N]^2$ with no $\Delta ^0_2$ infinite homogeneous sets goes through in $\text {RCA}_0+\text {B}\Sigma ^0_2$. Thus they were able to separate SRT$^2_2$ and RT$^2_2$ in the reverse-mathematical setting.

Theorem 5.5

(Chong, Slaman, and Yang [9]). $\text {RCA}_0+\text {SRT}^2_2 \nvdash \text {RT}^2_2$.

Remarkable as it is, this result still leaves open the question of whether any approach along more traditional lines, working in the standard first-order model, can be made to work. Such an approach would in fact establish a stronger result. Recall that an $\omega$-model of second-order arithmetic is one with standard first-order part. Write $P \leqslant _\omega Q$ to mean that every $\omega$-model of $\text {RCA}_0+Q$ is an $\omega$-model of P. For example, COH and (S)RT$^2_2$ can be separated via $\omega$-models, for instance by using a conservativity result of Hirschfeldt and Shore [55] or by considering the principle DNR, as in Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman [49], so $\text {RT}^2_2 \nleqslant _\omega \text {COH}$. The natural follow-up question to Theorem 5.5 can now be stated as follows.

Open Question 5.6

(Cholak, Jockusch, and Slaman [8]; Chong, Slaman, and Yang [9]). Is $\mathrm{RT}^2_2 \leqslant _\omega \mathrm{SRT}^2_2$? Equivalently, is $\mathrm{COH} \leqslant _\omega \mathrm{SRT}^2_2$?

In light of the methods in [9] discussed above, the following question is also of interest (and a positive answer to it would imply a positive answer to Question 5.6).

Open Question 5.7

(Chong, Slaman, and Yang [10]). Does $\mathrm{RCA}_0+\mathrm{I}\Sigma ^0_2+\mathrm{SRT}^2_2 \vdash \mathrm{RT}^2_2$?

It is possible that the approach to answering Question 5.6 ruled out in its simplest form by Theorem 5.4 could still be revived, if the answer to the following questions is positive.

Open Question 5.8

(Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman [49]). Does every computable stable 2-coloring of pairs have an infinite homogeneous that is both $\Delta ^0_2$ and low$_2$ (or just $\Delta ^0_2$ and low$_n$ for some n, where n could even depend on the coloring)?

As explained in [49], a relativizable positive answer to this question would yield a negative solution to Question 5.6. On the other hand, it could be that there is a computable stable 2-coloring of pairs such that the jump of every infinite homogeneous set has PA degree relative to $\emptyset '$, which, again as explained in [49], would not only give a negative answer to Question 5.8, but (if this fact is relativizable) also a positive one to Question 5.6.

Another way to think about Question 5.6 is to study its analogs for computability-theoretic reducibilities stronger than $\leqslant _\omega$. Many interesting principles (including Ramsey’s Theorem and its variants) have the form

$$\begin{aligned} \forall X\,[\Theta (X)\, \rightarrow \, \exists Y\, \Psi (X,Y)] \end{aligned}$$

with $\Theta$ and $\Psi$ arithmetic. Such a principle can be thought of as a problem. An instance of this problem is an X such that $\Theta (X)$ holds and a solution to this instance is a Y such that $\Psi (X,Y)$ holds.

For principles of this kind, the definition of $\leqslant _\omega$ can be reformulated without reference to reverse mathematics. Recall that a Turing ideal is a collection of sets closed under Turing reduction and finite joins. Say that a problem P holds in a Turing ideal $\mathcal I$ if every instance of P in $\mathcal I$ has a solution in $\mathcal I$. Turing ideals are exactly the second-order parts of $\omega$-models of RCA$_0$, so $P \leqslant _\omega Q$ if and only if P holds in every ideal in which Q holds.

Reducibilities such as the following ones allow for a finer-grained investigation of relationships between problems. All four of the notions below capture the idea of being able to solve any given instance X of a problem P by using the ability to solve an instance of another problem Q obtained computably from X. The difference between the computable and Weihrauch versions is that the latter are uniform. The difference between the normal and strong versions is that the latter do not allow the use of X itself in computing a solution to X.

Definition 5.9

Let P and Q be problems.

• 1. Say that P is computably reducible to Q, and write , if for every instance X of P, there is an X-computable instance $\widehat{X}$ of Q such that, for every solution $\widehat{Y}$ to $\widehat{X}$, there is an $X \oplus \widehat{Y}$-computable solution to X.

• 2. Say that P is strongly computably reducible to Q, and write , if for every instance X of P, there is an X-computable instance $\widehat{X}$ of Q such that, for every solution $\widehat{Y}$ to $\widehat{X}$, there is a $\widehat{Y}$-computable solution to X.

• 3. Say that P is Weihrauch reducible to Q, and write , if there are Turing functionals $\Phi$ and $\Psi$ such that, for every instance X of P, the set $\widehat{X}=\Phi ^X$ is an instance of Q, and for every solution $\widehat{Y}$ to $\widehat{X}$, the set $Y=\Psi ^{X \oplus \widehat{Y}}$ is a solution to X.

• 4. Say that P is strongly Weihrauch reducible to Q, and write , if there are Turing functionals $\Phi$ and $\Psi$ such that, for every instance X of P, the set $\widehat{X}=\Phi ^X$ is an instance of Q, and for every solution $\widehat{Y}$ to $\widehat{X}$, the set $Y=\Psi ^{\widehat{Y}}$ is a solution to X.

(Strong) Weihrauch reducibility has also been called (strong) uniform reducibility. The notion of Weihrauch reducibility is actually a broader one, introduced by Weihrauch [118, 119] in the context of computable analysis and widely studied since, but the definition given above is equivalent to a special case of it. (See Dorais, Dzhafarov, Hirst, Mileti, and Shafer [13] and the papers listed in the bibliography [5].)

One approach to Question 5.6 is to seek partial answers, perhaps involving methods that can be adapted to answer the full question, by replacing $\leqslant _\omega$ with each of the stronger notions of reducibility above. Of course, given the computability-theoretic difference between RT$^2_2$ and SRT$^2_2$, the second of the two equivalent statements of Question 5.6 is the relevant one here. All but one of these versions of Question 5.6 have been answered by Dzhafarov [32].

Theorem 5.10

(Dzhafarov [32]).  and (and hence ).

The case of computable reducibility remains open, however, and might well be the most relevant one to a potential solution to Question 5.6.

Open Question 5.11

(Hirschfeldt and Jockusch [48]). Is ?

It should be noted that, when considering reducibilities stronger than $\leqslant _\omega$, the number of colors starts to matter. For instance, while it is not difficult to show that $\text {RT}^n_k \leqslant _\omega \text {RT}^n_j$ even when $2 \leqslant j \leqslant k$, Patey [96] showed that in this case, as long as $n \geqslant 2$. Thus the following results strengthen Theorem 5.10.

Theorem 5.12

(Dzhafarov [32]). .

Theorem 5.13

(Dzhafarov, Patey, Solomon, and Westrick [33]). .

The analog of Question 5.11 for SRT$^2_{<\infty }$ is also open.

The difference between and $\leqslant _\omega$ is that the latter covers cases in which a problem P is reducible a problem Q, but only if one is allowed to use several instances of Q to solve an instance of P. It is thus natural to seek a nonuniform version of $\leqslant _\omega$ that allows for multiple uses of a principle, but only if the relevant instances are produced in a uniformly computable way. Such a notion was defined in [48] using games.

Definition 5.14

For problems P and Q representing true $\Pi ^1_2$ principles, the reduction game $G(Q \rightarrow P)$ is a two-player game that proceeds as follows.

On the first move, Player 1 plays an instance $X_0$ of P, and Player 2 either plays an $X_0$-computable solution to $X_0$ and declares victory, in which case the game ends, or responds with an $X_0$-computable instance $Y_1$ of Q. If Player 2 cannot move (which might happen if there is no $X_0$-computable instance of Q), then Player 1 wins, and the game ends.

For $n > 1$, on the nth move (if the game has not yet ended), Player 1 plays a solution $X_{n-1}$ to the instance $Y_{n-1}$ of Q. Then Player 2 either plays a $(\bigoplus _{i<n} X_i)$-computable solution to $X_0$ and declares victory, in which case again the game ends, or plays a $(\bigoplus _{i<n} X_i)$-computable instance $Y_n$ of Q.

Player 2 wins this play of the game if it ever declares victory. Otherwise, Player 1 wins.

Reduction games can be used to give a characterization of $\leqslant _\omega$. A strategy for a player in a game such as the above ones is a map taking any sequence of moves by the opponent to a move by the given player. Such a strategy is winning if it enables the player to win no matter what the opponent does.

Theorem 5.15

(Hirschfeldt and Jockusch [48]). If $P \leqslant _\omega Q$ then Player 2 has a winning strategy for $G(Q \rightarrow P)$. Otherwise, Player 1 has a winning strategy for $G(Q \rightarrow P)$.

Effectivizing winning strategies yields a notion of generalized uniform reducibility between $\Pi ^1_2$ principles. (See [48] for a more detailed definition.)

Definition 5.16

A computable strategy for Player 2 in a reduction game is a Turing functional that, given the join of Player 1’s first n moves as an oracle, outputs Player 2’s nth move.

Say that P is Weihrauch (or uniformly) reducible to Q in the generalized sense, and write , if Player 2 has a computable winning strategy in $G(Q \rightarrow P)$.

Assuming that, as expected, the answer to Question 5.6 is negative, the following might be an easier version of that question.

Open Question 5.17

(Hirschfeldt and Jockusch [48]). Is ?

It is also worth noting that it does not seem trivial to adapt the proof of Theorem 5.5 above given in [9] to the case of arbitrarily many colors. For one thing, Cholak, Jockusch, and Slaman [8] showed that SRT$^2_{<\infty }$ implies B$\Sigma ^0_3$, and hence I$\Sigma ^0_2$, over RCA$_0$, so SRT$^2_{<\infty }$ does not hold in the model built in that proof. Thus the following question is still open.

Open Question 5.18

(Cholak, Jockusch, and Slaman [8]). Does $\mathrm{SRT}^2_{<\infty }$ imply $\mathrm{RT}^2_{<\infty }$ over $\mathrm{RCA}_0$?

A liability of writing an open questions paper is that some of the questions might be solved while the paper is in preparation. Indeed, while I was in the final stages of revising this paper for submission, a problem I had planned to discuss was solved by Monin and Patey [93]. I will still include this discussion here, however, as an example of ongoing work in the area, and as an opportunity to mention a couple of open questions in [93].

One of the things that looking at notions of computability-theoretic reduction does is highlight cases in which relationships between principles are less well-understood than might have been thought. Recall that Weak Weak König’s Lemma (WWKL) is the statement that if T is a binary tree such that $\liminf _n \frac{|\{\sigma \in T : |\sigma |=n\}|}{2^n} > 0$, then T has a path. The system WWKL$_0$ obtained by adding this statement to RCA$_0$ has played a significant role in reverse mathematics, and there is a case for according it similar status to the area’s “big five” systems (making it the John Havlicek of reverse mathematics, perhaps). This system is very closely connected with algorithmic randomness, since the “fat trees” in the statement of WWKL correspond to $\Pi ^0_1$ classes of positive measure, and as shown by Kučera [69], a $\Pi ^0_1$ class $\mathcal C$ has positive measure if and only if every 1-random set has a tail in $\mathcal C$.

Liu’s proof in [76] that $\text {WWKL} \nleqslant _\omega \text {RT}^2_2$ could be seen as closing the story on the relationship between WWKL$_0$ and RT$^n_k$, since for $n \geqslant 3$ and $k \geqslant 2$, RT$^n_k$ is equivalent to ACA$_0$ over RCA$_0$, and hence considerably stronger than WWKL$_0$. Indeed, as shown by Jockusch [59], in this case, there is a k-coloring of $[\mathbb N]^n$ all of whose infinite homogeneous sets compute $\emptyset '$, and relativizing this result shows that . Jockusch’s argument actually shows that .

But what about strong reductions? Relativizing Jockusch’s theorem shows that if $n \geqslant 3$ and $k \geqslant 2$ then for any X, there is an X-computable instance of RT$^n_k$ such that for any solution H. However, the conclusion of this statement cannot in general be improved to . Indeed, Hirschfeldt and Jockusch [48] showed that if X is not hyperarithmetic, then there is no instance of RT (of any complexity) such that every solution computes X. In particular, RT does not allow self-encoding, where a problem P allows self-encoding if for every X there is an X-computable instance Z of P all of whose solutions compute X. (This notion is similar to that of cylinder in the theory of Weihrauch reducibility, but that notion requires the solutions of Z to compute X uniformly.) An example of a principle that does allow self-encoding, and indeed is a cylinder, is WKL. (Given X, consider an X-computable binary tree whose only path is X.) As noted in [48], it follows that .

WWKL, on the other hand, does not allow self-encoding. Relativizing the result of Kučera mentioned above shows that every set that is 1-random relative to a given set X computes a solution to every X-computable instance of WWKL, and it is well-known that for most X, no set that is 1-random relative to X can compute X. (The precise statement, proved by Hirschfeldt, Nies, and Stephan [54], is that this is the case unless X belongs to the countable class of K-trivial sets. Rod and researchers influenced by him have played a major role in developing the theory of these sets, which are now one of the central objects of study in algorithmic randomness.) Thus an early version of Hirschfeldt and Jockusch [48] included the following questions (which can also be asked for sW-reducibility): Let $n \geqslant 3$ and $k \geqslant 2$. Is ? Is ?

Another way to look at these questions is as being about the relative distribution of homogeneous and 1-random sets. For instance, the question of whether can be restated as follows: Is it the case that, for every X, there is an X-computable instance of Ramsey’s Theorem each of whose infinite homogeneous sets computes a set that is 1-random relative to X?

As noted above, all of these questions have now been answered by the following recent result.

Theorem 5.19

(Monin and Patey [93]).  .

A set A is computably encodable if every infinite set has an infinite subset that computes A. The proof of Theorem 5.19 uses a notion called $\Pi ^0_1$ encodability, which is introduced in [93] as an extension of computable encodability. The definition in [93] is for subsets of $\omega ^\omega$, but it is a bit simpler, and sufficient for the proof of Theorem 5.19, to consider subsets of $2^\omega$.

Definition 5.20

A class $\mathcal C \subseteq 2^\omega$ is $\Pi ^0_1$ encodable if every infinite set has an infinite subset X such that $\mathcal C$ has a nonempty $\Pi ^{0,X}_1$ subclass.

The key to proving Theorem 5.19 is the following result.

Theorem 5.21

(Monin and Patey [93]). A class $\mathcal C \subseteq 2^\omega$ is $\Pi ^0_1$ encodable if and only if it has a nonempty $\Sigma ^1_1$ subclass.

As explained in [93], this theorem implies Solovay’s result in [109] that a set is computably encodable if and only if it is hyperarithmetic.

Theorem 5.19 follows from Theorem 5.21 by letting T be an instance of WWKL such that the class [T] of paths on T has no nonempty $\Sigma ^1_1$ subsets. As noted in [93], an example of such a T is an infinite tree whose paths are all 1-random relative to Kleene’s $\mathcal O$, since every nonempty $\Sigma ^1_1$ class has an element computable from $\mathcal O$. Now let c be an instance of RT such that any solution computes a path on T. Since every infinite set has an infinite subset that is homogeneous for c, it follows that [T] is encodable, contradicting Theorem 5.21.

This argument actually proves something stronger, because there is no need for c to be computable from T. Monin and Patey [93] made the following definition.

Definition 5.22

A problem P is strongly omnisciently computably reducible to a problem Q, written as , if for every instance X of P, there is an instance $\widehat{X}$ of Q such that, for every solution $\widehat{Y}$ to $\widehat{X}$, there is a $\widehat{Y}$-computable solution to X.

As noted in [93], several proofs that show that in fact show that . As discussed above, this is in particular true of Theorem 5.19.

Theorem 5.23

(Monin and Patey [93]). .

Monin and Patey [93] asked the following questions about soc-reducibility.

Open Question 5.24

(Monin and Patey [93]). Let $n,k \geqslant 2$. Is ? Is ?

Before moving away from reverse mathematics, I will mention one more question, which was posed by Damir Dzhafarov and Noah Schweber (see [104]), and came from work they did in reverse mathematics.

Definition 5.25

Let f be a computable binary function such that $f(n,s+1) \leqslant f(n,s)$ for all n and s, and let $F(n)=\lim _s f(n,s)$. A limit-nondecreasing subsequence for f is a set X such that if $i,j \in X$ and $i<j$ then $F(i) \leqslant F(j)$. (Such an X is called f-good in [104].)

It is easy to see that every f of this kind has an $\emptyset '$-computable limit-nondecreasing subsequence. Dzhafarov and Schweber (see [104]) asked whether this upper bound is tight. That is, they asked whether there is an f as above such that every limit-nondecreasing subsequence computes $\emptyset '$, and failing that, whether it is the case that a set that computes a limit-nondecreasing subsequence for every such f must compute $\emptyset '$. Patey (see [104]) has given negative answers to both of these questions, and provided further computability-theoretic information on the complexity of limit-nondecreasing subsequences. There may be more to say on this front, however.

Open Question 5.26

(Dzhafarov and Schweber (see [104])). How complicated must a limit-nondecreasing subsequence for a function f as above be in general?

Kolmogorov complexity functions, such as plain or prefix-free complexity, are natural examples of functions with nonincreasing approximations. Suppose for example that $f(n)=C_s(n)$, where $C_s(n)$ is the stage s approximation to the plain Kolmogorov complexity C(n) of n, and let X be a limit-nondecreasing subsequence for f. Since there cannot be $2^k$ many numbers n with $C(n)<k$, the $2^k$th element n of X must have $C(n) \geqslant k$. Thus there is an X-computable function g such that $C(g(k)) \geqslant k$ for all k. By results of Kjos-Hanssen, Merkle, and Stephan [66], X has DNC degree. (That is, there is an X-computable function h that is diagonally noncomputable, which means that $h(e) \ne \Phi _e(e)$ for all e, where $\Phi _e$ is the eth partial computable function.) Thus, as pointed out in [104], the answer to the first part of Question 5.26 is at least at the level of the DNC degrees.

Kolmogorov complexity functions are rather special, though. If A has DNC degree then, again by results in [66], A computes an increasing function g such that $C(g(k)) \geqslant k$ for all k. Let c be such that $C(n) \leqslant n+c$ for all n. Then one can A-computably find $n_0<n_1<\cdots$ such that $C(g(n_{i+1})) \geqslant g(n_i)+c$ for all i. The set $X=\{g(n_i) : i \in \omega \}$ is then an A-computable limit-nondecreasing subsequence for the function f in the previous paragraph. Thus in this case there is a full answer to the first part of Question 5.26, but the general case might well require more powerful oracles.

Question 5.26 can also be restated in reverse-mathematical terms. Let LNS be the following statement: If f is a binary function such that $f(n,s+1) \leqslant f(n,s)$ for all n and s then there is an infinite set X such that if $i,j \in X$ and $i<j$ then $\exists t\,\forall s>t\, (f(i,s) \leqslant f(j,s))$.

Open Question 5.27

What is the reverse mathematical strength of LNS?

Patey (see [104]) showed that LNS does not imply the principle ADS (which was studied in [55] and is strictly weaker than RT$^2_2$) over RCA$_0$.

6 Measures of Relative Randomness

Much of my time in Wellington was spent thinking about algorithmic randomness. Richard Coles brought a question of Cris Calude’s down from Auckland, which Rod, André Nies, and I eventually solved [21]. In the process of working on this question, Rod and I started to get increasingly interested in the general area. This interest led to several papers, a survey article with André and Bas Terwijn [22], and a slim volume called Algorithmic Randomness and Complexity [17].

The Sydney Opera House was completed ten years late and almost fifteen times over budget. By those standards, Rod and I did not do too badly. Our book took about seven years longer to write and ended up being three or four times as long as we had initially projected. Some of this delay was caused by the rapidly moving target that the area became as more and more researchers—many of them brilliant young ones, and many of them mentored or influenced by Rod—began to solve its problems and unearth new ones at an alarming rate. In this section and the next, I would like to mention two old problems (by the standards of this area) that have endured despite these efforts.

The Kučera-Gács Theorem [37, 69] states that every set is Turing reducible, and indeed wtt-reducible, to some 1-random set. Merkle and Mihailović [80] showed that the use of this reduction can always be taken to be of order $n+o(n)$. One of the few original results in the Downey-Hirschfeldt book [17] is that this bound cannot be improved to $n+O(1)$. Say that A is cl-reducible to B if there is a Turing functional $\Gamma$ such that $\Gamma ^B = A$ and $\gamma ^B(n) \leqslant n+O(1)$, where $\gamma$ is the use function of $\Gamma$. (The original name for this notion in Downey, Hirschfeldt, and LaForte [18] was “strong weak truth table (sw-) reducibility”. For some reason, this adjectival salad was not popular. Lewis and Barmpalias [73, 74] renamed it “computable Lipschitz (cl-) reducibility”, reflecting the fact this reducibility is an effective version of the notion of Lipschitz transformation.)

Theorem 6.1

(Downey and Hirschfeldt [17]). There is a set that is not cl-reducible to any 1-random set.

Given the relationship between initial-segment complexity and randomness, if then there is reason to say that A is no more random than B. (In particular, in this case $K(A \upharpoonright n) \leqslant K(B \upharpoonright n) + O(1)$, where K is prefix-free Kolmogorov complexity.) This is no longer the case if the bound on the use is even slightly relaxed. For instance, for any unbounded, nondecreasing computable function f and any 1-random set A, it is easy to find a non-1-random set B such that A is Turing reducible to B via a reduction with use bounded by $n+f(n)$. Other measures of relative randomness include the following.

Definition 6.2

Say that A is K-reducible to B if $K(A \upharpoonright n) \leqslant K(B \upharpoonright n) + O(1)$, and that A is C-reducible to B if $C(A \upharpoonright n) \leqslant C(B \upharpoonright n) + O(1)$ (where, as above, C is plain Kolmogorov complexity).

Say that A is rK-reducible to B if $K(A \upharpoonright n \mid B \upharpoonright n) \leqslant O(1)$. It is easy to see that this definition does not change if K is replaced by C.

The development of the theory of algorithmic randomness seems to have made these notions less significant than they once may have seemed, but the following questions, motivated by Theorem 6.1, still seem worth answering.

Open Question 6.3

(Downey, Hirschfeldt, Nies, and Terwijn [22]; Miller and Nies [86]). Is every set K-reducible to some 1-random set? Is every set C-reducible to some 1-random set? Is every set rK-reducible to some 1-random set?

Although these questions have not been central to the study of algorithmic randomness, I do believe they (and particularly the first one) are of intrinsic interest, given that the interplay between levels of randomness and initial-segment complexity has been a major theme in the area. Furthermore, the fact that they have remained open for so long, in the face of our greatly improved understanding of the notions involved, suggests that they may depend on aspects of the notions of 1-randomness and Kolmogorov complexity that remain underdeveloped.

7 Nonmonotonic Randomness

An even older question in algorithmic randomness is that of establishing the relationship between nonmonotonic randomness and 1-randomness. This question seems quite fundamental, since the nonmonotonic betting strategies used to define nonmonotonic randomness are natural generalizations of the usual betting strategies that can be used to define notions such as 1-randomness, computable randomness, and Schnorr randomness. Furthermore, it is the only remaining one I know of in determining implications between major notions of algorithmic randomness.

Nonmonotonic randomness (also know as Kolmogorov-Loveland randomness) was introduced by Muchnik, Semenov, and Uspensky [95]. The version of the definition below is essentially the one given by Merkle, Miller, Nies, Reimann, and Stephan [81].

In algorithmic randomness, a martingale is a function $d : 2^{<\omega } \rightarrow \mathbb R^{\geqslant 0}$ such that $d(\sigma ) = \frac{d(\sigma 0)+d(\sigma 1)}{2}$, representing a strategy for betting on the successive bits of a binary sequence. The initial capital available is $d(\lambda )$, where $\lambda$ is the empty string. If $\sigma$ represents the bits seen so far, then the strategy is to bet $\frac{d(\sigma 0)}{2d(\sigma )}$ of the current capital on the next bit being 0, and $\frac{d(\sigma 1)}{2d(\sigma )}$ of this capital on the next bit being 1. If that strategy is followed, then for any $\tau$, the capital available after seeing the bits of $\tau$ is $d(\tau )$. A martingale d succeeds on a set A if $\limsup _n d(A \upharpoonright n) = \infty$.

A martingale is computable if its values are uniformly computable, and c.e. if its values are uniformly left-c.e. One of the several ways to define 1-randomness is to say that a set is 1-random if no c.e. martingale succeeds on it. Say that a set is computably random if no computable martingale succeeds on it. Schnorr [101] showed that the latter notion, which he introduced in [101, 102], is strictly weaker than 1-randomness.

Schnorr [101, 102] also introduced the notion of Schnorr randomness, which he believed more adequately captures the informal idea of “computable randomness” than the notion now known as computable randomness. (He saw 1-randomness itself as a notion of computably enumerable randomness.) An order is an unbounded, nondecreasing function from $\mathbb N$ to $\mathbb N$. A set X is Schnorr random if $\limsup _n \frac{d(X \upharpoonright n)}{h(n)}<\infty$ for every computable martingale d and every computable order h. Wang [115, 116] showed that Schnorr randomness is strictly weaker than computable randomness.

It is natural to ask what happens if one is allowed to bet on the bits of a sequence out of order, which leads to the idea of a nonmonotonic betting strategy. Such a strategy has two components, a scan rule and a stake function. These determine the next bit to bet on, and how much to bet on each possible value of that bit, respectively, based on the values observed at the previously selected bits. Of course, a strategy cannot be allowed to bet twice on the same bit. (In the definition in [81], the scan rules and stake functions making up nonmonotonic betting strategies are partial functions, but Merkle [79] showed that, for the purpose of defining nonmonotonic randomness, it is enough to consider total nonmonotonic betting strategies.)

Definition 7.1

A finite assignment is a sequence $(r_1,a_1),\ldots ,(r_n,a_n)$ with $r_i \in \mathbb N$ and $a_i \in \{0,1\}$, such that the $r_i$ are pairwise distinct. The domain of this assignment is $\{r_1,\ldots ,r_n\}$.

A scan rule is a function s from the set of finite assignments to $\mathbb N$ such that s(x) is not in the domain of x for each finite assignment x.

A stake function is a function from the collection of finite assignments to $[-1,1]$.

A nonmonotonic betting strategy is a pair consisting of a scan rule and a stake function.

The idea behind this definition of a stake function q is that, letting the current capital be d, a negative value of q(x) represents a bet of $-q(x)d$ that the value of the next bit bet on is 0, while a positive value of q(x) represents a bet of q(x)d that the value of the next bit bet on is 1 (and hence $q(x)=0$ represents an even bet, which is the same as not betting at all).

The nonmonotonic martingale $d^X_b$ associated with playing a nonmonotonic strategy b on a sequence X (with starting capital 1), and the resulting notion of nonmonotonic randomness, can now be defined as follows.

Definition 7.2

Let $b=(s,q)$ be a nonmonotonic betting strategy. For a set X, let $p^X(0)=\lambda$ and

$$\begin{aligned} p^X(n+1)=p^X(n) {}^\smallfrown (s(p^X(n)),X(s(p^X(n)))). \end{aligned}$$

Then $p^X(n)$ is the finite assignment corresponding to scanning X in accordance with s. Let $c^X(0)=1$ and

$$\begin{aligned} c^X(n+1) = {\left\{ \begin{array}{ll} 1-q(p^X(n)) &{} \text {if } X(s(p^X(n)))=0\\ 1+q(p^X(n)) &{} \text {if } X(s(p^X(n)))=1. \end{array}\right. } \end{aligned}$$

Let

$$\begin{aligned} d^X_b(n)=\prod _{i=0}^n c^X(i). \end{aligned}$$

The strategy b succeeds on X if $\limsup _n d^X_b(n) = \infty$.

Say that X is nonmonotonically random if no computable nonmonotonic betting strategy succeeds on it.

Muchnik, Semenov, and Uspensky [95] showed that 1-randomness implies nonmonotonic randomness, which in turn clearly implies computable randomness. (Their proof also shows that the notion of randomness obtained by considering c.e. nonmonotonic betting strategies in place of computable ones is equivalent to 1-randomness.) As explained for instance in [17, Sect. 7.5], results of Muchnik (see [95]) on Kolmogorov complexity show that the latter implication is strict. The following fundamental question remains open, however.

Open Question 7.3

(Muchnik, Semenov, and Uspensky [95]). Is there a set that is nonmonotonically random but not 1-random?

Merkle, Miller, Nies, Reimann, and Stephan [81] obtained several interesting results related to this question. In particular, they showed that if $A \oplus B$ is nonmonotonically random, then at least one of A or B is 1-random. On the one hand, this result suggests that nonmonotonic randomness and 1-randomness are quite close (as does Muchnik’s analysis of the initial-segment Kolmogorov complexity of nonmonotonically random sets in [95]). On the other hand, it is well-known that if $A \oplus B$ is random (in some sense), then one should expect the level of randomness of A and B individually to be higher than that of $A \oplus B$. (For instance, using results of Figueira, Hirschfeldt, Miller, Ng, and Nies [34], Bienvenu, Greenberg. Kučera, Nies, and Turetsky [3] showed that if $A \oplus B$ is 1-random then at least one of A or B has the stronger property of being balanced random.) Kastermans and Lempp [64] separated certain weaker versions of nonmonotonic randomness from 1-randomness.

As far as I know, the following question has not been considered so far. Say that a set X is Schnorr nonmonotonically random if $\limsup _n \frac{d^X_b(n)}{h(n)} < \infty$ for every computable nonmonotonic betting strategy b and every computable order h.

Open Question 7.4

What is the strength of Schnorr nonmonotonic randomness in relation to other notions of algorithmic randomness?

8 Asymptotic Computability

After finishing the book with Rod, I was slightly burned out on randomness. I was brought back into thinking about it by a question about coarse computability asked by Paul Schupp, which led to a paper with him, Carl Jockusch, and Rutger Kuyper [50]. Coarse computability and other notions of asymptotic computability capture the idea of computing a set “almost everywhere”. The contemporary computability-theoretic study of these notions began with a paper of Jockusch and Schupp [60], which studied the notion of generic computability introduced by Kapovich, Myasnikov, Schupp, and Shpilrain [63]. As with so many of the most interesting lines of research in computability theory, Rod got into the game early, in papers with Jockusch and Schupp [26] and Jockusch, McNicholl, and Schupp [24].

As it turns out, the idea of asymptotic computability had already occurred to Meyer [82] in the early 70’s, leading him to ask a question that was answered by Lynch [77]. Much later, Terwijn [113] returned to this idea, becoming to my knowledge the first person to define coarse computability. (Meyer and Lynch were working with a different notion of asymptotic computability, defined below.)

The definitions of generic and coarse computability begin with the relevant notion of “almost everywhere”.

Definition 8.1

For $S \subseteq \omega$ and $n \in \omega$, let $\rho _n(S)=\frac{|S \upharpoonright n|}{n}$.

The upper (asymptotic) density $\overline{\rho }(S)$ of S is $\limsup _n \rho _n(S)$.

The lower (asymptotic) density $\underline{\rho }(S)$ of S is $\liminf _n \rho _n(S)$.

If $\overline{\rho }(S)=\underline{\rho }(S)$ then this number is called the (asymptotic) density of S.

Definition 8.2

A partial description of a set A is a partial function f such that $f(n)=A(n)$ whenever f(n) is defined. A generic description of A is a partial description of A with domain of density 1. A set is generically computable if it has a computable generic description.

A coarse description of a set A is a set C such that $C(n)=A(n)$ on a set of density 1. A set is coarsely computable if it has a computable coarse description.

Jockusch and Schupp [61] showed that there are sets that are generically computable but not coarsely computable, and vice-versa.

These notions of asymptotic computability lead naturally to notions of asymptotic reducibility, from which degree structures are defined as usual. As with mass problems, there are both uniform and nonuniform versions.

Definition 8.3

Say that B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B.

Say that B is uniformly coarsely reducible to A if there is a Turing functional $\Phi$ such that if C is a coarse description of A, then $\Phi ^C$ is a coarse description of B.

Say that B is nonuniformly generically reducible to A if for every generic description f of A, there is an enumeration operator W such that $W^{{{\mathrm{graph}}}(f)}$ enumerates the graph of a generic description of B.

Say that B is uniformly generically reducible to A if there is an enumeration operator W such that if f is a generic description of A, then $W^{{{\mathrm{graph}}}(f)}$ is the graph of a generic description of B.

One of the basic questions one can ask about the degree structures arising from these reducibilities is whether minimal pairs exist. Recall that for a given degree structure with a minimum degree $\mathbf{0}$, nonzero degrees $\mathbf{a}$ and $\mathbf{b}$ form a minimal pair if $\mathbf{0}$ is the only degree that is below both $\mathbf{a}$ and $\mathbf{b}$. Hirschfeldt, Jockusch, Kuyper, and Schupp [50] showed that there are minimal pairs for (uniform or nonuniform) coarse reducibility, and indeed proved the stronger result that there are sets A and B that form a minimal pair for relative coarse computability; that is, A and B are not coarsely computable, but if C is coarsely computable relative both to A and to B, then C is coarsely computable. In fact, any A and B that are sufficiently mutually random form a minimal pair for relative coarse computability. (See [50] for details.)

The situation for generic reducibility is more complicated. The following question was originally asked for uniform generic reducibility, but it is open for the nonuniform version as well.

Open Question 8.4

(Jockusch and Schupp [61]; Igusa [57]). Is there a minimal pair in the (uniform or nonuniform) generic degrees?

One might expect that, as in the case of the coarse degrees, this question has a positive answer, which might perhaps be found by considering mutually random sets. However, if this is the case, then the proof will have to be significantly different from the one for the coarse degrees, because Igusa [57] showed that there are no minimal pairs for relative generic computability; that is, if A and B are not generically computable, then there is a C that is not generically computable but is generically computable relative both to A and to B. (A weaker form of this result, with the additional hypothesis that A and B are $\Delta ^0_2$, was proved by Downey, Jockusch, and Schupp [26].)

One approach to Question 8.4, suggested by Igusa [58], is to focus on the following question.

Open Question 8.5

(Igusa [58]). If A is not generically computable, must there be a B that is uniformly generically reducible to A such that B is not generically computable but has density 1?

Igusa [58] showed that answering this question in either direction would have consequences for the uniform dense degrees: a positive answer would imply that there are no minimal degrees (which is also an open question), while a negative answer would imply that there are minimal pairs. (For the nonuniform dense degrees, a positive answer to the analog of Question 8.5 would imply that there are no minimal degrees, by the same argument as in the uniform case, but for minimal pairs the situation is less clear, as the argument in [58] that a negative answer to Question 8.5 implies the nonexistence of minimal pairs appears to make essential use of uniformity.)

Cholak and Igusa [7] noted that Question 8.5 can be recast in terms of the relationship between generic and coarse degrees, because, as they showed, a (uniform or nonuniform) generic degree contains a coarsely computable set if and only if it contains a set of density 1.

At the time of writing, I am working with Eric Astor and Carl Jockusch on a paper [2] that reintroduces Meyer’s notion of asymptotic computability, which we call effective dense computability, and introduces another such notion, called dense computability.

Definition 8.6

A set A is densely computable if there is a partial computable function f such that $f(n)\mathord {\downarrow }=A(n)$ on a set of density 1.

A set A is effectively densely computable if there is a (total) computable function $f : \omega \rightarrow \{0,1,\square \}$ such that $\{n : f(n)=\square \}$ has density 0, and $f(n)=A(n)$ for all n outside this set.

It is easy to see that effective dense computability implies both generic and coarse computability, and that both generic and coarse computability imply dense computability. As mentioned above, generic and coarse computability are incomparable notions, so all of these implications are strict.

As with generic computability and coarse computability, one can define notions of reducibility associated with dense computability and effective dense computability, and corresponding degree structures. Eric, Carl, and I have shown that there are minimal pairs in the (uniform or nonuniform) dense degrees, but we do not know whether this is the case for the effective dense degrees. Settling this question seems likely to require methods similar to those needed to answer Question 8.4.

I had planned to finish with one more question in this area, but after the initial submission of this paper, I learned from Benoit Monin that he had recently solved it. I will still discuss it though, as I find his result quite lovely. Definitions of the classes of sets and degrees mentioned below can be found e.g. in [17].

To each notion of asymptotic computability, one can attach an asymptotic computability bound. The following two notions were introduced by Downey, Jockusch, and Schupp [26] and Hirschfeldt, Jockusch, McNicholl, and Schupp [51], respectively.

Definition 8.7

Say that A is partially computable at density r if there is a partial description f of A such that $\underline{\rho }({{\mathrm{dom}}}f) \geqslant r$. The partial computability bound of A is

$$\begin{aligned} \alpha (A) = \sup \{r : A\text { is partially computable at density}\, r\}. \end{aligned}$$

Say that A is coarsely computable at density r if there is a computable set C such that $\underline{\rho }(\{n : C(n)=A(n)\}) \geqslant r$. The coarse computability bound of A is

$$\begin{aligned} \gamma (A) = \sup \{r : A\text { is coarsely computable at density}\, r\}. \end{aligned}$$

Astor, Hirschfeldt, and Jockusch [2] have shown that the analogous notions for dense and effective dense computability are equivalent to the ones for coarse and generic computability, respectively.

As shown in [51], every hyperimmune degree contains a set A such that $\gamma (A)=0$. Andrews, Cai, Diamondstone, Jockusch, and Lempp [1] showed that the same is true of every PA degree. However, they also showed that there are degrees that do not contain any such sets. Two examples of such degrees given in that paper are the degrees of computably traceable sets, and the degrees of sets computable from a 1-random set of hyperimmune-free degree. In both cases, every set A in such degrees has $\gamma (A) \geqslant \frac{1}{2}$.

Definition 8.8

For a degree $\mathbf{a}$, let

$$\begin{aligned} \Gamma (\mathbf{a}) = \inf \{\gamma (A) : A \text { is }{} \mathbf{a}\text {-computable}\}. \end{aligned}$$

Hirschfeldt, Jockusch, McNicholl, and Schupp [51] showed that every nonzero degree contains a set A with $\gamma (A)=\frac{1}{2}$, so $\Gamma (\mathbf{a}) \leqslant \frac{1}{2}$ for all $\mathbf{a} \ne \mathbf{0}$, and the results mentioned above produce examples of degrees $\mathbf{a}$ with $\Gamma (\mathbf{a})=0$ and $\Gamma (\mathbf{a})=\frac{1}{2}$. Of course, $\Gamma (\mathbf{0})=1$. In the original version of this paper, I wrote that “[i]t would be remarkable if these are the only possible values of $\Gamma (\mathbf{a})$” and asked the following question from Andrews, Cai, Diamondstone, Jockusch, and Lempp [1]: Is it the case that $\Gamma (\mathbf{a})$ is always 0, $\frac{1}{2}$, or 1? If not, then what are the possible values of $\Gamma (\mathbf{a})$?

Andrews, Cai, Diamondstone, Jockusch, and Lempp [1] showed that if A is truth-table reducible to a 1-random set then $\gamma (A) \geqslant \frac{1}{2}$ (from which their result on 1-random sets of hyperimmune-free degree mentioned above follows immediately). Furthermore, the proof in [51] that every Turing degree contains a set A with $\gamma (A)=\frac{1}{2}$ works for tt-degrees as well. Thus it is also interesting to consider the values of

for tt-degrees $\mathbf{a}$. In the original version of this paper, I also asked the following question: Is it the case that is always 0, $\frac{1}{2}$, or 1? If not, then what are the possible values of ?

Monin [91] has completely answered these questions as follows, using notions developed by Monin and Nies [92] and techniques from the theory of error-correcting codes.

Theorem 8.9

(Monin [91]). The only possible values of $\Gamma (\mathbf{a})$ and are 0, $\frac{1}{2}$, and 1.