Skip to main content
2 of 2
added 673 characters in body
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.

But your question inquires not for an algorithm for each function separately, but a uniform algorithm working with all equations to be solved. Here, there are various non-uniformity results that one can mention.

For example, by the MRDP theorem, there can be no computable algorithm that determines whether a given integer polynomial equation in several variables has a solution in the integers.

But meanwhile, there of course can be a computational procedure that maps any given Diophantine equation to an integer solution of it, when there is a solution, for one may simply undertake exhaustive search.

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