15
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What amount/kind of prior knowledge can we assume, e.g. regarding automata, formal languages, algorithms? $\endgroup$
    – Raphael ♦
    Mar 16, 2012 at 0:36
  • $\begingroup$ @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". $\endgroup$
    – Kaveh
    Mar 16, 2012 at 0:41
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Sep 23, 2012 at 15:05

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ How is this problem interesting to the average undergraduate student? Is there any known consequence that can be derived from the existence of such automorphism? I think motivation is paramount when introducing new concepts, especially if it is only to show students a "famous open problem". $\endgroup$
    – Janoma
    Mar 18, 2012 at 15:08
  • 3
    $\begingroup$ @Janoma: the motivation is to study (and understand) the global structure of the Turing degrees. It would be easy to state without proof a few results such as density, and mention this as an easy to state but hard to solve open problem. $\endgroup$
    – Carl Mummert
    Mar 18, 2012 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.