Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.)
