The problem whether a real function $f$ has a root or not is undecidable, given that $f$ is from a class of functions including polynomials and the sine function (http://dl.acm.org/citation.cfm?id=321856). Usually, undecidability is proved by using a periodic function like sin to encode integer problems. Is there anything known about undecidability of the root existence problem for some "reasonable" class of functions with bounded domains, such as from a bounded $\Omega\subset\mathbb{R}^m$ to $\mathbb{R}^n$?

$\begingroup$ As mentioned in mathoverflow.net/questions/109814 , the real field expanded with all analytic functions on a bounded domain is an ominimal structure. However, I’m not aware of any results on the decidability of its reducts to a finite language (note that decidability of an ominimal structure is equivalent to decidability of the root existence problem for its definable functions). Decidability of the real field with exponentiation is a notorious open problem related to Schanuel’s conjecture. $\endgroup$– Emil JeřábekNov 9, 2012 at 12:19

$\begingroup$ Also, asking the functions to have bounded domain does not make much of a difference per se. A “reasonable” class of functions on, say, $(0,1)^m$ can be made into a “reasonable” class of functions on $\mathbb R^m$, and vice versa, by composing with a “reasonable” homeomorphism of $(0,1)$ and $\mathbb R$, such as $1/(1x)1/x$. $\endgroup$– Emil JeřábekNov 9, 2012 at 12:23

$\begingroup$ Emil: right, thank you. What I have in mind is in fact compact domains (typically, finite unions of cubes), my formulation was not very good. $\endgroup$– Peter FranekNov 9, 2012 at 21:02
2 Answers
Suppose there is an algorithm that decides whether a function $f\colon \Omega \to \mathbb{R}$ has a root. Then one can also compute a root of $f$ if $f$ has one.
One can see this using a standard bipartition argument: Cover $\Omega$ with finitely many balls of radius $1$. This is possible since the closure of $\Omega$ is compact. Then using the algorithm we can find a ball that contains a root of $f$. Then we cover this ball with balls of radius $2^{1}$ and again find a smaller ball which contains a root...
Iterating this process yield a sequence converging to a root of $f$ with rate $2^{n}$ or in other words a Cauchyreal representation for a root.
Now, finding a root for a function implies Brouwer's fixed point theorem.
To see that let $\Omega$ be bounded and closed and $g\colon \Omega \to \Omega$ continuous. $g$ has a fixedpoint at any root of the function $f\colon \Omega \to \mathbb{R}$, $f(x):= \lvert g(x)  x\rvert$.
For Brouwers fixed point theorem it is known that there is no algorithm to find solutions, see for instance Computable counterexamples to the Brouwer fixedpoint theorem, Petrus H. Potgieter.
Thus, we can conclude that there is no algorithm which decides whether a function has a root.

1$\begingroup$ The questions asks for an algorithm deciding whether or not the function has a root, not an algorithm for finding a root. So you need an extra step to show that deciding whether there is a solution in $\Omega$ also allows you to compute one. I think that can be done but it would be nice to include here. $\endgroup$ Jan 19, 2013 at 16:35


Suppose $f$ is continuous (and therefore uniformly continuous) on a compact domain $K \subseteq {\mathbb R}^n$ (and this is effective in the sense that given $\epsilon > 0$ you can construct $\delta > 0$ such that $\x  y\ < \delta$ implies $\f(x)  f(y)\ < \epsilon$. Then if $f(x) = 0$ has no solution in $K$ you can prove that fact: take $\epsilon > 0$ small enough, take $\delta$ as above, cover $K$ with finitely many open balls of radius $\delta$, and compute the values of $f$ at the centres of these balls with sufficient precision to show they all have norm $> \epsilon$.

$\begingroup$ Robert: thank you. However, in this way you can only prove the nonexistence of a root (if it doesn't exists). $\endgroup$ Nov 9, 2012 at 21:07

$\begingroup$ Peter: Yes, I know. I don't think there is any way in general to prove the existence of a root if it does exist. $\endgroup$ Nov 11, 2012 at 2:35