<p>No, it is not decidable. A good heuristic to answer such questions is the following: every computable map is continuous. If you could decide whether $f(x) = 0$ for all $x \in \mathbb{C}$, then the characteristic map $d$ of such a decision procedure, namely
$$d : f \mapsto \begin{cases}
1 &amp; \text{if $\forall x \in \mathbb{C} . f(x) = 0$}\\
0 &amp; \text{otherwise}
\end{cases}
$$
would be a non-constant computable map from the vector space of all such functions to the discrete space $\{0,1\}$, but such a map is discontinuous. By the same reasoning you cannot even decide whether $f(x) = 0$ at a single given $x \in \mathbb{C}$. And for the same reason still it is impossible to decide whether $y = 0$ where $y \in \mathbb{R}$.</p>

<p>A similar heuristic in a slightly different form: computable maps are continuous, therefore in any computable procedure a small perturbation of the input must create only a small perturbation of the output. From this you can see immediately that the map which takes $f$ to one of its roots (assuming $f$ has one) is not computable, because it is easy to make roots jump around wildly with arbitrarily small perturbations of $f$. (This heuristic would not work if you know someting extra about $f$, for instance if you are guaranteed that it is an odd-degree polynomial).</p>

<p>Of course, you need to know what topology to put on the vector space, but as a heuristic it is good enough to just imagine "the usual" topology, whatever that is. (There are theorems in computable analysis which say that an admissible representation of a separable metric space gives induces the metric topology, so the heuristic is pretty safe.)</p>

CC BY-SA 3.0
2014-11-24T14:32:53.113Z
Thank you, we meet online so often, and you have answered so many questions by me. The answer is really excellent.
XL _At_Here_There
CC BY-SA 3.0
2014-11-24T10:45:46.383Z
2014-11-24T13:11:55.690Z
2014-11-24T13:11:55.690Z
Andrej Bauer
<p>Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$  in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm?</p>

<p>Also, I am wondering under what condition regarding the domain of the function, can it be decidable that $f$ is identically zero?</p>

CC BY-SA 3.0
2014-11-24T04:58:37.933Z
How are you given the computable analytic function?
Peter Shor 
CC BY-SA 3.0
2014-11-24T05:02:53.243Z
@PeterShor, thank you for your comment. Actually, It's definition is the same as one in Computable Analysis by Weihrauch.
XL _At_Here_There
<reference-request><computability><computable-analysis><model-theory>
Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$
XL _At_Here_There
# Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

(Asked by: username_0 on 2014-11-24)

Is it decidable whether a computable analytic function $f(x\_1,x\_2,\dots,x\_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm?

Also, I am wondering under what condition regarding the domain of the function, can it be decidable that $f$ is identically zero?

**Tags:** reference-request, computability, computable-analysis, model-theory
> **Comments:**
> **username_1**: How are you given the computable analytic function?  
> **username_0**: @PeterShor, thank you for your comment. Actually, It's definition is the same as one in Computable Analysis by Weihrauch.  

---

## 1 answers

### Answer by username_2 on 2014-11-24. Score: 7 | Accepted answer

No, it is not decidable. A good heuristic to answer such questions is the following: every computable map is continuous. If you could decide whether $f(x) = 0$ for all $x \in \mathbb{C}$, then the characteristic map $d$ of such a decision procedure, namely
$$d : f \mapsto \begin{cases}
1 & \text{if $\forall x \in \mathbb{C} . f(x) = 0$}\\
0 & \text{otherwise}
\end{cases}
$$
would be a non-constant computable map from the vector space of all such functions to the discrete space $\{0,1\}$, but such a map is discontinuous. By the same reasoning you cannot even decide whether $f(x) = 0$ at a single given $x \in \mathbb{C}$. And for the same reason still it is impossible to decide whether $y = 0$ where $y \in \mathbb{R}$.

A similar heuristic in a slightly different form: computable maps are continuous, therefore in any computable procedure a small perturbation of the input must create only a small perturbation of the output. From this you can see immediately that the map which takes $f$ to one of its roots (assuming $f$ has one) is not computable, because it is easy to make roots jump around wildly with arbitrarily small perturbations of $f$. (This heuristic would not work if you know someting extra about $f$, for instance if you are guaranteed that it is an odd-degree polynomial).

Of course, you need to know what topology to put on the vector space, but as a heuristic it is good enough to just imagine "the usual" topology, whatever that is. (There are theorems in computable analysis which say that an admissible representation of a separable metric space gives induces the metric topology, so the heuristic is pretty safe.)

> **Comments:**
> **username_0**: Thank you, we meet online so often, and you have answered so many questions by me. The answer is really excellent.  

---

