Skip to main content
2 of 5
added 285 characters in body
Pat Devlin
  • 2.7k
  • 16
  • 21

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

Pat Devlin
  • 2.7k
  • 16
  • 21