[Solved]: Easy to state open problems in computability theory

Problem Detail: 

I was searching for interesting and easy to state open problems in computability (understandable by undergraduate students taking their first course in computability) to give examples of open problems (and obviously I want the students to be able to understand the problem without needing too much new definitions and also be interesting to them).

I found this list but the problems in it seem too complicated for undergraduates and will need spending considerable time giving definitions before stating the problem. The only problem I have found so far is

Is Diophantine problem over rational numbers decidable?

Do you know any other interesting and easy to state open problem in computability theory?

Asked By : Kaveh

Answered By : Carl Mummert

One famous open question about the poset $(D, \leq_T)$ of Turing degrees is whether it has any non-trivial automorphisms. That is, does there exist a non-identity bijection $f\colon D \to D$ such that $a \leq_T b $ if and only if $f(a) \leq_T f(b)$?.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/430