<p>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 <a href="http://www-math.mit.edu/~poonen/papers/h10_notices.pdf" rel="nofollow">nice, brief survey by Bjorn Poonen</a>.)</p>

CC BY-SA 3.0
2015-12-30T00:52:04.417Z
2015-12-30T00:52:04.417Z
Joshua Grochow
<p>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.</p>

<p>(By contrast, the same problem with "prime" replaced by "composite" is decidable.)</p>

CC BY-SA 3.0
2015-12-29T21:01:25.353Z
2015-12-29T21:01:25.353Z
Jeffrey Shallit
<p>I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.</p>

CC BY-SA 3.0
2015-12-29T19:00:41.237Z
Try the post here: http://cstheory.stackexchange.com/questions/18846/a-simple-problem-whose-decidability-is-not-known
Shaull
<fl.formal-languages><computability><turing-machines><decidability>
Are there any open problems concerning decidability?
Saravanan
# Are there any open problems concerning decidability?

(Asked by: username_0 on 2015-12-29)

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

**Tags:** fl.formal-languages, computability, turing-machines, decidability

> **Comments:**
> **username_1**: Try the post here: http://cstheory.stackexchange.com/questions/18846/a-simple-problem-whose-decidability-is-not-known  

---

## 2 answers

### Answer by username_3 on 2015-12-29. Score: 9 | Accepted answer

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


---

### Answer by username_2 on 2015-12-30. Score: 3

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](http://www-math.mit.edu/~poonen/papers/h10_notices.pdf).)


---

