The Turing automorphism problem: does a nontrivial automorphism of the Turing degrees exist?

The partial order $\mathscr{D}_{\mathbb{T}}$ of Turing degrees is the quotient of subsets of the natural numbers by Turing equivalence, ordered by Turing reducibility. Whether this structure admits a nontrivial automorphism — a bijection of the degrees that preserves the order in both directions and moves at least one degree — is a central and long-standing open problem of computability theory, posed as Question 1 in Kjos-Hanssen's study of a tractable case of the problem (arXiv:1908.05381; published 2025). That paper proves two tractable cases: permutations of $\omega$ induce only the trivial automorphism, and any homeomorphism of Cantor space that is a bi-uniformly $E_0$-invariant map ($E_0$ being equality modulo finite difference) induces only the trivial automorphism. The residual question — whether a nontrivial automorphism exists by any other means — is therefore exactly the classical automorphism problem. No resolution had been found as of August 2026: partial rigidity results stop at the cone above $\mathbf{0}''$, and the derived directions — extending the exclusion analysis beyond the bi-uniformly $E_0$-invariant class, and an analogous result for the degrees $\mathcal{D}_a$ of arithmetical reducibility explicitly suggested in the source's Remark 17 per a reported remark of Woodin — remain unexplored.

Background

A set $B$ of natural numbers is Turing reducible to a set $A$ ($B\le_T A$) if there is a single algorithm, allowed to consult $A$ as an oracle, that decides membership in $B$; $A$ and $B$ are Turing equivalent ($A\equiv_T B$) if each is reducible to the other. The Turing degrees $\mathscr{D}_{\mathbb{T}}$ are the $\equiv_T$-equivalence classes, partially ordered by $\le_T$. An automorphism of $\mathscr{D}_{\mathbb{T}}$ is a bijection $\pi$ with $x\le y\iff\pi(x)\le\pi(y)$ for all degrees $x,y$; it is trivial if $\pi(x)=x$ for every $x$. The Turing jump of a set is the halting problem relative to that set; iterating it from $\emptyset$ gives the degrees $\mathbf{0'},\mathbf{0''},\dots$, and a cone above a degree $\mathbf{b}$ is the set of all degrees $\ge\mathbf{b}$.

Whether $\mathscr{D}_{\mathbb{T}}$ has a nontrivial automorphism — the automorphism problem, or rigidity question, for the Turing degrees — has been open since the early study of the degree structure. Jockusch and Solovay (1977) showed that every jump-preserving automorphism is the identity above $\mathbf{0}^{(4)}$. Nerode and Shore (1980) showed that every automorphism is the identity on some cone. Slaman and Woodin strengthened this (see Slaman's 2008 survey and their online draft "Definability in Degree Structures", 2005): every automorphism is the identity on the cone above $\mathbf{0}''$, and the automorphism group of $\mathscr{D}_{\mathbb{T}}$ is countable. The source notes a structural obstacle to lowering the base of the cone further: as a relation on sets, Turing reducibility is $\Sigma^0_3$ but not $\Pi^0_2$ or $\Sigma^0_2$, so the natural induction cannot continue toward $\mathbf{0}$ in the way partial-rigidity arguments would need. In the opposite direction, S. Barry Cooper claimed in a 1997/98 University of Leeds preprint to construct a nontrivial automorphism, induced by a discontinuous function on Baire space $\omega^\omega$ (the set of infinite sequences of natural numbers, with the product topology); that claim was never independently verified.

The Slaman–Woodin framework analyzes automorphisms through representatives: functions $F$ on Cantor space $2^\omega$ (the set of infinite binary sequences, with the product topology) such that $x\equiv_T y\iff F(x)\equiv_T F(y)$ and the induced permutation of degrees is the given automorphism. Their draft proves, for instance, that every automorphism is represented by an arithmetically definable function on all of $2^\omega$, and by a continuous function (relative to a real parameter) on a comeager set of generic reals. Kjos-Hanssen's program rules out nontriviality for simple classes of representatives. His 2018 result (with a new and more general proof in the source paper) shows that no permutation $\theta$ of $\omega$ induces a nontrivial automorphism, where $\theta$ induces the automorphism via $A\mapsto A\circ\theta$, and the theorem in fact covers the degree structures $\mathcal{D}_r$ of any reducibility $\le_r$ between one-one reducibility $\le_1$ and Turing reducibility $\le_T$. The paper then treats a topological class. Let $E_0$ denote equality modulo finite difference ($X=^*Y$ iff $X(n)=Y(n)$ for all but finitely many $n$). A function $F:2^\omega\to2^\omega$ is uniformly $E_0$-invariant if for each $a$ there is a $b$ such that whenever $X$ and $Y$ agree from position $a$ onward, $F(X)$ and $F(Y)$ agree from position $b$ onward; $F$ is a bi-uniformly $E_0$-invariant homeomorphism if $F$ and $F^{-1}$ are both uniformly $E_0$-invariant (equivalently for the paper's purposes, $F$ is an $E_0$-isomorphism: $XE_0Y\iff F(X)E_0F(Y)$, with this two-sided uniformity). The main theorem (Theorem 15) shows that a homeomorphism of Cantor space with this property that induces an automorphism of $\mathcal{D}_r$ must be computable, so the automorphism it induces is trivial: a computable representative is everywhere degree-non-increasing, and applying the same to the inverse forces the identity. This subsumes the permutation case, since $A\mapsto A\circ\theta$ is a bi-uniformly $E_0$-invariant homeomorphism.

The paper closes with a remark attributed to Woodin (June 6, 2019): he and Slaman may have shown, in unpublished work from the 1990s, that every automorphism of $\mathcal{D}_a$ — the degrees of arithmetical reducibility, where $A\le_a B$ iff $A$ is arithmetically definable from $B$ — is represented outright by a continuous function. The author notes this "gives some extra interest in a possible future $\mathcal{D}_a$ version" of the results.

Problem Statement

The problem is the classical automorphism problem for the Turing degrees, stated as Question 1 in the source: does there exist a nontrivial automorphism of $\mathscr{D}_{\mathbb{T}}$ — a bijection $\pi:\mathscr{D}_{\mathbb{T}}\to\mathscr{D}_{\mathbb{T}}$ such that $x\le y\iff\pi(x)\le\pi(y)$ for all degrees $x,y$ and $\pi(x)\ne x$ for at least one degree? Equivalently, since the tractable cases are settled: does there exist a nontrivial automorphism that is not induced by any permutation of $\omega$ (excluded by Theorem 8 for every reducibility between $\le_1$ and $\le_T$) and not induced by any bi-uniformly $E_0$-invariant homeomorphism of Cantor space (excluded by Theorem 15)? A complete answer is either a construction of such an automorphism, with proof of well-definedness, order-preservation in both directions, and nontriviality, or a proof that every automorphism of $\mathscr{D}_{\mathbb{T}}$ is the identity. Two further questions, neither required for a complete answer to the main question, remain open: whether the exclusion extends beyond the bi-uniformly $E_0$-invariant class, and whether the analogous rigidity statement holds for the degrees $\mathcal{D}_a$ of arithmetical reducibility ($A\le_a B$ iff $A$ is arithmetically definable from $B$).

References

1. Bjørn Kjos-Hanssen, "A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms", arXiv:1908.05381 (v2, 2020), https://arxiv.org/abs/1908.05381
2. Bjørn Kjos-Hanssen, "A Tractable Case of the Turing Automorphism Problem: Bi-uniformly $E_0$-invariant Cantor Homeomorphisms", in J. Cummings, A. Marks, Y. Yang, L. Yu (eds.), Higher Recursion Theory and Set Theory, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, World Scientific, 2025, pp. 137-144, DOI 10.1142/9789819806584_0007, https://doi.org/10.1142/9789819806584_0007
3. Bjørn Kjos-Hanssen, "Permutations of the integers induce only the trivial automorphism of the Turing degrees", Bulletin of Symbolic Logic 24(2):165-174, 2018, DOI 10.1017/bsl.2018.15, https://doi.org/10.1017/bsl.2018.15
4. Carl G. Jockusch, Jr. and Robert M. Solovay, "Fixed points of jump preserving automorphisms of degrees", Israel Journal of Mathematics 26(1):91-94, 1977, DOI 10.1007/BF03007659, https://doi.org/10.1007/BF03007659
5. Anil Nerode and Richard A. Shore, "Reducibility orderings: theories, definability and automorphisms", Annals of Mathematical Logic 18(1):61-89, 1980, DOI 10.1016/0003-4843(80)90004-2, https://doi.org/10.1016/0003-4843(80)90004-2
6. Theodore A. Slaman, "Global properties of the Turing degrees and the Turing jump", in Computational Prospects of Infinity, Part I: Tutorials, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 14, World Scientific, 2008, pp. 83-101, DOI 10.1142/9789812794055_0002, https://doi.org/10.1142/9789812794055_0002
7. Theodore A. Slaman and W. Hugh Woodin, "Definability in Degree Structures", unpublished online draft dated 21 July 2005, https://math.berkeley.edu/~slaman/talks/sw.pdf
8. Iván Ongay-Valverde, "Sets of real numbers closed under Turing equivalence: applications to fields, orders and automorphisms", Archive for Mathematical Logic 62:843-869, 2023, DOI 10.1007/s00153-023-00865-7, https://doi.org/10.1007/s00153-023-00865-7 (preprint arXiv:2106.12660, https://arxiv.org/abs/2106.12660)
9. S. Barry Cooper, "The Turing universe is not rigid", University of Leeds Pure Mathematics Preprint Series 1997, no. 16 (revised February 1998), no DOI or arXiv ID; bibliographic details as documented in reference [1] of the source paper (arXiv:1908.05381)