0
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by cody, Kaveh, Jukka Suomela, Joshua Grochow, Community Dec 30 '15 at 2:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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.