Skip to main content
1 of 2
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Your question seems to concern the issue of the computability of solutions of computable functions, and the larger context for such a question is the subject known as computable analysis.

Carl Mummert has a very nice blog post concerning the following theorems, which I believe lie at the heart of your question.

Here are several interesting results from computable analysis:

Theorem 1. If $f$ is a computable function from $\mathbb{R}$ to $\mathbb{R}$ and $a$ is an isolated root of $f$, then α is computable.

Corollary 2. If $p(x)$ is a polynomial over $\mathbb{R}$ with computable coefficients, then every root of $p(x)$ is computable.

Theorem 3. There is a effective closed subset of $\mathbb{R}$ which is nonempty (in fact, uncountable) but which has no computable point.

Theorem 4. There is a computable function from $\mathbb{R}$ to $\mathbb{R}$ which has uncountably many roots but no computable roots.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k