Let's assume we're talking about real functions purely for clarity purposes, but my question is more general.

We say that a function $f$ is computable, if for a given $x$, a turing machine can output $y$ such that $f(x)=y$.

However, I'm wondering whether there is some concept of "computability for the expresssion of a function". For example, let's say I have some implicitly defined function $f$, and let's say that this function is equivalent to $g(x)=\sin(x)$, but we don't know this yet. Then what we would want is to compute the fact that $f(x)=\sin (x)$, but we don't necessarily need to compute that $f(0.45)=0.434965534...$

Is there a concept that rigorously captures this idea of the expression of a function being computable, rather than the function itself being computable? In other words, it may be that a function is incomputible, but that there is at least a finite number of computations we can do to derive that it has a certain closed form expression.

  • $\begingroup$ The question is unclear. Are you essentially asking if, given two expressions involving variables, it is decidable if they are equal (for all values of such variables)? $\endgroup$ – chi Dec 8 '17 at 10:47
  • $\begingroup$ @chi, that is close. However, I'm not assuming we know the second expression. An example of what I'm talking about is very simple: Assume we have a differential equation in terms of the function $f$, and then want to know what the closed form expression of $f$ is. The answer to the problem may be that $f(x)=\Gamma(x)$ (the gamma function). The problem of finding a closed form solution for a function may be computable, even if this function $f$ itself is not computable. $\endgroup$ – user56834 Dec 8 '17 at 11:15
  • $\begingroup$ well, what's the difference from this question and the one asking if any two functions in lambda calculus are equivalent(or equal)? it's known to be undecidable, unless you restrict your scope, which is not mentioned in your question. $\endgroup$ – Jason Hu Jan 7 '18 at 23:33
  • $\begingroup$ It sounds like you're looking for symbolic computation and computer algebra systems. Algorithms in this area do things like "find closed form of a sum" and "find closed form of an integral". $\endgroup$ – Andrej Bauer Mar 8 '18 at 21:53

I assume that a closed form of a function is a finite expression involving function symbols from some fixed natural finite list together with some real[1] parameters. Since we know what it means to compute a real number, and since we know what it means to compute finite tuples of stuff we know how to compute with, we obtain in a direct way a notion of what it means to compute a closed form of a function.

Then in particular we can ask questions such as "given these parameters for the differential equation, can we compute a closed form of the solution".

Note however that all usual continuous functions are computable. Given a closed form of a function $f$ and some input $x \in \mathbb{R}$, we can compute $f(x)$. However, the problem "given a continuous function that has a closed form, find that closed form" is not computable.

So asking for closed forms is asking for more, not asking for less.

[1] If you don't like computing with real numbers, go for parameters from the algebraic closure of $\mathbb{Q}[\pi,e]$ instead.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.