OSDev.org

NickJohnson wrote:Are you sure about that? I know it's possible to finitely approximate a limit to an arbitrary position, but I'm not sure there is a way to compute it precisely. From the stuff I've been reading it seems like you can't always do that and can't compute whether it's possible for a specific formula or not. I think calculus is not computable by a Turing machine.

Lambda Calculus != Turing Machine

I'm not talking about lambda calculus, I'm talking about Newtonian calculus: series, derivatives, integrals etc. The issue is that normal calculus relies on the limit to derive and prove those things. Of course, once you have the derivative/integral formula for a function, you can just plug it in, but the idea is to have the computer derive it instead of you. Otherwise your calculus subroutines are just a bunch of edge cases.

And lambda calculus *is* computationally equivalent to the Turing machine. That's one of the major parts of the Church-Turing thesis, and why functional languages work.

NickJohnson wrote:I'm not talking about lambda calculus, I'm talking about Newtonian calculus: series, derivatives, integrals etc. The issue is that normal calculus relies on the limit to derive and prove those things. Of course, once you have the derivative/integral formula for a function, you can just plug it in, but the idea is to have the computer derive it instead of you. Otherwise your calculus subroutines are just a bunch of edge cases.

And lambda calculus *is* computationally equivalent to the Turing machine. That's one of the major parts of the Church-Turing thesis, and why functional languages work.

Okay, basically, mathematics in total is just a symbolic representation of a process. Since all of the mathematics is just manipulation of symbols following thought experiments (at base), they can be expressed as a manipulation of symbols just as easily. Thus, for instance, the Power Rule for derivatives (forgive the short Calc. lesson) is defined as f(x) = nx^(n-1) or (lambda (x) (* n (expt x (- n 1)))). Therefore, the derivative of f(x) = 3x^2 or (lambda (x) (* 3 (expt x 2))), is simplified f(x) = 6x or (lambda (x) (* x 6)). Again, this is just a simple example of symbolic manipulation. These manipulations are trivial, especially in a language as expressive as Lisp or Scheme. However, interpretation of these symbols is the complicated part which is left up to the person him/herself. Given infinite time and infinite space it's possible to interpret and compute the more complicated theories including limits., at least as far as I understand it. (Correct me if I am wrong, please.).

syntropy wrote:Given infinite time and infinite space it's possible to interpret and compute the more complicated theories including limits., at least as far as I understand it. (Correct me if I am wrong, please.).

Given infinite time and infinite space you would be able to calculate anything... you would just never get the result (only after infinite time... which means never). A more serious question is whether, given infinite space (the tape on a Turing machine), you can calculate something in finite time, ie. the calculation ends and yields a result.

Whether that is the case for calculating limits in calculus, I simply don't know.

Walling wrote:Whether that is the case for calculating limits in calculus, I simply don't know.

I see two approaches to the problem. Either you can calculate the limits and somehow derive the derivate functions from that; or you can use an analytical approach and do some pattern matching (ie. derive(x^2) = 2x; derive(sin(x)) = cos(x); and so on). The problem with the first approach is that it's inexact, even if you could calculate the limits of an arbitrary function at an arbitrary x value. The problem with the second approach that there exist some functions which have no closed-form derivates (unfortunately I haven't touched analysis in quite a few years and I can't come up with an example, but I do remember that they exist), or the derivate of the function can't be interpreted everywhere (for example abs(x) is interpreted on R, while you can't calculate the limit/derivate of this function at x=0, because it just doesn't exist).

Either way, I see no practical use of it. Take a piece of paper and work out the limits by hand