Can we decide whenever a function is the derivate of another function in this Language?

Question

Our EXP functions are made in the following way:

• Any constant $ \in \Bbb R$ is a EXP
• $X \in \Bbb R$ is a EXP
• $sin( g(x))$, $cos( g(x))$ are in EXP if $g(x)$ is a EXP
• $tan( g(x))$ is a EXP if $g(x)$ is a EXP and $g(x) \neq \frac\pi 2 + k\pi, k \in \Bbb Z $
• $sqrt( g(x))$ is a EXP if $g(x)$ is a EXP and $g(x) \gt 0$
• $pow( f(x), k)$ is a EXP if $f(x)$ is a EXP and $k \in \Bbb R$
• $exp(g(x))$ is a EXP if $g(x)$ is a EXP
• $ln(f(x))$ is a EXP if $f(x)$ is a EXP and $f(x) \gt 0$
• $f(x)+g(x)$ is a EXP if $g(x),f(x)$ are EXP
• $f(x)-g(x)$ is a EXP if $g(x),f(x)$ are EXP
• $f(x)*g(x)$ is a EXP if $g(x),f(x)$ are EXP
• $f(x)/g(x)$ is a EXP if $g(x),f(x)$ are EXP and $g(x) \neq 0$
• if $g(x)$ is a EXP then $g'(x)$ is a EXP (derivative)

What I want to know, is if there's an algorithm that, given $f(x) \in EXP$ can say:

• Yes: iff there exist a $g(x)$ such that $g'(x) = f(x)$ and $g(x) \in EXP$
• No: otherwise
• Always halt

Of course since we have derivates, also the following derivation rules still applies:

• if $f(x) = c$ where $c \in \Bbb R$, then $f'(x) = 0$
• if $f(x) = x$ where $x \in \Bbb R$, then $f'(x) = 1$
• if $f(x) = sin(g(x))$ then $f'(x) = cos(f(x))*g'(x)$
• if $f(x) = cos(g(x))$ then $f'(x) = -sin(f(x))*g'(x)$
• if $f(x) = tan(g(x))$ then $f'(x) = \frac{g'(x)}{cos^2(g(x))}$
• if $f(x) = sqrt(g(x))$ then $f'(x) = (1/2)*pow(g(x), -1/2)*g'(x)$
• if $f(x) = exp(g(x))$ then $f'(x) = exp(g(x))*g'(x)$
• if $f(x) = pow(g(x),k)$ and $k \in \Bbb R$ then $f'(x) = k*pow(g(x), k-1)*g'(x)$
• if $f(x) = ln(g(x))$ then $f'(x) = \frac{g'(x)}{g(x)}$
• if $f(x) = g(x)+h(x)$ then $f'(x) = g'(x)+h'(x)$
• if $f(x) = g(x)-h(x)$ then $f'(x) = g'(x)-h'(x)$
• if $f(x) = g(x)*h(x)$ then $f'(x) = g'(x)*h(x) +g(x)*h'(x)$
• if $f(x) = g(x)/h(x)$ then $f'(x) = \frac{g'(x)*h(x) -g(x)*h'(x)}{h(x)^2}$

P.S. I did not repeated that denominator of a fraction should be different by zero because that is already covered by the first set of rules.

P.P.S: Use of absolute value is admitted because of following observation:

$$ |f(x)| = sqrt(f(x)*f(x))$$

So you are just using a short form, but you are not taking positive values of a function, you are just computing the Squareroot of its Square in this language. Nor integrals are admitted in this language.

Answer 1

Here's another stab. It's based on the idea mentioned by Joel David Hamkins in his comments.

Let $a(x)$ and $b(x)$ be two such functions. We'll use the fact that deciding whether or not $a(x)$ and $b(x)$ are identically equal is undecidable. For this, we need a function $\Phi(a,b)$ that takes two functions and outputs $0$ if they are identically $0$ and some non-zero real otherwise.

One function we could take is simply $\Phi(a,b) = sup_{x} (a(x)-b(x))^2$. Perhaps this is not allowable for your class of functions. So I propose instead the function $$\Phi(a,b) = \int_{-\infty} ^{\infty} \frac{(a(x)-b(x))^2}{e^{|x|} (1+(a(x)-b(x))^2)} dx.$$

We then consider the integral of $e^{-t^2 \Phi}$, which is an elementary function iff $\Phi = 0$, which is iff $a(x)=b(x)$, which is undecidable.

---

A slightly different punchline might be to consider the double integral

$$ \int \int \frac{(a(x)-b(x))^2}{e^{|x|} (1+(a(x)-b(x))^2)} e^{-t^2} dx dt, $$ which is perhaps not great because it's a function of two variables, which isn't likely what you had in mind.

---

Or a third variation on this would be to define $\gamma(x) = |x|/x$ (and $\gamma(0) = 0$). Then consider the function $\gamma((a(x)-b(x))^2)e^{-x^2}$, which has an elementary antiderivative iff the leading coefficient is $0$ almost everywhere (which is undecidable).

---

A fourth variation is perhaps more satisfying. We may assume $a(x)$ and $b(x)$ are in the ring generated by $\mathbb{Z}[x, \sin(x^n), \sin(x \sin(x^n))]$. Let $C(x) = |a(x) - b(x)| - (a(x)-b(x))$. Then it is undecidable to determine if $C(x)$ is identically $0$. But for $C(x)$ of this form, it's all but certainly true that $e^{C(x) x^2}$ has an elementary antiderivative iff $C(x) = 0$. [I am unsure how to prove this claim, but it could probably be proven along the same lines that $e^{ax^2}$ has no elementary antiderivative]

Answer 2

Even though it is not explicitly stated in the question, I am going to assume that EXP is the smallest set of expressions closed under the operations listed. (Otherwise, the answer would be different for different choices of the set of expressions—for instance, if we closed the set under antiderivatives, the problem would be trivially decidable. The last sentence of the “P.P.S.” further indicates this is not what the OP wants.)

Then, Richardson’s theorem does give a negative answer, even though the OP denies it in the bounty quote (presumably because of misunderstanding the statement of the theorem).

Let me restate the relevant theorem as proved by Richardson [1]:

Theorem: Let $E$ be a set of expressions representing partial functions $\mathbb R\to\mathbb R$ with the following properties:

1. Given expressions in $E$ representing functions $A(x)$ and $B(x)$, we can compute expressions in $E$ representing the functions $A(x)+B(x)$, $A(x)-B(x)$, $A(x)\cdot B(x)$, and $A(B(x))$.

2. $E$ includes expressions representing the identity function; constant functions for rational numbers, $\log 2$, and $\pi$; the functions $\exp x$ and $\sin x$; and a function $\mu$ such that $\mu(x)=|x|$ for $x\ne0$.

3. $E$ includes an expression representing a total function $g(x)$ such that for no function $f(x)$ represented by an $E$-expression, and for no nondegenerate interval $I$, we have $g(x)=f'(x)$ on $I$.

Then it is undecidable whether a given expression from $E$ represents a function that has an antiderivative also represented in $E$.

(By subsequent work of Caviness, Wang, and Laczkovich, one can drop $\log 2$, $\pi$, and $\exp$ from the assumptions, and closure under composition can also be substantially weakened. However, this is not important for the present purpose.)

I stress that the conditions are to be taken literally. Unlike what I wrote in the first paragraph of my answer, there is no implied assumption in Richardson’s theorem that $E$ uses only the functions specified in the closure conditions. If the theorem applies to $E$, it applies to any larger set of expressions closed under condition 1, as long as it still satisfies 3.

Now, it should be clear that EXP satisfies the assumptions of Richardson’s theorem: 1 and 2 hold essentially by definition, except that one has to construct $\mu(x)$ as $\sqrt{x^2}$ (as noted in the “P.P.S.”). As for 3, we may take $g(x)=\exp(x^2)$.

Reference:

[1] Daniel Richardson, Some undecidable problems involving elementary functions of a real variable, Journal of Symbolic Logic 33 (1968), no. 4, pp. 514–520. jstor

Answer 3

Pick a function $f(x)$ and either try to integrate its absolute value or try to integrate $\sqrt{f(x)}$ or $1/f(x)$. This will require you to solve $f(x) = 0$. And asking if there are any such solutions is undecidable for the class of functions you describe.

---

Edit it's not clear for a few reasons why or if this would actually do the trick.

But I feel we could pick $f(x)$ to be a polynomial without repeated roots. Then asking if the integral of $|f(x)|$ is a polynomial is undecidable.