A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms

Bj{\o}rn Kjos-Hanssen

REVIEW 2 major objections 5 minor 7 references

A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A homeomorphism of Cantor space that preserves eventual agreement between binary sequences, uniformly in both directions, can induce only the trivial automorphism of the Turing degrees.

desk verdict The core Turing-degree claim is not yet proven: the proof's use of Lemma 14 overreaches, since a nonmeager Gδ agreement set need not contain a cylinder, and the theorem's stated scope over all reducibilities is also unsupported. read the letter →

arxiv 1908.05381 v2 pith:VPF5V2T4 submitted 2019-08-15 math.LO

Bj{o}rn Kjos-Hanssen This is my paper · ORCID

classification math.LO MSC 03D2803D30

keywords TuringdegreesautomorphismproblemE0equivalencerelationCantorspacebi-uniformE0-isomorphismtruth-tablereducibilityBairecategory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper addresses the long-standing question of whether the Turing degrees have a nontrivial automorphism. It proves that one natural class of candidate maps cannot work: any automorphism of a degree structure between many-one and Turing reducibility that is induced by a homeomorphism of Cantor space preserving eventual agreement, uniformly in both directions, must be the identity. The proof shows such a homeomorphism is necessarily computable, and then argues that a computable induced map cannot move any degree. If the result is correct, a broad family of continuous, uniformity-respecting constructions is eliminated from the search for exotic automorphisms.

What carries the argument

The engine is a recursion lemma: if $\Theta^{-1}\circ S^*\circ\Theta$ is computable, where $S^*$ is the induced shift on Cantor space, then every finite initial segment of $\Theta$ can be computed by iterating that conjugate, so $\Theta$ is computable. To obtain the hypothesis, a forcing and category lemma upgrades a condition of the form 'the map agrees with some Turing functional on a nonmeager set' to full computability, using the uniform $E_0$-invariance to control all tails. The degree-theoretic conclusion then rests on the fact that a computable $\Theta(A)$ is truth-table reducible to $A$, i.e. each bit of $\Theta(A)$ is decided by a finite lookup table using finitely many bits of $A$.

What would settle it

A decisive test is to search for a bi-uniform $E_0$-isomorphism homeomorphism $\Theta$ whose induced map $[A]_r\mapsto[\Theta(A)]_r$ is a nontrivial automorphism for some reducibility between $\le_1$ and $\le_T$. A concrete place to start is the paper's Example 16 recursion: tabulate how many bits of $A$ are needed to compute $\Theta(A)(n)$; if this count is unbounded, then $\Theta(A)\le_{tt} A$ does not imply $\Theta(A)\le_{btt} A$, and any $A$ with $[\Theta(A)]_{btt}\ne[A]_{btt}$ would refute the theorem as stated.

Watch

Extended reading notes

Core claim

The central claim is Theorem 15: let $\pi$ be an automorphism of the degree ordering for any reducibility between $\le_1$ and $\le_T$, and suppose $\pi$ is induced by a homeomorphism $\Theta$ of Cantor space that is a bi-uniform $E_0$-isomorphism. Then $\Theta$ is computable and $\pi$ is trivial. Here $E_0$ is the equivalence relation of eventual agreement on infinite binary sequences, and bi-uniform means that the place where two input sequences start agreeing is controlled, through a fixed function, by the place where their images start agreeing, and conversely. The proof obtains computability of $\Theta$ by a recursion that reads off all finite initial segments of $\Theta$ from the conjugated successor shift $\Theta^{-1}\circ S^*\circ\Theta$, after a category argument shows this conjugate is forced to equal a Turing functional on a nonmeager set. Once $\Theta$ is computable, $\Theta(A)$ is truth-table reducible to $A$, and the triviality of $\pi$ follows by applying the same argument to $\Theta^{-1}$.

Load-bearing premise

The proof's last step assumes that a truth-table reduction between sets is also a reduction in the particular degree ordering being studied; that is true for Turing and truth-table degrees but not automatically for many-one or bounded truth-table degrees, so the theorem's announced range is not fully established by the argument as written.

Editorial extensions

If this is right

If the theorem is correct, any nontrivial automorphism of the Turing degrees, if one exists, cannot be induced by a bi-uniform $E_0$-invariant homeomorphism of Cantor space.
The exclusion is stated for every reducibility between many-one and Turing, so the same class of maps is ruled out simultaneously for many-one, bounded truth-table, truth-table, and Turing degree structures.
The intermediate conclusion that $\Theta$ is computable is stronger than triviality of the induced automorphism: these maps are entirely constructive objects.
The proof also gives a more direct route to the special case that no permutation of the integers induces a nontrivial automorphism, which the paper develops as Theorem 8.
Example 10 shows the uniformity hypothesis is not vacuous: some $E_0$-invariant continuous maps fail the uniformity condition, so the theorem is not about an empty class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A close reading of the proof's final step suggests that the theorem's full range is not actually established by the written argument: the step infers from $\Theta(A)\le_{tt} A$ that $\pi([A]_r)\le[A]_r$, but for many-one or bounded truth-table reducibility a truth-table reduction is not automatically a reduction in the target ordering, so a separate argument would be needed for those cases.
If a continuous representation of automorphisms of the arithmetical degrees exists, the same recursion scheme might transfer to that setting by replacing the shift with the relevant jump operation; this is a speculative extension, not a claim of the paper.
Relaxing bi-uniformity to one-sided uniformity, as in the deletion example, breaks the argument; testing whether one-sided uniformity already admits noncomputable induced automorphisms would locate the precise boundary of this method.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main thing you should know: as written, the paper's central claim does not go through. The gap is not the reducibility point the reader flagged (though that's real too); it is one step earlier, where Lemma 14 is invoked to make Γ computable.

Lemma 14 requires that F(X)=Φ^X is forced above σ in the strong sense: equality for every real extending σ. The proof earlier finds a nonmeager Gδ set E={B:Γ(B)=Φ^B}. From nonmeager Gδ you get only that E is comeager in some [σ], not that E contains a cylinder. The proof of Lemma 14 then uses σցX and needs that point to be in E. For a comeager set, σցX need not be in E; the finite-modification class of X is countable and could lie entirely outside E. So the step that makes Γ, and then Θ, computable is unsupported.

That said, the paper is not careless. The idea is genuinely new and worth pursuing: bi-uniform E0-invariance is a natural strong condition, and the shift-based recursion in Lemma 12 is clean. Lemma 14, once repaired or reformulated, would be a useful tool. The compact writing is a plus, not a minus.

The second soft spot is the theorem's stated scope. The proof shows Θ(A)≤tt A and then concludes π([X]_r)≤[X]_r for every reducibility between ≤1 and ≤T. That only works if ≤tt is a subrelation of ≤r, which is false for many-one and bounded truth-table. The theorem should be restricted to reducibilities containing ≤tt, or the argument needs to establish Θ(A)≤r A directly.

Net assessment: the Turing-degree version might be true, but the proof as written has a load-bearing gap. The reducibility overreach is a simple scope fix. This is a paper for a serious referee, not a desk reject: the approach is sound in spirit, the writing is honest, and the gap is specific enough that an author could plausibly close it.

My recommendation: send to peer review, but with a clear request to address the Baire-to-cylinder issue and to correct the theorem's scope.

Referee Report

2 major / 5 minor

Summary. The paper studies automorphisms of degree structures induced by homeomorphisms of Cantor space. It introduces the notion of a bi-uniformly E0-invariant homeomorphism and claims that any such homeomorphism that induces an automorphism of the Turing degrees (or, more generally, of the degrees associated with any reducibility between ≤1 and ≤T) must be computable, and hence the induced automorphism is trivial. The proof strategy combines Baire category, a finite-use recursion lemma, and an argument that a uniformly E0-invariant continuous map agreeing with a Turing functional on a nonmeager set must be computable. The paper is short, clearly written, and contains helpful examples.

Significance. If the main result were established, it would be a genuine, if modest, contribution to the Turing automorphism problem: it would rule out a natural combinatorial class of candidate nontrivial automorphisms. The paper's treatment of bi-uniform E0-invariance is elegant and the permutation case in Section 2 is a nice, self-contained warm-up. The proof is largely self-contained and does not rely on unproved external claims. However, the central proof has a substantial gap in the application of Lemma 14, and the theorem is stated more broadly than the proof supports. As it stands, the main claim is not established.

major comments (2)

[§3, Lemma 14 and Theorem 15] The proof of Theorem 15 derives a nonmeager Gδ set E={B:Γ(B)=Φ^B} and then invokes Lemma 14. The lemma's hypothesis is that F(X)=Φ^X is forced above σ, which the proof of the lemma interprets as equality for every X extending σ. However, Baire category applied to the nonmeager Gδ set E yields only that E is comeager in some interval [σ], and a comeager Gδ set need not contain a basic open interval. In the proof of Lemma 14, the step F(X)(n)=F^{σ↓X}(n)=Φ^{σ↓X}(n) uses σ↓X=X for X∈[σ] and requires X∈E; for X outside E the equality is not available. Thus the application of Lemma 14 is unjustified, and the computability of Γ, and hence of Θ, is not established.
[§3, Theorem 15, final paragraph] The final inference 'Θ(A)≤tt A, and in particular π([X]_r)≤[X]_r' requires that ≤tt be a subrelation of ≤r. For reducibilities such as ≤1, ≤m, or ≤btt, which are between ≤1 and ≤T but do not contain ≤tt, the implication Θ(A)≤tt A ⇒ Θ(A)≤r A is false in general. The theorem is therefore stated too broadly; as written it is not proved for those reducibilities. The Turing-degree version in the abstract is unaffected by this particular issue, but the theorem statement should be corrected to 'for any reducibility ≤r that contains ≤tt' or the proof must establish Θ(A)≤r A directly.

minor comments (5)

[Abstract] In the first sentence the function is named F, but in the displayed equivalence it is called f; the notation should be made consistent.
[Theorem 15] The statement contains a typo: 'automorphism ot Dr' should read 'automorphism of Dr'.
[Lemma 12 proof] The phrase 'Since homeomorphisms have finite use' is terse; adding a sentence explaining the modulus of continuity for Θ would make the argument easier to follow.
[Throughout] The symbol ≤T is used both for Turing reducibility and as the right endpoint of the interval of reducibilities; clarifying the distinction would prevent confusion.
[References] Reference [2] is a MathOverflow post; if a peer-reviewed version of that example exists, it would be preferable to cite it.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained and derives the computability of Θ from stated lemmas, with prior work cited only as background.

full rationale

The paper's central claim is that a bi-uniformly E0-invariant Cantor homeomorphism inducing an automorphism of Dr must be computable, and hence induce the trivial automorphism. The derivation chain is self-contained: Lemma 12 proves Θ is computable from the computability of Γ = Θ∘S⋆∘Θ−1; Lemma 14 proves Γ is computable from the existence of a nonmeager Gδ set on which Γ(B)=ΦB together with uniform E0-invariance; and the nonmeager Gδ set is obtained by a Baire-category argument from the assumption that Θ induces a well-defined automorphism. Each step uses only stated hypotheses and standard computability/descriptive-set facts. There is no fitted parameter renamed as a prediction, no quantity defined in terms of the target conclusion, and no load-bearing appeal to a self-citation: the author's earlier paper [4] is mentioned only as background and motivation ('In [4] we attacked the problem...'), not as the source of the theorem's key premises. The result is not equivalent to its inputs by construction. Even if the proof has a mathematical gap (as a separate correctness concern), that would not constitute circularity. The derivation is therefore not circular, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof relies on standard facts from descriptive set theory and computability theory. No new axioms, fitted parameters, or invented entities are introduced. The main nonstandard dependencies are the composition-closure of uniform E0-invariance and the use of Baire category to extract a single forcing condition.

assumptions (5)

standard math Baire category theorem on Cantor space: a countable union of meager sets is meager, and a nonmeager Gδ set contains a comeager basic open set.
Used in Lemma 5 and Theorem 15 to pass from 'for every B some Φ works' to 'some Φ works on a nonmeager set' and then to a forcing condition.
domain assumption Total computable Turing functionals on Cantor space are continuous and have bounded finite use on compact sets; computable homeomorphisms are truth-table reductions.
Used in Lemma 12 ("homeomorphisms have finite use") and in the final step "Θ(A)≤tt A".
standard math Composition of uniformly E0-invariant functions is uniformly E0-invariant; hence Γ=Θ∘S⋆∘Θ^{-1} is uniformly E0-invariant if Θ and Θ^{-1} are.
Invoked in Theorem 15 to apply Lemma 14 to Γ.
domain assumption If a map induces an automorphism of Dr, it preserves the reducibility relation, so A≤rB implies π([A])≤rπ([B]).
Used in Theorem 8 and Theorem 15 to transfer A≤1Θ^{-1}(B) to Θ(A)≤rB.
domain assumption If a homeomorphism's inverse is computable, the homeomorphism itself is computable (via compactness and search).
Needed in Theorem 15 after applying Lemma 12 to Θ^{-1}; the paper does not spell this step out.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms." pith.science (2026). https://pith.science/paper/VPF5V2T4

@misc{pith2026190805381,
  author       = {Pith},
  title        = {Pith review of: A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VPF5V2T4}},
  note         = {Machine review of arXiv:1908.05381}
}

abstract

A function $F:2^\omega\to 2^\omega$ is an $E_0$-isomorphism if for all $x,y\in 2^\omega$, we have $xE_0y\iff f(x)E_0 f(y)$, where $xE_0y\iff(\exists a)(\forall n\ge b) x(n)=y(n)$. If such witnesses $a$ for $xE_0 y$ and for $f(x)E_0 f(y)$ depend on each other but not on $x$, $y$, then $F$ is called bi-uniform. It is shown that a homeomorphism of Cantor space which is a bi-uniform $E_0$-isomorphism can induce only the trivial automorphism of the Turing degrees.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[1]

Barry Cooper

S. Barry Cooper. The Turing universe is not rigid. Univer sity of Leeds Pure Mathematics Preprint Series 1997, no. 16 (revised February 1998)

work page 1997
[2]

mod ﬁnite

Ville Salo (https: //mathoverﬂow.net /users/123634/ville salo). Homeomorphisms and “mod ﬁnite”. MathOverﬂow. URL:https: //mathoverﬂow.net /q/364844 (ver- sion: 2020-07-04)

work page 2020
[3]

Jockusch, Jr

Carl G. Jockusch, Jr. and Robert M. Solovay. Fixed points of jump preserving automorphisms of degrees. Israel J. Math., 26(1):91–94, 1977

work page 1977
[4]

Permutations of the integers induc e only the trivial automor- phism of the Turing degrees

Bjørn Kjos-Hanssen. Permutations of the integers induc e only the trivial automor- phism of the Turing degrees. Bull. Symb. Log., 24(2):165–174, 2018

work page 2018
[5]

Anil Nerode and Richard A. Shore. Reducibility ordering s: theories, deﬁnability and automorphisms. Ann. Math. Logic, 18(1):61–89, 1980

work page 1980
[6]

Theodore A. Slaman. Global properties of the Turing degr ees and the Turing jump. In Computational prospects of inﬁnity. Part I. Tutorials , volume 14 of Lect. Notes Ser . Inst. Math. Sci. Natl. Univ. Singap., pages 83–101. World Sci. Publ., Hacken- sack, NJ, 2008

work page 2008
[7]

Slaman and Hugh Woodin

Theodore A. Slaman and Hugh Woodin. Deﬁnabil- ity in degree structures. Online draft, July 2005. URL:https://math.berkeley.edu/˜slaman/talks/sw.pdf. 7

work page 2005

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Barry Cooper

S. Barry Cooper. The Turing universe is not rigid. Univer sity of Leeds Pure Mathematics Preprint Series 1997, no. 16 (revised February 1998)

work page 1997

[2] [2]

mod ﬁnite

Ville Salo (https: //mathoverﬂow.net /users/123634/ville salo). Homeomorphisms and “mod ﬁnite”. MathOverﬂow. URL:https: //mathoverﬂow.net /q/364844 (ver- sion: 2020-07-04)

work page 2020

[3] [3]

Jockusch, Jr

Carl G. Jockusch, Jr. and Robert M. Solovay. Fixed points of jump preserving automorphisms of degrees. Israel J. Math., 26(1):91–94, 1977

work page 1977

[4] [4]

Permutations of the integers induc e only the trivial automor- phism of the Turing degrees

Bjørn Kjos-Hanssen. Permutations of the integers induc e only the trivial automor- phism of the Turing degrees. Bull. Symb. Log., 24(2):165–174, 2018

work page 2018

[5] [5]

Anil Nerode and Richard A. Shore. Reducibility ordering s: theories, deﬁnability and automorphisms. Ann. Math. Logic, 18(1):61–89, 1980

work page 1980

[6] [6]

Theodore A. Slaman. Global properties of the Turing degr ees and the Turing jump. In Computational prospects of inﬁnity. Part I. Tutorials , volume 14 of Lect. Notes Ser . Inst. Math. Sci. Natl. Univ. Singap., pages 83–101. World Sci. Publ., Hacken- sack, NJ, 2008

work page 2008

[7] [7]

Slaman and Hugh Woodin

Theodore A. Slaman and Hugh Woodin. Deﬁnabil- ity in degree structures. Online draft, July 2005. URL:https://math.berkeley.edu/˜slaman/talks/sw.pdf. 7

work page 2005