I was searching for interesting and easy to state open problems in computability

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.