Is the collection of bi-hyperhyperimmune Turing degrees the spectrum of a structure?

Andrews, Gerdes, and Miller characterized the bi-hyperhyperimmune (bi-hhi) Turing degrees — those containing a set that both contains and avoids a member of every disjoint weak array — as exactly the degrees that compute a function not dominated by any $\Delta^0_2$ function, equivalently the degrees that compute a weakly 2-generic binary sequence; in particular this class is closed upwards, the basic necessary condition for being the degree spectrum of a countable structure. They settled negatively the suggestion of Csima and Kalimullin that a specific graph $\mathcal{H}$ has spectrum exactly the bi-hhi degrees, and posed the surviving question (their Question 4.4): is the collection of bi-hyperhyperimmune Turing degrees the spectrum of some structure? No construction or impossibility proof is known in the literature; the question remains open as of 2026.

Background

In computability theory, the information content of a set $X \subseteq \omega$ of natural numbers is measured by its Turing degree: $X \leq_T Y$ means a machine with oracle $Y$ can decide membership in $X$, and $\mathrm{deg}(X)$ is the equivalence class of $X$ under mutual computability. A set is computably enumerable (c.e.) if it can be effectively listed. Immunity properties grade how strongly an infinite set resists effective approximation, and they lift to degrees: a degree has the property if some set of that degree has it. A weak array is a uniformly c.e. sequence $\mathcal{A} = \{F_n\}_{n \in \omega}$ of finite sets; it is disjoint if its members are pairwise disjoint. An infinite set is hyperhyperimmune if every disjoint weak array has a member disjoint from it; Andrews, Gerdes, and Miller call a set bi-hyperhyperimmune (bi-hhi) if, for every disjoint weak array, it both contains some member (as a subset) and avoids some member (has empty intersection with it) — that is, the set and its complement are both hyperhyperimmune. A Turing degree is bi-hhi if it contains a bi-hhi set.

A function $f : \omega \to \omega$ is $\Delta^0_2$ if it is computable from the halting problem $\emptyset'$; $f$ dominates $g$ if $f(n) \geq g(n)$ for all but finitely many $n$; and $f$ is $\Delta^0_2$-escaping if no $\Delta^0_2$ function dominates it. A set $S$ of finite binary strings is dense if every string has an extension in $S$, and $X \in 2^\omega$ is weakly 2-generic if for every dense $\Sigma^0_2$ set of strings, some prefix of $X$ lies in $S$. The main theorem of Andrews, Gerdes, and Miller (Theorem 1.1) states that for a Turing degree $\mathbf{d}$ the following are equivalent: $\mathbf{d}$ computes a $\Delta^0_2$-escaping function; $\mathbf{d}$ computes a weakly 2-generic sequence; $\mathbf{d}$ contains a blockwise hyperhyperimmune set; $\mathbf{d}$ contains a blockwise bi-hyperhyperimmune set; and $\mathbf{d}$ contains a bi-hyperhyperimmune set (the blockwise variants demand containment or avoidance of the whole interval between the least and greatest element of a finite set). This is the two-jump analogue of Kurtz's classical theorem that the hyperimmune degrees are exactly the degrees containing a weakly 1-generic, and it implies that the bi-hhi degrees are closed upwards (Corollary 1.2) — the property that had been the missing prerequisite for even posing a spectrum question about this class.

The degree spectrum of a countable structure $\mathcal{A}$ in a computable language is $\mathrm{DgSp}(\mathcal{A}) = \{\mathrm{deg}(\mathcal{B}) : \mathcal{B} \cong \mathcal{A}, \mathrm{dom}(\mathcal{B}) = \omega\}$, the set of Turing degrees of presentations of $\mathcal{A}$; the choice of language is immaterial, since standard effective codings (for example into graphs) preserve degree spectra. Knight proved that every degree spectrum is either the singleton of the computable degree (the trivial case) or closed upwards, so upward closure is a necessary condition for a degree class to be a spectrum. Csima and Kalimullin initiated the study of which degree classes defined by immunity or domination are spectra: the hyperimmune degrees form a spectrum, and they built a countable graph $\mathcal{H}$, a disjoint union of components (each an $\omega$-chain decorated with cycles coding a finite set) ranging over disjoint weak arrays, every degree computing a copy of which is bi-hhi; they suggested that $\mathrm{DgSp}(\mathcal{H})$ might be exactly the bi-hhi degrees, while noting that even upward closure of the class was then open. In the surrounding literature, Diamondstone, Greenberg, and Turetsky proved that the array non-recursive degrees (those computing a function that escapes domination by the modulus function of $\emptyset'$), the non-jump-traceable degrees (jump traceability is a lowness notion requiring every partial function computed from a set to admit small uniformly c.e. traces), and the degrees computing a function not dominated by any $\omega$-computably-approximable function (a function with a computable approximation whose number of mind changes is computably bounded) are all degree spectra of countable structures, while Andrews and Miller proved that the PA degrees (degrees of complete consistent extensions of Peano arithmetic) and the upward closure of the 1-random (Martin-Löf random) degrees are not spectra of any structure. Against this backdrop, Andrews, Gerdes, and Miller answered Csima and Kalimullin's suggestion negatively: computing a copy of $\mathcal{H}$ requires deciding a $\Pi^0_3$-complete index set, so every degree in $\mathrm{DgSp}(\mathcal{H})$ is $\mathrm{high}_2$ (its double jump computes $\mathbf{0}'''$), whereas a 2-generic degree below $\emptyset''$ is bi-hhi with double jump only $\emptyset''$. Their Question 4.4 then asks whether the bi-hhi degrees are realized by some other structure.

Problem Statement

Andrews, Gerdes, and Miller's Question 4.4, verbatim: 'Is the collection of bi-hyperhyperimmune Turing degrees the spectrum of a structure?' Equivalently, let $\mathcal{C}$ be the class of Turing degrees $\mathbf{d}$ such that $\mathbf{d}$ computes a function not dominated by any $\Delta^0_2$ function — which, by Theorem 1.1 of Andrews, Gerdes, and Miller, is the same as the class of degrees computing a weakly 2-generic sequence, and as the class of degrees containing a bi-hyperhyperimmune set. Does there exist a countable structure $\mathcal{A}$, in a computable language, with $\mathrm{DgSp}(\mathcal{A}) = \mathcal{C}$? An affirmative answer exhibits such a structure together with both inclusions — every degree in $\mathcal{C}$ computes a copy of $\mathcal{A}$, and every degree computing a copy of $\mathcal{A}$ lies in $\mathcal{C}$ — while a negative answer proves that no countable structure has degree spectrum exactly $\mathcal{C}$. The target is the full class $\mathcal{C}$, not a proper subclass such as the spectrum of Csima and Kalimullin's graph $\mathcal{H}$ (contained in the $\mathrm{high}_2$ degrees).

References

1. Uri Andrews, Peter Gerdes, Joseph S. Miller, 'The degrees of bi-hyperhyperimmune sets', Annals of Pure and Applied Logic 165(3):803-811, 2014. DOI: 10.1016/j.apal.2013.10.004, https://doi.org/10.1016/j.apal.2013.10.004
2. Barbara F. Csima, Iskander S. Kalimullin, 'Degree spectra and immunity properties', Mathematical Logic Quarterly 56(1):67-77, 2010. DOI: 10.1002/malq.200910001, https://doi.org/10.1002/malq.200910001
3. David Diamondstone, Noam Greenberg, Daniel Turetsky, 'Natural large degree spectra', Computability 2(1):1-8, 2013. DOI: 10.3233/COM-13008, https://doi.org/10.3233/COM-13008
4. Uri Andrews, Joseph S. Miller, 'Spectra of theories and structures', Proceedings of the American Mathematical Society 143(3):1283-1298, 2014. DOI: 10.1090/S0002-9939-2014-12283-0, https://doi.org/10.1090/S0002-9939-2014-12283-0
5. Uri Andrews, Mingzhong Cai, Iskander Sh. Kalimullin, Steffen Lempp, Joseph S. Miller, Antonio Montalban, 'The complements of lower cones of degrees and the degree spectra of structures', Journal of Symbolic Logic 81(3):997-1006, 2016. DOI: 10.1017/jsl.2015.59, https://doi.org/10.1017/jsl.2015.59
6. Julia F. Knight, 'Degrees coded in jumps of orderings', Journal of Symbolic Logic 51(4):1034-1042, 1986. DOI: 10.2307/2273915, https://doi.org/10.2307/2273915
7. Stuart A. Kurtz, 'Notions of weak genericity', Journal of Symbolic Logic 48(3):764-770, 1983. DOI: 10.2307/2273469, https://doi.org/10.2307/2273469
8. Laurent Bienvenu, Christopher P. Porter, 'On the interplay between effective notions of randomness and genericity', Journal of Symbolic Logic 84(1):393-407, 2019. DOI: 10.1017/jsl.2018.53, https://doi.org/10.1017/jsl.2018.53 (arXiv:1804.09774)
9. Peter M. Gerdes, 'A $\Pi^0_2$ singleton of minimal arithmetic degree', Journal of Symbolic Logic 91(1):336-368, 2026. DOI: 10.1017/jsl.2024.23, https://doi.org/10.1017/jsl.2024.23 (arXiv:2308.12102)
10. Iskander Sh. Kalimullin, V. L. Selivanov, A. N. Frolov, 'Degree spectra of structures', Journal of Mathematical Sciences 256(2):143-159, 2021. DOI: 10.1007/s10958-021-05424-0, https://doi.org/10.1007/s10958-021-05424-0
11. Peter Hertling, Philip Janicki, 'Strong Kurtz randomness and binary expansions of reordered computable numbers', preprint, 2025 (revised June 2026). arXiv:2509.22406, https://arxiv.org/abs/2509.22406