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$?



(Un)Decidability of the root existence problem for functions with bounded domain
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](http://arxiv.org/abs/0804.3199).


Thus, we can conclude that there is no algorithm which decides whether a function has a root.


