I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.
1
-
6$\begingroup$ Try the post here: cstheory.stackexchange.com/questions/18846/… $\endgroup$– ShaullDec 29, 2015 at 19:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number? This is currently not known to be either decidable or undecidable.
(By contrast, the same problem with "prime" replaced by "composite" is decidable.)
$\begingroup$
$\endgroup$
Hilbert's Tenth Problem over the rationals is neither known to be decidable nor undecidable: given a set of polynomial equations with rational coefficients, does it have a rational solution? (The same problem with rationals replaced by integers was famously proved undecidable by Matiyasevich, building on M. Davis, H. Putnam, and J. Robinson. See this nice, brief survey by Bjorn Poonen.)
answered Dec 30, 2015 at 0:52