The Slaman–Steel question: is Turing equivalence hyper-recursively-finite (equivalently, is every countable Borel equivalence relation hyper-Borel-finite)?

In 1988, in the same paper in which they proved that Turing equivalence is not hyperfinite, Slaman and Steel asked (their Question 6, in the setting of the axiom of determinacy) whether Turing equivalence $\equiv_T$ on $2^\omega$ is hyper-recursively-finite: can it be written as an increasing union of Borel subequivalence relations, none of whose classes contains an infinite sequence of distinct reals uniformly computable from one of its members? Day and Marks (2020, published 2026) proved this is equivalent to a purely descriptive-set-theoretic question: is every countable Borel equivalence relation hyper-Borel-finite, i.e. approximable from below by Borel subequivalence relations none of whose classes contains an infinite set enumerable by any countable family of Borel functions? They showed that measure and Baire category arguments cannot refute hyper-Borel-finiteness (it always holds on a conull set), and that a positive answer would produce the first nonuniform functions between degree structures, refute the $(\equiv_T,\equiv_m)$-analogues of Steel's conjecture, and make many-one equivalence a universal countable Borel equivalence relation that is not uniformly universal. No resolution has been found; the published 2026 version poses the question as open.

Background

Let $2^\omega$ denote Cantor space, the set of infinite binary sequences, the standard space of reals in computability theory. A real $x$ is Turing reducible to $y$ (written $x\le_T y$) if $x$ is computable by a Turing machine with oracle $y$, and $x$ and $y$ are Turing equivalent ($x\equiv_T y$) if each computes the other. Every $\equiv_T$-class is countable (there are only countably many programs), and $\equiv_T$ is a Borel equivalence relation, so it is a countable Borel equivalence relation (CBER): a Borel equivalence relation, on a standard Borel space, all of whose classes are countable. The structure theory of CBERs under Borel reducibility (a relation $E$ reduces to $F$ when some Borel map carries $E$-classes into $F$-classes) is a central chapter of descriptive set theory; its simplest nontrivial member is $E_0$, eventual equality of binary sequences. A CBER $E$ is hyperfinite if it is an increasing union $E=\bigcup_n F_n$ of Borel equivalence relations with finite classes (equivalently, induced by a Borel action of the integers; this characterization is due to Slaman–Steel and independently Weiss). Slaman and Steel proved in 1988 that $\equiv_T$ is not hyperfinite — indeed not hyperfinite on any pointed perfect set, where a pointed perfect set is the set of paths through a perfect tree $T$ (a tree whose path set is closed with no isolated points) such that every path $x$ through $T$ computes $T$ itself.

In the same 1988 paper ("Definable functions on degrees"), motivated by the observation that hyperfiniteness of $\equiv_T$ would allow one to construct counterexamples to Martin's conjecture, Slaman and Steel asked a natural weakening of hyperfiniteness. A Turing functional is an oracle Turing machine viewed as a partial function from reals to reals; let $\Phi_i$ be the $i$-th one, and write its output on oracle $x$, viewed as a subset of $\omega\times\omega$, in columns: the $j$-th column is $f_i(x)(j)=\{n:\langle j,n\rangle\in\Phi_i(x)\}$ (and $f_i(x)(j)=x$ if $\Phi_i(x)$ is not total). An infinite sequence of reals is uniformly computable from $x$ if it is such a sequence of columns. Turing equivalence is hyper-recursively-finite if $\equiv_T=\bigcup_n E_n$ for some increasing sequence of Borel subequivalence relations $E_n\subseteq E_{n+1}$ such that for every $n$, $x$, and $i$, the set $\{f_i(x)(j):j\in\omega\}$ is not an infinite set of distinct elements of the $E_n$-class of $x$ — that is, no approximating relation ever contains an entire infinite uniformly computable sequence inside one of its classes. Since $\equiv_T$ is not hyperfinite, in any such representation the relations $E_n$ cannot all have finite classes; the question is whether the computability-theoretic structure of $\equiv_T$ still permits an approximation from below that is "finite" relative to uniformly computable sequences.

Day and Marks introduced the corresponding notion for arbitrary CBERs. Given a countable family of Borel functions $f_i:X\to X^\omega$, a CBER $E$ on $X$ is hyper-$(f_i)$-finite if it admits such an increasing cover by Borel subequivalence relations $F_n$ with no $F_n$-class containing an infinite set of the form $\{f_i(x)(j):j\in\omega\}$; $E$ is hyper-Borel-finite if it is hyper-$(f_i)$-finite for every countable family of Borel functions $f_i:X\to X^\omega$. Day and Marks proved (Theorem 3.5) that $\equiv_T$ is hyper-recursively-finite if and only if every CBER is hyper-Borel-finite — the transfer maps an arbitrary CBER with its Borel functions into $\equiv_T$ via iterated Turing jumps at computable ordinals — so the 1988 computability-theoretic question and a general classification question for CBERs are one and the same problem. (They note the equivalent statement for the universal CBER $E_\infty$, the orbit equivalence relation of the shift action of the countable free group, to which every CBER Borel reduces.)

The question is significant because of Martin's conjecture, the central open problem of degree theory: under the axiom of determinacy (AD), every Turing-invariant function $f:2^\omega\to2^\omega$ is constant on a Turing cone (the set of reals computing some fixed base real $c$) or satisfies $f(x)\ge_T x$ on a cone, and the increasing such functions are, on a cone, exactly the iterates of the Turing jump $j(x)=x'$ (which computes the halting problem relative to $x$). The natural strategy for building a counterexample constructs $f$ in countably many stages, and the stage-$n$ relation "the values of $f$ on $x$ and $y$ have been coded into each other by stage $n$" exhibits $\equiv_T$ as an increasing union of Borel equivalence relations — so the feasibility of this strategy is governed by exactly the kind of approximation Slaman and Steel asked about. Day and Marks sharpened both directions. A positive answer would imply (Corollary 5.6) that many-one equivalence $\equiv_m$ on $2^\omega$ (where $x\le_m y$ iff $x(n)=y(\rho(n))$ for all $n$, for some total computable function $\rho:\omega\to\omega$) is a universal CBER — one to which every CBER Borel reduces — that is not uniformly universal (uniform universality is a strengthening of universality for which Marks conjectured equivalence with universality), and would give Borel $(\equiv_T,\equiv_m)$-invariant functions $f$ — functions with $x\equiv_T y$ implying $f(x)\equiv_m f(y)$ — that are not uniformly invariant (invariance witnessed by fixed computable programs) on any pointed perfect set and are $\le_m$-incomparable with the Turing jump and its complement on every cone, refuting the analogues of Steel's conjecture suggested by Kihara and Montalbán's correspondence between uniformly invariant functions and Wadge degrees (the degrees of sets of reals under continuous many-one reductions). A negative answer is expected to come from Day–Marks Conjecture 6.1 — every increasing Borel cover of $\equiv_T$ agrees with $\equiv_T$ on some pointed perfect set — which would also imply $E_0$-ergodicity of Martin measure (the $\{0,1\}$-valued measure on the Turing-invariant sets under AD, whose measure-one sets are exactly those containing a Turing cone), in the sense that every Borel homomorphism from $\equiv_T$ to $E_0$ has constant $E_0$-class on a cone.

Two known technical constraints shape any attack. First, every hyperfinite CBER is trivially hyper-Borel-finite, but by Day–Marks Theorem 3.8, for every CBER $E$, every family $(f_i)$, and every Borel probability measure $\mu$, the restriction of $E$ to some $\mu$-conull Borel set is hyper-$(f_i)$-finite (with the analogous statement for Baire category, via generic hyperfiniteness — the fact that every CBER is hyperfinite on a comeager set): measure and category arguments can never refute hyper-Borel-finiteness, so a negative answer must fail on a null set. Second, the simplest style of witness — covering the space by an increasing sequence of Borel sets and restricting — provably cannot work for $\equiv_T$, since some member of any such cover contains a pointed perfect set, and $\equiv_T$ restricted to a set containing a pointed perfect set contains a uniformly computable infinite sequence inside a single class.

Problem Statement

Determine whether Turing equivalence is hyper-recursively-finite, in either of two provably equivalent forms.

(1) Computability-theoretic form (Slaman–Steel 1988, Question 6, posed under AD; Day–Marks Question 3.4): does there exist an increasing sequence $E_0\subseteq E_1\subseteq\dots$ of Borel subequivalence relations of $\equiv_T$ on $2^\omega$ with $\bigcup_n E_n=\equiv_T$, such that for every $n$, every $x\in 2^\omega$, and every $i\in\omega$, the set $\{f_i(x)(j):j\in\omega\}$ is not an infinite set of distinct elements of the $E_n$-class of $x$? Here $f_i(x)(j)$ is the $j$-th column of the output of the $i$-th Turing functional (oracle Turing machine) $\Phi_i$ on oracle $x$, viewed as a subset of $\omega\times\omega$: $f_i(x)(j)=\{n:\langle j,n\rangle\in\Phi_i(x)\}$ if $\Phi_i(x)$ is total, and $f_i(x)(j)=x$ otherwise.

(2) Descriptive-set-theoretic form (Day–Marks Question 3.3, equivalent to (1) by Theorem 3.5): is every countable Borel equivalence relation $E$ on a standard Borel space $X$ hyper-Borel-finite — that is, for every countable family $(f_i)_{i\in\omega}$ of Borel functions $f_i:X\to X^\omega$, does there exist an increasing sequence $F_0\subseteq F_1\subseteq\dots$ of Borel subequivalence relations of $E$ with $\bigcup_n F_n=E$, such that for every $n$, $i$, and $x$, the set $\{f_i(x)(j):j\in\omega\}$ is not an infinite subset of the $F_n$-class of $x$?

A complete answer in either direction — a proof of (1)/(2) or a refutation of (1)/(2) — resolves the problem. The original question was posed in the setting of the axiom of determinacy; Day–Marks work in the Borel setting and note that all their arguments adapt to AD, so answers in either setting (or a separation between the two settings) are admissible. A refutation may proceed either directly for $\equiv_T$ or by exhibiting a countable Borel equivalence relation that is not hyper-Borel-finite; the two formulations are equivalent by Day–Marks Theorem 3.5.

References

1. Adam R. Day and Andrew S. 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://arxiv.org/abs/2004.00174
2. Theodore A. Slaman and John R. Steel, "Definable functions on degrees", in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, 1988, pp. 37–55, DOI 10.1007/bfb0084969, https://doi.org/10.1007/bfb0084969 (origin of the question, posed as Question 6 under AD)
3. Andrew S. Marks, Theodore A. Slaman, and John 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, pp. 493–520, DOI 10.1017/CBO9781139519694.017, https://doi.org/10.1017/CBO9781139519694.017; arXiv:1109.1875, https://arxiv.org/abs/1109.1875 (background on Martin's conjecture and CBERs)
4. Takayuki Kihara and Antonio 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, arXiv:1608.05065, https://arxiv.org/abs/1608.05065 (correspondence between uniformly invariant functions and Wadge degrees)
5. Cecelia Higgins, "Measurable Brooks's theorem for directed graphs", Fundamenta Mathematicae (2026), DOI 10.4064/fm241107-7-4, arXiv:2405.00991, https://arxiv.org/abs/2405.00991 (adjacent work on measurable graph coloring)
6. Andrew Marks, Dino Rossegger, and Theodore Slaman, "Hausdorff dimension and countable Borel equivalence relations", Proceedings of the American Mathematical Society 154 (2026), no. 2, 883–892, DOI 10.1090/proc/17496, https://doi.org/10.1090/proc/17496; arXiv:2410.22034, https://arxiv.org/abs/2410.22034 (adjacent canonization result)
7. Patrick Lutz, "Martin's conjecture for regressive functions on the hyperarithmetic degrees", Journal of Mathematical Logic 25 (2025), no. 2, article 2450015, DOI 10.1142/S0219061324500156, https://doi.org/10.1142/S0219061324500156; arXiv:2306.05746, https://arxiv.org/abs/2306.05746 (answers a different Slaman–Steel question)
8. Patrick Lutz and Benjamin 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, DOI 10.1090/jams/1046, https://doi.org/10.1090/jams/1046; arXiv:2305.19646, https://arxiv.org/abs/2305.19646 (adjacent Martin's conjecture progress)
9. Antonio Nakid Cordero, "Martin's Conjecture in the Enumeration Degrees", arXiv:2510.19147 (2025), https://arxiv.org/abs/2510.19147 (adjacent degree-structure work)
10. Jan Grebík, Andrew S. Marks, Václav Rozhoň, and Forte Shinko, "Borel dimension growth and hyperfiniteness", arXiv:2608.22565 (2026), https://arxiv.org/abs/2608.22565 (adjacent hyperfiniteness work)