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 $fcolon 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
