What can be said about the decidability of $x = 0$ and $x(t) = 0$ in these families of symbolic expressions?

27 Views Asked by At

I have a program interfacing with symbolic algebra software (a CAS). In this software, suppose I can produce any integer expression and, given expressions $x$ and $y$, any expression of the form:

\begin{matrix} x + y \\ x - y \\ x \cdot y \\ x \div y \\ \operatorname{Z}_k(x_1,x_2,\ldots,x_n) \end{matrix}

where $\operatorname{Z}_k(x_0,x_1,\ldots,x_n)$ returns the $k$th root of the polynomial $x_n z^n + x_{n-1} z^{n-1} + \cdots + x_1 z + x_0$ for $n \in \mathbb{N}$, $k = 1\ldots n$ and expressions $x_0,x_1,\ldots,x_n$.

My understanding (please correct me if I'm wrong) is that the family of expressions that can be generated using these operations is isomorphic to the field of algebraic numbers $\overline{\mathbb{Q}}$, which is algebraically closed.

Now suppose I have an expression, $x$, in this family, e.g. $$x = \operatorname{Z}_3\left(\tfrac{114}{119} -\tfrac{25}{7}\operatorname{Z}_1\left[\tfrac{384}{17} + 12\operatorname{Z}_1(1,0,1), 0, 1, \tfrac{13}{9}\right],0,0,-13,0,5\right) + \tfrac{208}{43}$$ or $$x = \tfrac{1}{128} - \tfrac{2}{256}$$ and I wish to determine whether $x = 0$.

Question 1. Is this problem decidable in the computer theoretical sense? That is, is there an algorithm implementable on a Turing machine that is guaranteed to return the correct answer to this problem in a guaranteed finite amount of time, whether in the affirmative or the negative, for any possible symbolic expression $x$ in the family?

My gut feel is that the answer is "Absolutely. Just compute the decimal expansion of $x$ to $p!$ digits where $p$ is the total number of digits, commas, and operators in the expression for $x$, and compare every digit to zero. If they're all zero, $x = 0$, otherwise $x \neq 0$, and either way the algorithm completes in a finite amount of time." Even so, I'm aware the halting problem has many angels dancing on the heads of pins, and that the problem may turn out to be undecidable or have no known decidability.

Question 2. If $\pi$ is included in the list of constants and $|x|$, $\ln x$, $\exp x$, $\sin x$, and $\cos x$ are included in the list of operations, does the answer to question (1) change? My gut feel is "no".

Question 3. If an indeterminate variable $t$ is included with the integers in the set of generators such that the expressions become functions of $t$ and the determination becomes whether $x(t) \equiv 0$, with the five operations of question (1), is the problem decidable? From what I've been able to determine from gleaning Wikipedia, this is a variation of the "constant problem" with a real closed field, and the answer to this specific question is "Yes" because of the Tarski-Seidenberg theorem. ...Maybe?

Question 4. If $\pi$ is included in the list of constants and $|x|$, $\ln x$, $\exp x$, $\sin x$, and $\cos x$ are included in the list of operations, does the answer to question (3) change? Wikipedia suggests that the answer is "Yes" (the problem is undecidable)... because of Richardson's theorem... but not unless the $|x|$ operation is included. ...Maybe?

My need here is only for a conclusion on decidability in each of the four cases: decidable, undecidable, or unknown. I don't require algorithms, if they exist, although somebody else with a similar question may appreciate them. Many thanks.