Easy to state open problems in computability theory
-
16-10-2019 - |
Pergunta
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?
Solução
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)$?.