# Easy to state open problems in computability theory

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?

• What amount/kind of prior knowledge can we assume, e.g. regarding automata, formal languages, algorithms? – Raphael Mar 16 '12 at 0:36
• @Raphael, you can assume the knowledge of basic computability theory, e.g. they know what is covered in the computability part of Sipser's book "Introduction to the theory of computation". – Kaveh Mar 16 '12 at 0:41
• computability theory is defn more abstract than say eg complexity theory esp for undergraduates. have not heard of entire undergrad classes for computability theory. what do you cover? do you have a syllabus online or is it similar to another online? it might be helpful to go over the history of Hilberts 10th problem which stayed open for most of the 20th century & is one of the "big" thms in the field. some say with real justification its one of the most important of the 20th century. – vzn Sep 23 '12 at 15:05

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)$?.