-2
$\begingroup$

Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?

The particular case I am wondering about is if the exact solution for the perimeter of an ellipse is computable. I am aware that the only readily available solutions are approximations, but I wonder if it might be computable in principle.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ It is very tricky to make precise what it means to be computable; please use a precise expression here. $\endgroup$
    – Ben McKay
    Commented Jan 18, 2023 at 15:19
  • $\begingroup$ I agree with @BenMcKay ... Would you say the greatest integer $\lfloor x \rfloor$ is computable? Is it elementary? ... Is the condition $x=0$ computable? $\endgroup$
    – Gerald Edgar
    Commented Jan 18, 2023 at 17:08

1 Answer 1

Reset to default
6
$\begingroup$

Obviously the perimeter of an ellipse is a computable function of the parameters (e.g. semi-major and semi-minor axes). What it means for this to be computable is precisely that we can compute approximations that converge within desired accuracy.

This perspective is a core definition of computable analysis, which provides notions of computability for functions on the reals.

In particular, in that account the computable functions on the reals do not generally align with the elementary functions. One can see this simply by diagonalizing against the elementary functions. That is, make a (computable) list of all of them, and then design a function $d(x)$ that at $x=n$ deviates from the $n$th function on the list, but otherwise smoothly joins these values. This is a computable function that is not elementary.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The elementary functions are usually given to include all real constant functions, so they are not countable. $\endgroup$
    – Ben McKay
    Commented Jan 18, 2023 at 18:25
  • $\begingroup$ Ah, my diagonalization works only with respect to the parameter-free case. $\endgroup$
    – Joel David Hamkins
    Commented Jan 18, 2023 at 18:48
  • $\begingroup$ Related curiosity: is there any elementary function which is not computable? $\endgroup$
    – Jango
    Commented Jan 17 at 20:12
  • 1
    $\begingroup$ @Jango As Ben mentioned, if every real constant function counts as elementary, then some of them must be noncomputable, since there are only countably many computable functions. But if one has a weaker notion, then they will all be computable, since the computable functions are closed under composition. $\endgroup$
    – Joel David Hamkins
    Commented Jan 17 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .