The ordering of computational difficulty has no hidden symmetries

← All digests

Family 241 · Mathematical logic
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-21

1. The question

Imagine sorting all sets of natural numbers by how much computational information they contain. One set is below another if a computer given answers about the second can decide membership in the first.

After identifying sets with exactly the same computational power, we obtain the Turing degrees. Could their entire ordering be relabelled nontrivially while preserving every comparison? Such a relabelling would be a hidden symmetry of relative computation.

Family 241 contains a manuscript dated 24 September 2026 claiming that no such symmetry exists. Every order automorphism of the full Turing-degree structure is the identity. The statement is in ZFC and places no definability or regularity assumption on the automorphism itself.

2. Background and essential definitions

Oracles and degrees

An oracle Turing machine is an ordinary algorithm allowed to ask membership questions about a fixed set $B\subseteq\mathbb N$. Write $A\leq_TB$ if some such machine decides membership in $A$ using oracle $B$.

This is a comparison of available information, not running time. A reduction may take arbitrarily long finite time on successive inputs.

Two sets are Turing equivalent when each computes the other. A Turing degree is an equivalence class under this relation. Let $\mathcal D_T$ denote the degrees, ordered by reducibility. The least degree $\mathbf0$ consists of computable sets.

The join $A\oplus B$ combines two oracles, for example by putting membership bits of $A$ in even positions and those of $B$ in odd positions. On degrees it gives a least upper bound, written $\mathbf a\vee\mathbf b$. An automorphism of the order must preserve these joins because least upper bounds are determined by the order alone.

The Turing jump $\mathbf a'$ is the degree of the halting problem for machines using an oracle of degree $\mathbf a$. Iteration gives $\mathbf0'$, $\mathbf0''$, and higher jumps. A cone above $\mathbf c$ consists of every degree $\mathbf a\geq_T\mathbf c$.

Rigidity

An order automorphism is a bijection $\pi:\mathcal D_T\to\mathcal D_T$ satisfying

$$\mathbf a\leq_T\mathbf b \quad\Longleftrightarrow\quad \pi(\mathbf a)\leq_T\pi(\mathbf b).$$

Rigidity says that $\pi(\mathbf a)=\mathbf a$ for every degree. It concerns the full partial order, not only computably enumerable degrees, a fixed interval or a restricted class of effectively described relabellings.

A topological notion of typicality

The proof uses Baire category. A nowhere-dense set has closure containing no open region. A meager set is a countable union of nowhere-dense sets; a comeager set is its complement. In a complete metric space, a comeager set is topologically large.

This is different from probability-one behavior. The argument removes auxiliary parameters using category, without assigning a probability distribution to them.

A Borel function has inverse images of open sets belonging to the sigma-algebra generated by open sets. Such functions have enough regularity to become continuous after restriction to a suitable comeager subset. This does not mean they are continuous at every point of the original space.

3. Development history and previous partial results

Turing introduced oracle computation in his 1939 work on systems of logic based on ordinals. The degree structure subsequently became a central object of computability theory: it organizes what can be computed relative to what, without retaining a preferred presentation of each oracle.

The automorphism problem gradually became more constrained. Jockusch and Solovay showed that every jump-preserving order automorphism fixes all degrees above $\mathbf0^{(4)}$. Shore and Slaman later proved that the jump is definable from the degree ordering, using Slaman–Woodin’s definability of the double jump. Consequently, jump preservation is automatic for order automorphisms.

Nerode and Shore proved that every automorphism fixes some cone, though the cone could depend on the automorphism. Slaman and Woodin obtained a common fixed cone: every automorphism fixes every degree above $\mathbf0''$. They also showed that the automorphism group is countable and developed arithmetic representations of its elements.

These results leave a sharp remaining question. Fixing all sufficiently high degrees does not by itself force every lower degree to be fixed. A nontrivial automorphism might act only outside the known fixed cone while preserving all comparisons with it.

The new paper uses an external theorem from Slaman and Woodin’s unpublished 2005 manuscript Definability in Degree Structures, also presented in Slaman’s later account. In the all-input form cited by the paper, every arbitrary degree automorphism has one arithmetic function on sets of integers that induces it at every input. The all-input scope is important; a representation only on generic inputs would be a different premise.

There are also methodological predecessors involving recovery of real parameters. Groszek–Slaman and Lutz–Siskind recover reals from finitely many branches of perfect sets under appropriate hypotheses. Kjos-Hanssen proved rigidity for automorphisms induced by permutations of the natural numbers, using parameter recovery and a measure cone theorem. The present manuscript claims a different recovery mechanism based on addition and Baire category, applicable to representatives of arbitrary degree automorphisms.

4. What the new manuscripts claim

The main theorem is

$$\operatorname{Aut}(\mathcal D_T,\leq_T)=\{\mathrm{id}\}.$$

No effective presentation, continuity, Borelness or arithmetic definition is required of $\pi$ in this statement. The cited representation theorem supplies regularity on the level of chosen oracle representatives.

The manuscript also gives a recovery theorem that is stated independently of automorphisms. Encode a real number $x$ by its strict rational cut $C(x)$, the set of indices of rational numbers below $x$. Suppose

$$F:\mathbb R\longrightarrow2^{\mathbb N}$$

is Borel, has countable fibers, and satisfies

$$F(x+y)\leq_T F(x)\oplus F(y) \quad\text{for all }x,y\in\mathbb R.$$

Countable fibers means that each output has at most countably many real preimages. For any irrational $t\in(0,1)$, the theorem claims that for a comeager set of pairs $(u,v)$, some rational $\delta\in(0,1)$ gives

$$\begin{aligned} C(t)\leq_T {}&F(u)\oplus F(u-v)\\ &\oplus F(v-u+\delta t)\\ &\oplus F(v-u+\delta(t-1)). \end{aligned}$$

The four displayed values are the only real oracles used. Program indices and rational constants may depend on the particular parameters; the theorem does not claim an effective uniform selection of them.

Finally, the paper derives the Slaman–Woodin biinterpretability conjecture from their established equivalence with rigidity. In that precise formulation, the degree order and full second-order arithmetic can be interpreted in each other without parameters, including a definable relation matching a coded set of integers to its Turing degree.

5. Why the advance matters

Importance: 5/5, provisional. Rigidity would settle a foundational question about whether the abstract order of relative computational power retains enough information to distinguish every degree.

The biinterpretability consequence strengthens the significance: through the cited equivalence, the result connects the apparently sparse language of one partial order with the much richer structure of natural numbers and all their subsets.

The recovery theorem is also a concrete proposed mechanism. It extracts one real parameter from four outputs of a function constrained only by Borel regularity, countable fibers and an addition reducibility relation.

This score does not mean that every degree has a short explicit definition, or that an algorithm can identify arbitrary degrees. Rigidity and effective classification are different notions. The definability consequence uses the specific Slaman–Woodin equivalence, not a general principle that every rigid structure has all elements individually definable.

6. The main idea

Represent the automorphism by a Borel function

For an arbitrary automorphism $\pi$, the cited theorem gives an arithmetic representative $\widehat F$ on subsets of $\mathbb N$, with output degree $\pi([A]_T)$ on every input $A$.

Compose with rational-cut coding to obtain $F(x)=\widehat F(C(x))$. This is Borel. Each fiber is countable because all its inputs have the same Turing degree, and a fixed oracle can compute only countably many sets through the countably many programs.

Real addition is computable at the level of degree bounds. Since $\pi$ preserves joins, the resulting $F$ satisfies the addition inequality required by the recovery theorem.

Encode the parameter in a bounded walk

Start with a real state $s_0=0$. At each stage choose one of two increments,

$$\delta t\quad\text{or}\quad\delta(t-1),$$

recording the choice by $r_n=0$ or $r_n=1$, respectively. After $N$ steps,

$$s_N=\delta\left(Nt-\sum_{n<N}r_n\right).$$

If the states remain bounded in absolute value by one, then

$$\left|t-\frac1N\sum_{n<N}r_n\right|<\frac1{N\delta}.$$

The average of the binary choices therefore recovers $t$ with an effective error bound. Because $t$ is irrational, sufficiently accurate approximations eventually answer every rational-cut query.

The challenge is to compute the choices without having $t$ as an oracle. Countable fibers and continuity on a comeager restriction supply an output bit that takes different values near two positions. Testing that bit of $F(u+s_n)$ forces the walk inward near the two endpoints. Its behavior in the middle need not be monotone.

Four fixed values update the walk

Borel regularity also supplies two addition programs that remain fixed along the selected recurrence. One moves from the neighborhood of $u$ to that of $v$, adding the chosen increment; the other returns to the neighborhood of $u$.

The initial value, return value and two possible increment values are exactly the four oracles in the theorem. Recursive substitution of these programs computes the next tested bit from the previous ones.

The algorithm computes the choices $r_n$, not the numerical states $s_n$. This avoids silently supplying the unknown real parameter as extra information. There is no asserted running-time bound; each requested bit is obtained after a finite computation.

Remove the auxiliary reals

Let $d(x)$ be the degree of $C(x)$. The four arguments are rational affine combinations of $t,u,v$, so recovery implies, after applying the inverse automorphism,

$$\pi^{-1}(d(t))\leq_Td(t)\vee d(u)\vee d(v)$$

for a comeager set of pairs.

A relative category cone-avoidance theorem says that if a fixed set is not computable from a fixed oracle, the pairs of auxiliary reals that make it computable form only a meager set. Thus the displayed comeager recovery forces

$$\pi^{-1}(d(t))\leq_Td(t).$$

Every noncomputable degree has an irrational representative of this kind, and the computable degree is automatically fixed. Applying the same argument to $\pi^{-1}$, and using order preservation, gives both inequalities between $\pi(\mathbf a)$ and $\mathbf a$. Antisymmetry yields equality.

7. Scope, limitations, and open questions

The claim covers arbitrary automorphisms of the full degree order. The proof’s regularity comes from the all-input representation theorem, which is an essential external dependency and is explicitly attributed to the 2005 Slaman–Woodin manuscript.

The representing Borel function need not be injective and need not have a functional inverse. The final symmetry argument represents the inverse degree automorphism separately.

Comeager recovery is topological, not a probability-one statement. The reductions may vary with the auxiliary pair, which the category-avoidance argument allows by ranging over all program indices.

The theorem does not give an efficient procedure for comparing arbitrary Turing degrees or computing the recovered parameter without its four oracles. Questions about automorphisms of other reducibility structures or restricted degree substructures are not automatically settled by full Turing-degree rigidity.

8. Sources and further reading

Turing, Systems of logic based on ordinals, Proceedings of the London Mathematical Society 45 (1939), 161–228, introduces oracle computation. Shore and Slaman, Defining the Turing jump, Mathematical Research Letters 6 (1999), 711–722, gives the jump-definability theorem.

Slaman and Woodin, Definability in Degree Structures, unpublished manuscript dated 21 July 2005, is the source cited for the all-input representation and rigidity–biinterpretability equivalence. Slaman, Global properties of the Turing degrees and the Turing jump, in Computational Prospects of Infinity, Part I (2008), 83–101, presents related results.

Kjos-Hanssen, Permutations of the integers induce only the trivial automorphism of the Turing degrees, Bulletin of Symbolic Logic 24 (2018), 165–174, is the parameter-recovery predecessor. Lutz and Siskind, Part 1 of Martin’s conjecture for order-preserving and measure-preserving functions, Journal of the American Mathematical Society 38 (2025), 319–367, supplies a related finite-oracle perfect-set recovery theorem.

Source manuscripts

• M1. OpenAI, Rigidity of the Turing degrees (September 24, 2026).

Sources consulted on 21 October 2026 at repository revision 1581d4c. Download the manuscript citations.