0
$\begingroup$

I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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