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.



Can we decide whenever a function is the derivate of another function in this Language?
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](https://en.wikipedia.org/wiki/Richardson's_theorem) 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]


