2 See comment by François: He is right, I added an step which shows that decision algorithm for roots can be used to compute a root.

Finding

Suppose there is an algorithm that decides whether a function $f\colon \Omega \to \mathbb{R}$ has a rootfor . Then one can also compute a function 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 equivalent 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.

In the other direction the function $f:\Omega\to \mathbb{R}$ has a root at any fixed-point of the function $g:\Omega \to \Omega$, $g(x):= x + f(x) * x$.(Strictly speaking one has to take care that one does not get out of $\Omega$ but this should be doable.)

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.

1

Finding a root for a function is equivalent to 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$. In the other direction the function $f:\Omega\to \mathbb{R}$ has a root at any fixed-point of the function $g:\Omega \to \Omega$, $g(x):= x + f(x) * x$. (Strictly speaking one has to take care that one does not get out of $\Omega$ but this should be doable.)

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.