(Un)Decidability of the root existence problem for functions with bounded domain 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$?
 A: 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 bi-partition 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 Cauchy-real 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 fixed-point 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 counter-examples to the Brouwer fixed-point theorem, Petrus H. Potgieter.
Thus, we can conclude that there is no algorithm which decides whether a function has a root.
A: 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$.  
