Can the Turing degrees be relabeled?
A preprint claims that the order of relative computability has no nontrivial symmetry
Covers result 241 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
4:35. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
A set of numbers A is computable from a set B if a program that may ask questions about B can decide membership in A. Sets that compute each other have the same Turing degree, and the degrees form a partial order: the computable sets at the bottom, the halting problem’s degree 0′ above them, and, as Kleene and Post showed, pairs of degrees with neither computable from the other. A small picture like 0 < a, b < a ∨ b has a symmetry, swapping a and b; adding one more degree below a alone makes it rigid. In a 1965 lecture, Hartley Rogers asked whether the full order of Turing degrees is rigid. Nerode and Shore showed every automorphism is the identity on some cone. Slaman and Woodin, in work announced around 1990 and written up in an unpublished 2005 manuscript, showed every automorphism fixes everything above 0″, that there are only countably many, and that each is given by an arithmetic function. Barry Cooper claimed a nontrivial automorphism in the 1990s, but no one could verify it, and the field, and later Cooper himself, treated the problem as open.
Result 241 is one OpenAI preprint, 10 pages, dated September 24, 2026. It claims, in ZFC and with no definability assumption, that every order automorphism of the Turing degrees is the identity. As a corollary, through an equivalence Slaman and Woodin had proved, the degrees are biinterpretable with second-order arithmetic without parameters: their bi-interpretability conjecture.
What it doesn’t claim
Anything about other degree structures: the computably enumerable degrees, the degrees below 0′ and the arithmetic degrees remain open. The deep step is not new: the paper imports Slaman and Woodin’s representation theorem as its external input.
Where it stands
- Posted as a preprint
- OpenAI, 10 pages, dated September 24, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- Yes (docs)
Last checked October 19, 2026. The preprint has not been revised since release. In Lean, one comparator states the theorem for degrees of sets, using Mathlib’s oracle computability; the proof, about 84,000 lines with no unproved steps, also formalizes a version of the Slaman–Woodin input (we did not build it). OSVerify has not reviewed it. Andrew Marks wrote an exposition with a variant of the key lemma, calling the result “the finishing touch on the proof”, and Kjos-Hanssen adapted the method to truth-table degrees, for automorphisms given by Baire-measurable functions. We found no statement from Slaman, Woodin or Shore.
How the proof goes
- A function on the reals. Code each set as a real number. Slaman and Woodin’s theorem turns the automorphism into a concrete function F, and because a sum is computable from its terms and the automorphism respects order and joins, F(x + y) is computable from F(x) and F(y).
- A walk that cannot escape. Pick a real t. Step up by δt or down by δ(1 − t), depending on one bit of F at the current point; the bit takes one value near the bottom of an interval and the other near the top, so the walk stays inside, and the fraction of down steps approaches t. The whole walk is computable from the same four values of F.
- The squeeze. So t is computable from four values of F at points built from t and two helper reals. A Baire category argument removes the helpers: the inverse automorphism never raises a degree. Applying the same to the automorphism itself forces it to be the identity.
The numbers in the video
- Ours: of the 318 partial orders on 6 points, 102 are rigid (counts checked against the published tables).
- Ours: a toy version of the walk with t = 1/√2 and δ = 1/10 stays in its interval; after 20,000 steps the down-step fraction is 0.7071. Our steering bit is a stand-in, not one coming from an automorphism.
Read the source
- Rigidity of the Turing degrees (PDF), 10 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 241.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
Say a set of numbers A is computable from a set B if a program that may ask questions about B can decide membership in A. Two sets that compute each other have the same Turing degree, and the degrees form a partial order: zero at the bottom, the halting problem’s degree, 0′, above it, and in between, Kleene and Post found two degrees, neither computable from the other. A small picture like this has a symmetry: swap the two incomparable degrees and the order cannot tell. Add one more degree below just one of them and the symmetry is gone; the picture is rigid. Of the 318 partial orders on 6 points, 102 are rigid. In a 1965 lecture, Hartley Rogers asked whether the full order of Turing degrees is rigid: is the identity its only automorphism? Partial answers followed. Nerode and Shore showed every automorphism is the identity on some cone of degrees. Slaman and Woodin showed, in work announced around 1990 and written up in an unpublished 2005 manuscript, that every automorphism fixes everything above 0″, that there are only countably many, and that each is given by an arithmetic function. In the 1990s Barry Cooper claimed a nontrivial automorphism, but no one could verify his construction, and the field, and later Cooper himself, treated the problem as open.
1:25The claim
Result 241 is one OpenAI preprint, 10 pages, dated September 24, 2026. It claims that every order automorphism of the Turing degrees is the identity, in ZFC (Zermelo–Fraenkel set theory with choice), with no definability assumption on the automorphism. As a corollary, through an equivalence Slaman and Woodin had proved, the degrees are biinterpretable with second-order arithmetic without parameters: their bi-interpretability conjecture. Not claimed: anything about other degree structures. The computably enumerable degrees, the degrees below 0′, and the arithmetic degrees remain open. And the deep step is not new: the paper imports Slaman and Woodin’s representation theorem as its external input.
2:16How the proof goes
Code each set of numbers as a real number, and push the automorphism through that coding. Slaman and Woodin’s theorem turns it into a concrete function F on the reals, and because a sum is computable from its two terms, and the automorphism respects order and joins, F respects addition up to computation: F(x + y) is computable from F(x) and F(y). Now the new idea: a walk. Pick a real t. Step up by a small delta times t, or down by delta times 1 − t, depending on one bit of F at the current point. The bit takes one value near the bottom of an interval and the other near the top, so the walk can never leave it. Since the walk stays bounded, the fraction of down steps must approach t. And the whole walk can be computed from the same four values of F. Our toy version with t equal to 1/√2 stays in its interval, and after 20,000 steps the down-step fraction reads 0.7071. So t can be computed from four values of F, at points built from t and two helper reals. A Baire category argument removes the helpers: the inverse automorphism never raises a degree. Applying the same to the automorphism itself squeezes it to the identity.
3:37Where it stands
The preprint is unrefereed and unchanged since release. In Lean, one comparator states the theorem for degrees of sets, using Mathlib’s oracle computability; the proof, about 84,000 lines with no unproved steps, also formalizes a version of the Slaman and Woodin input. We did not build it. OSVerify has not reviewed it. Andrew Marks wrote an exposition with a variant of the key lemma, calling the result the finishing touch on the proof, and Kjos-Hanssen adapted the method to truth-table degrees, for automorphisms given by Baire-measurable functions. We found no statement from Slaman, Woodin or Shore. If it holds, the order of relative computability has no hidden symmetry: the only relabeling of the Turing degrees that preserves it leaves every degree where it is, about 60 years after Rogers asked.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.