HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Easy to state open problems in computability theory

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theoryopencomputabilityeasystateproblems

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#430, answer score: 5

Revisions (0)

No revisions yet.