Steel's uniformity conjecture: is every Turing-invariant function equal on a cone to a uniformly Turing-invariant function?

Steel's uniformity conjecture, posed around 1982 and recorded as Conjecture III of Slaman–Steel's Definable functions on degrees and as Conjecture 1.4 of Marks–Slaman–Steel, asks whether, under the axiom of determinacy, every Turing-invariant function $f: 2^\omega \to 2^\omega$ agrees in Turing degree with a uniformly Turing-invariant function on a cone of Turing degrees — that is, whether the computational reductions witnessing invariance can always be chosen independently of the particular reals involved. Martin's conjecture, the proposed classification of all natural degree-invariant functions as the iterates of the Turing jump, has been proved only for the uniform class, so the conjecture decides whether that hypothesis loses any generality. The problem is to prove the conjecture for all Turing-invariant functions, or to construct a Turing-invariant function that is not equivalent on any cone to any uniformly invariant one. The most recent literature — Day–Marks's paper published in June 2026 in Transactions of the AMS, Series B, and Cordero's October 2025 preprint — records the conjecture as open; Cordero refutes the analogous statement in the enumeration degrees, leaving the Turing-degree case as the surviving open core.

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 an algorithm permitted to consult the other as an oracle; the equivalence classes are the Turing degrees, and the induced preorder is Turing reducibility $\le_T$. A function $f : 2^\omega \to 2^\omega$ is Turing invariant (or degree invariant) if $x \equiv_T y$ implies $f(x) \equiv_T f(y)$ — exactly the condition for an oracle construction to induce a function on degrees. The Turing jump $x \mapsto x'$, sending a real to its relativized halting problem, is the basic example.

Martin's conjecture, proposed by D. A. Martin in the 1970s, attempts to classify all such functions. Its natural setting is ZF + DC + AD, where AD, the axiom of determinacy (every two-player infinite game with integer moves has a winning strategy for one of the players), implies Martin's cone theorem: every Turing-invariant set of reals either contains a Turing cone $\{x : x \ge_T c\}$ or is disjoint from one. Martin measure, which assigns measure 1 exactly to the sets containing a cone, is therefore a countably complete measure on the Turing-invariant sets, and 'a.e.' means 'on some cone'. For invariant functions write $f \le_m g$ if $f(x) \le_T g(x)$ a.e., and $f \equiv_m g$ if $f(x) \equiv_T g(x)$ a.e. Part I of Martin's conjecture asserts that every Turing-invariant $f$ is either constant a.e. or satisfies $f(x) \ge_T x$ on a cone; part II asserts that $\le_m$ prewellorders the increasing invariant functions, with the jump operation as successor. The conjecture, still open, is a precise form of the claim that the only natural degree-invariant functions are the transfinite iterates of the jump.

The one class in which Martin's conjecture is completely settled is the uniformly Turing-invariant functions. Say $x \ge_T y$ via $i$ if the $i$-th Turing functional computes $y$ from $x$, and $x \equiv_T y$ via $(i,j)$ if this holds in both directions; $f$ is uniformly Turing-invariant if there is a fixed map $u : \omega^2 \to \omega^2$ such that $x \equiv_T y$ via $(i,j)$ always implies $f(x) \equiv_T f(y)$ via $u(i,j)$ — the indices witnessing invariance are transformed independently of the reals themselves. Steel's 1982 paper established part II of Martin's conjecture for this class and Slaman–Steel's 1988 paper established part I. Steel then conjectured that the uniformity assumption loses nothing: under AD, every Turing-invariant $f$ is $\equiv_m$-equivalent to some uniformly Turing-invariant $g$. This is Conjecture III of Slaman–Steel's Definable functions on degrees and Conjecture 1.4 of Marks–Slaman–Steel's survey. By a standard argument recorded in the latter, it is equivalent to requiring that every Turing-invariant function be uniformly Turing-invariant on some pointed perfect set, meaning the set $[T]$ of infinite paths through a perfect subtree $T$ of $2^{<\omega}$ every path of which computes $T$.

The conjecture is a load-bearing part of the Martin-conjecture program rather than a side question. Marks–Slaman–Steel's Theorem 1.8 (credited to Slaman–Steel) shows that, restricted to Borel functions, it is equivalent to Martin's conjecture restricted to Borel functions; and since the uniform case is already fully classified, a positive answer in general would yield the full Martin's conjecture. In the other direction, a counterexample would be the first known genuinely non-uniform degree-invariant function, the very type of object at issue in Sacks's question whether Post's problem admits a degree-invariant solution: Lachlan showed there is no uniformly invariant such solution, so any solution would have to be non-uniform. Day–Marks connect possible counterexamples with a question Slaman–Steel posed in 1988, whether Turing equivalence is hyper-recursively-finite — that is, an increasing union of Borel equivalence relations no class of which contains an infinite sequence of reals uniformly computable from any one member of the class. The problem also has a descriptive-set-theoretic face: a countable Borel equivalence relation is a Borel (measurability-class) equivalence relation all of whose equivalence classes are countable, such as $\equiv_T$; a homomorphism between such relations is a map sending equivalent points to equivalent points, so a Turing-invariant function is exactly a homomorphism from $\equiv_T$ to itself, and the uniformity question asks whether every such homomorphism is a uniform one on a cone.

Problem Statement

Work in ZF + DC + AD. Let $f : 2^\omega \to 2^\omega$ be a Turing-invariant function, with no Borelness or other definability restriction. Steel's uniformity conjecture asks whether $f$ is Martin-equivalent to a uniformly Turing-invariant function:

$$\exists \, g : 2^\omega \to 2^\omega, \; \exists \, u : \omega^2 \to \omega^2, \; \exists \, c \in 2^\omega \;\; \Big( \forall x, y \in 2^\omega \, \forall i, j \in \omega : \; x \equiv_T y \text{ via } (i,j) \Rightarrow g(x) \equiv_T g(y) \text{ via } u(i,j) \Big) \;\wedge\; \Big( \forall x \in 2^\omega : \; x \ge_T c \Rightarrow f(x) \equiv_T g(x) \Big).$$

Here $x \equiv_T y$ via $(i,j)$ means that the $i$-th and $j$-th Turing functionals compute $y$ from $x$ and $x$ from $y$ respectively. Equivalently, in Steel's original formulation: is every Turing-invariant function uniformly Turing-invariant on some pointed perfect set?

The conjecture asserts that every Turing-invariant $f$ is Martin-equivalent to a uniformly Turing-invariant function — that is, that there are a uniformly Turing-invariant $g$ (with its uniformity map $u$) and a real $c$ such that $f(x) \equiv_T g(x)$ for every $x \ge_T c$. Its negation asserts that there is a Turing-invariant $f$ such that for every uniformly Turing-invariant $g$ and every real $c$ there is an $x \ge_T c$ with $f(x) \not\equiv_T g(x)$ — equivalently, that $f$ is not uniformly Turing-invariant on any pointed perfect set.

Any restriction of the class of functions (for instance to Borel $f$) is a strictly weaker derived problem, not the conjecture itself; the Borel subcase is separately known to be equivalent to Martin's conjecture for Borel functions.

References

1. John R. Steel, A classification of jump operators, Journal of Symbolic Logic 47(2) (1982), 347–358. DOI 10.2307/2273146, https://doi.org/10.2307/2273146
2. Theodore A. Slaman and John R. Steel, Definable functions on degrees, in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, Berlin (1988), pp. 37–55. DOI 10.1007/BFb0084969, https://doi.org/10.1007/BFb0084969
3. Andrew Marks, Theodore Slaman, and John 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; also arXiv:1109.1875. DOI 10.1017/CBO9781139519694.017, https://doi.org/10.1017/CBO9781139519694.017
4. Takayuki Kihara and Antonio Montalbán, The uniform Martin's conjecture for many-one degrees, Transactions of the American Mathematical Society 370(12) (2018), 9025–9044. DOI 10.1090/tran/7519, https://doi.org/10.1090/tran/7519; preprint arXiv:1608.05065, https://arxiv.org/abs/1608.05065
5. Andrew S. Marks, Uniformity, universality, and computability theory, Journal of Mathematical Logic 17(1) (2017), article 1750003. DOI 10.1142/S0219061317500039, https://doi.org/10.1142/S0219061317500039; preprint arXiv:1606.01976, https://arxiv.org/abs/1606.01976
6. Vittorio Bard, Uniform Martin's conjecture, locally, Proceedings of the American Mathematical Society 148 (2020), 5369–5380. DOI 10.1090/proc/15159, https://doi.org/10.1090/proc/15159; preprint arXiv:1907.10766, https://arxiv.org/abs/1907.10766
7. 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, https://doi.org/10.1090/btran/253; preprint arXiv:2004.00174, https://arxiv.org/abs/2004.00174
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(2) (2025), 319–367. DOI 10.1090/jams/1046, https://doi.org/10.1090/jams/1046; preprint arXiv:2305.19646, https://arxiv.org/abs/2305.19646
9. Antonio Nakid Cordero, Martin's Conjecture in the Enumeration Degrees, preprint (2025), arXiv:2510.19147, https://arxiv.org/abs/2510.19147
10. Patrick Lutz, Martin's conjecture for regressive functions on the hyperarithmetic degrees, Journal of Mathematical Logic 25(2) (2025), article 2450015. DOI 10.1142/S0219061324500156, https://doi.org/10.1142/S0219061324500156; preprint arXiv:2306.05746, https://arxiv.org/abs/2306.05746