MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is conjectured that the automorphism group of the Turing degrees, $Aut(\mathcal{D})$, is trivial. However, to the best of my knowledge, the current state-of-the-art is that $Aut(\mathcal{D})$ is countable.

My question is twofold: first, is my understanding correct? Is there any countable group $G$ which we know can't be isomorphic to $Aut(\mathcal{D})$?

Second, and more interesting to me: what if anything could we conclude from some group-theoretic information about $Aut(\mathcal{D})$? I.e., what new computability theory would we know if we knew that $Aut(\mathcal{D})$ is abelian, or is simple, or is not finitely generated? (This is admittedly a slightly awkward question, given that we think $ZFC$ proves "$Aut(\mathcal{D})=\lbrace e\rbrace$.")

My reason for asking is that as a rule I am interested in interaction between computability theory and other subjects (for instance, the proof via Higman that there is a universal finitely presented group is dear to my heart), but I am especially interested in examples of other mathematics being applied to computability theory, and I'd be very interested in what the group-theoretic nature of $Aut(\mathcal{D})$ (assuming it's nontrivial) has to say about other parts of computability theory.

share|cite|improve this question
Yes, your understanding is correct. This is proved (among many other related results) in Ted and Hugh's notes "Definability in degree structures", available at – Andrés E. Caicedo Jan 23 '13 at 19:03
The key question here is the bi-interpretability conjecture, but as far as I know there is no concrete (interesting) information on what groups are known to be excluded as candidates. – Andrés E. Caicedo Jan 23 '13 at 19:05
I'm trying to figure out a precise sense for the loose term "the turing degrees". Do you mean the set of Turing degrees? Endowed with which structure? the partial order? – YCor Mar 19 '14 at 18:05
"The Turing degrees" refers to the poset of the Turing degrees - this is a standard term, and its standard meaning, in computability theory. Note that trivially the join is definable, and by results of (oh dear, I'm probably missing someone) Woodin, Slaman, and Shore, the jump is definable in this partial order; so really the poset structure already captures all the 'basic' operations on the degrees. – Noah Schweber Mar 19 '14 at 18:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.