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](http://www.jstor.org/stable/2271358)