4
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ How are you given the computable analytic function? $\endgroup$ – Peter Shor Nov 24 '14 at 4:58
  • $\begingroup$ @PeterShor, thank you for your comment. Actually, It's definition is the same as one in Computable Analysis by Weihrauch. $\endgroup$ – XL _At_Here_There Nov 24 '14 at 5:02
7
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Thank you, we meet online so often, and you have answered so many questions by me. The answer is really excellent. $\endgroup$ – XL _At_Here_There Nov 24 '14 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.