The Slaman–Steel question: is Turing equivalence hyper-recursively-finite?

In 1988, after proving that Turing equivalence $\equiv_T$ on $2^\omega$ is not hyperfinite (not an increasing union of Borel equivalence relations with finite classes), Slaman and Steel posed the weaker question — their Question 6 — of whether $\equiv_T$ can be written as an increasing union of Borel subequivalence relations no class of which contains an infinite sequence of reals uniformly computable from a member of the class: is $\equiv_T$ hyper-recursively-finite? Day and Marks (Trans. Amer. Math. Soc. Ser. B 13 (2026), 379–402) proved that this question is equivalent to a general structural question about countable Borel equivalence relations: is every countable Borel equivalence relation hyper-Borel-finite? They showed that a positive answer would produce the first nonuniform degree-invariant functions, refuting analogues of Steel's conjecture and the conjecture that every universal countable Borel equivalence relation is uniformly universal, while the natural negative route (their Conjecture 6.1) would establish that Turing equivalence cannot be nontrivially approximated from below, a key step toward Martin's conjecture. The question remains open: measure and category arguments provably cannot decide it, and no located work resolves it.

Background

Two infinite binary sequences (reals) $x, y \in 2^\omega$ are Turing equivalent, written $x \equiv_T y$, when each is computable from the other by a Turing machine with oracle access to the other; $x \leq_T y$ denotes Turing reducibility. A finer variant, many-one reducibility $x \leq_m y$, requires a single computable map $\rho$ with $x(n) = y(\rho(n))$ for all $n$. The Turing jump $j(x) = x'$ is the canonical strictly increasing operator of the degree structure (the halting problem relative to $x$). A function $f: 2^\omega \to 2^\omega$ is Turing invariant if $x \equiv_T y$ implies $f(x) \equiv_T f(y)$.

Martin's conjecture, one of the central open problems of computability theory, classifies Turing invariant functions with respect to the cone filter: a Turing cone is a set of the form $\{x : x \geq_T c\}$ for a base real $c$, and under the axiom of determinacy (AD) these cones generate a countably complete ultrafilter (Martin measure) on the Turing degrees; the conjecture is normally stated for Borel invariant functions in ZFC and, under AD, for all invariant functions. It asserts that every Turing invariant $f$ is either constant on a cone or satisfies $f(x) \geq_T x$ on a cone, and that the invariant functions are prewellordered by eventual domination, the increasing ones being exactly the iterates of the jump. Steel's conjecture concerns uniformity: $f$ is uniformly Turing invariant if the invariance is witnessed by a fixed computable transformation of program indices (if $x \equiv_T y$ via programs $(i,j)$ then $f(x) \equiv_T f(y)$ via programs $u(i,j)$), and the conjecture predicts every invariant $f$ agrees on a cone with a uniformly invariant one. A pointed perfect set is a perfect (closed, without isolated points) set $P \subseteq 2^\omega$ all of whose elements compute some fixed real; uniformity typically holds on pointed perfect sets, where a single program works for all elements.

On the descriptive-set-theoretic side, a countable Borel equivalence relation (CBER) is a Borel equivalence relation on a standard Borel space all of whose classes are countable; the prototype is $E_0$, eventual equality of binary sequences. A CBER $E$ is hyperfinite if $E = \bigcup_n F_n$ for an increasing sequence of Borel subequivalence relations $F_0 \subseteq F_1 \subseteq \cdots$ each having finite classes; hyperfiniteness is the central structural notion of the field (Jackson–Kechris–Louveau). There is a universal CBER $E_\infty$ (for instance the orbit equivalence relation of the shift action of the countable free group), to which every CBER Borel reduces, and $E_\infty$ is not hyperfinite. In their 1988 paper 'Definable functions on degrees', Slaman and Steel proved that Turing equivalence itself — whose classes are countable but which is only analytic ($\Sigma^1_1$), not Borel — is not hyperfinite, and asked how far this failure extends.

Day and Marks isolate the exact content of that question. Given a countable sequence of Borel functions $f_i : X \to X^\omega$, a countable Borel equivalence relation $F$ on $X$ is $(f_i)$-finite if no $f_i(x)$ enumerates infinitely many distinct elements of the $F$-class of $x$; $E$ is hyper-$(f_i)$-finite if $E = \bigcup_n F_n$ for an increasing sequence of Borel subequivalence relations $F_n$, each $(f_i)$-finite; and $E$ is hyper-Borel-finite if this holds for every countable family $(f_i)$ of Borel functions $X \to X^\omega$. Taking for $f_i$ the functions producing the columns of the $i$-th Turing functional applied to $x$ ($f_i(x)(j) = \{n : \langle j, n \rangle \in \Phi_i(x)\}$ when $\Phi_i(x)$ is total, and $x$ otherwise) recovers exactly the Slaman–Steel property: $\equiv_T$ is hyper-recursively-finite if it is hyper-$(f_i)$-finite for this family. Their Theorem 3.5 shows the question self-strengthens: $\equiv_T$ is hyper-recursively-finite if and only if every CBER is hyper-Borel-finite (and equivalently, $E_\infty$ is hyper-$(f_i)$-finite for the specific shift-action family $f_i(x)(j) = \gamma_{i,j} \cdot x$ of the free group $\mathbb{F}_\omega = \langle \gamma_{i,j} \rangle_{i,j \in \omega}$ acting on $\omega^{\mathbb{F}_\omega}$, where $\gamma_{i,j} \cdot x$ is the image of $x$ under the generator $\gamma_{i,j}$). Intuitively, each $f_i(x)$ is a potential computable enumeration of an infinite subset of an equivalence class, and the question asks whether every CBER can be stratified into Borel layers that block all such enumerations.

The question is a bottleneck for the Martin's conjecture program. Any attempt to build a Turing invariant counterexample to Martin's conjecture by a countable stage construction automatically writes $\equiv_T$ as an increasing union of Borel equivalence relations (the stage-$n$ relation records the mutual coding completed by stage $n$), so the possible shapes of such unions govern the possible counterexamples. Day and Marks prove (Corollary 5.6) that a positive answer would yield a Borel $(\equiv_T, \equiv_m)$-invariant function that is not uniformly invariant on any pointed perfect set and is everywhere $\leq_m$-incomparable with the jump and its complement — refuting the many-one analogue of Steel's conjecture suggested by Kihara and Montalbán's uniform Martin's conjecture for many-one degrees — and would refute Marks's conjecture that every universal CBER is uniformly universal, since $\equiv_m$ would then be universal yet is known not to be uniformly universal. Conversely, their Conjecture 6.1 predicts a strong failure of approximability: every representation $\equiv_T = \bigcup_n E_n$ by increasing Borel equivalence relations stabilizes on some pointed perfect set ($E_i \restriction P = \equiv_T \restriction P$ for some $i$ and some pointed perfect $P$), which would make stage-by-stage counterexample constructions hopeless; they prove this implies Martin measure is $E_0$-ergodic (every Borel homomorphism from $\equiv_T$ to $E_0$ has constant $E_0$-class on a cone), and they note that an analogous non-approximability phenomenon is known in the probability-measure-preserving setting (Gaboriau–Tucker-Drob). The elementary techniques are provably insufficient: Theorem 3.8 shows every CBER is hyper-$(f_i)$-finite on a conull set for every Borel probability measure (and the Baire category analogue holds by generic hyperfiniteness), so measure and category arguments cannot refute hyper-Borel-finiteness — only the global (everywhere) statement can settle the question. Two neighboring open questions delimit the frontier: whether any non-hyperfinite CBER is hyper-Borel-finite at all (Day–Marks Question 3.2), and whether every CBER satisfying the Borel boundedness property of Boykin and Jackson (a boundedness condition on Borel functions measured along classes) is hyper-Borel-finite (Question 3.6).

Problem Statement

Determine whether Turing equivalence $\equiv_T$ on $2^\omega$ — the equivalence relation of mutual computability between infinite binary sequences, $x \equiv_T y$ iff each of $x$ and $y$ is computable from the other by an oracle Turing machine — is hyper-recursively-finite, in either of two equivalent published forms (the equivalence is Day–Marks, Theorem 3.5):

(1) The Slaman–Steel form: does there exist an increasing sequence $E_0 \subseteq E_1 \subseteq \cdots$ of Borel subequivalence relations of $\equiv_T$ with $\bigcup_n E_n = \equiv_T$ such that no $E_n$-class contains an infinite sequence of reals uniformly computable from one of its members? Formally, writing $\Phi_i$ for the $i$-th Turing functional (the $i$-th oracle program, which on input $x$ either diverges or computes a real $\Phi_i(x)$), let $f_i(x)(j) = \{n : \langle j, n \rangle \in \Phi_i(x)\}$ (the $j$-th column of the real $\Phi_i(x)$) when $\Phi_i(x)$ is total, and $f_i(x)(j) = x$ otherwise; there should be no $n$, $i$, and $x$ for which $\{f_i(x)(j) : j \in \omega\}$ is infinite and contained in the $E_n$-class of $x$.

(2) The equivalent countable Borel form: is every countable Borel equivalence relation (CBER) hyper-Borel-finite — that is, for every CBER $E$ (a Borel equivalence relation with countable classes) on a standard Borel space $X$ and every countable family of Borel functions $f_i : X \to X^\omega$, does there exist an increasing sequence of Borel subequivalence relations $F_0 \subseteq F_1 \subseteq \cdots$ with $\bigcup_n F_n = E$ such that no $F_n$-class contains an infinite set of the form $\{f_i(x)(j) : j \in \omega\}$?

Slaman and Steel posed the question in the setting of ZF+DC+AD (axiom of determinacy), and Day and Marks study it for Borel objects in ZFC while remarking that all their arguments adapt to AD.

References

1. A. Day and A. Marks, On a question of Slaman and Steel, Transactions of the American Mathematical Society, Series B 13 (2026), 379–402. DOI 10.1090/btran/253; arXiv:2004.00174. https://doi.org/10.1090/btran/253
2. T. A. Slaman and J. R. Steel, Definable functions on degrees, in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, Berlin (1988), 37–55. DOI 10.1007/bfb0084969. https://doi.org/10.1007/bfb0084969
3. T. Kihara and A. Montalbán, The uniform Martin's conjecture for many-one degrees, Transactions of the American Mathematical Society 370 (2018), 9025–9044. DOI 10.1090/tran/7519. https://doi.org/10.1090/tran/7519
4. A. S. Marks, Uniformity, universality, and computability theory, Journal of Mathematical Logic 17 (2017), no. 1, 1750003. DOI 10.1142/S0219061317500039. https://doi.org/10.1142/S0219061317500039
5. A. S. Marks, T. A. Slaman, and J. R. Steel, Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations, in Ordinal Definability and Recursion Theory: The Cabal Seminar Volume III, Lecture Notes in Logic 43, Cambridge University Press (2016), 493–520. DOI 10.1017/cbo9781139519694.017; arXiv:1109.1875. https://doi.org/10.1017/cbo9781139519694.017
6. S. Jackson, A. S. Kechris, and A. Louveau, Countable Borel equivalence relations, Journal of Mathematical Logic 2 (2002), no. 1, 1–80. DOI 10.1142/S0219061302000138. https://doi.org/10.1142/S0219061302000138
7. C. M. Boykin and S. Jackson, Borel boundedness and the lattice rounding property, in Advances in Logic, Contemporary Mathematics 425, American Mathematical Society, Providence, RI (2007), 113–126. DOI 10.1090/conm/425/08121. https://doi.org/10.1090/conm/425/08121
8. D. Gaboriau and R. Tucker-Drob, Approximations of standard equivalence relations and Bernoulli percolation at p_u, Comptes Rendus Mathématique 354 (2016), no. 11, 1114–1118. DOI 10.1016/j.crma.2016.09.011. https://doi.org/10.1016/j.crma.2016.09.011
9. P. Lutz and B. Siskind, Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions, Journal of the American Mathematical Society 38 (2025), no. 2, 319–367, published online April 2024. DOI 10.1090/jams/1046. https://doi.org/10.1090/jams/1046
10. P. Lutz, Martin's conjecture for regressive functions on the hyperarithmetic degrees, Journal of Mathematical Logic 25 (2025), no. 2, article 2450015, published online March 2024. DOI 10.1142/S0219061324500156. https://doi.org/10.1142/S0219061324500156
11. A. N. Cordero, Martin's Conjecture in the Enumeration Degrees, arXiv:2510.19147 (2025). https://arxiv.org/abs/2510.19147
12. C. Higgins, Measurable Brooks's theorem for directed graphs, Fundamenta Mathematicae (published online May 2026). DOI 10.4064/fm241107-7-4; arXiv:2405.00991. https://doi.org/10.4064/fm241107-7-4
13. A. Marks, D. Rossegger, and T. Slaman, Hausdorff dimension and countable Borel equivalence relations, Proceedings of the American Mathematical Society 154 (2026), no. 2, 883–892, published online November 2025. DOI 10.1090/proc/17496; arXiv:2410.22034. https://doi.org/10.1090/proc/17496
14. J. Grebík, A. S. Marks, V. Rozhoň, and F. Shinko, Borel dimension growth and hyperfiniteness, arXiv:2608.22565 (2026). https://arxiv.org/abs/2608.22565