Problem #2

Martin's Conjecture

Open!!!

Restricted to Turing-invariant functions that are provably total in $\mathsf{ZFC}$ and not constant on a cone of Turing degrees, Martin's Conjecture proposes that every such function $f$ is, on a cone, equal to an iterate of the Turing jump: there is some ordinal $\alpha$ and a cone of degrees $\mathbf{x}$ on which

f(\mathbf{x}) = \mathbf{x}^{(\alpha)}.

The conjecture also proposes a well-founded structure ("Martin's Conjecture, part I") on the Turing-invariant functions ordered by eventual domination on a cone, refining this picture.

Suggest an edit

Reference for the problem statement

Donald A. Martin, (unpublished, circulated notes and problem lists; see Steel 1982 for context), 1982

Definitions

Turing degree: the equivalence class of a set $A \subseteq \omega$ under Turing equivalence $\le_T$ .
Cone of degrees: the set of degrees above some fixed degree $\mathbf{x}_0$ ; a property holds "on a cone" if it holds for all degrees above some $\mathbf{x}_0$ .
Turing jump, $\mathbf{x}^{(\alpha)}$ : the $\alpha$ -th iterate of the Turing jump operator applied to the degree $\mathbf{x}$ .
Turing-invariant function: a function $f$ on Turing degrees (or on reals, invariant under $\equiv_T$ ) satisfying $f(\mathbf{x}) \geq \mathbf{x}$ on a cone.

Known Partial Results

Slaman and Steel proved the conjecture for Borel functions in the "increasing" case.
The conjecture has been established for order-preserving functions under the Axiom of Determinacy in various restricted settings.
The general case, even for functions of low complexity, remains open.

Notes

Martin's Conjecture is often described as a precise version of the empirical observation that "naturally occurring" Turing degrees are always well-ordered by Turing reducibility, despite the existence of pathological, non-naturally-occurring counterexamples to a naive version of that statement.

Additional References

Steel, J. "Working Below a High Recursively Enumerable Degree." Journal of Symbolic Logic, 1982 (background on the cone-of-degrees framework Martin's conjecture is stated in).
Slaman, T. and Steel, J. "Definable functions on degrees." Cabal Seminar 81–85, 1988.
Montalbán, A. "Martin's conjecture: A classification of the naturally occurring Turing degrees." Notices of the AMS, 2019 (survey).

Comments

Loading comments…