2
$\begingroup$

I am wondering, if the Church-Turing thesis holds (all effectively calculable functions are computable by Turing machines/lambda calculus) and I can compute the limit of a function by hand, what is the encoding of e.g. the derivative $\lim_{h\to 0} \frac{df(x)}{dh} = \frac{f(x+h)-f(x)}{h}$.

I know the encoding for the divide and plus sequences, but how would one encode the limit?

$\endgroup$
10
  • $\begingroup$ I think that issues like this might give you some trouble $\endgroup$
    – Ben Grossmann
    Dec 16, 2014 at 0:16
  • $\begingroup$ See also this question $\endgroup$
    – Ben Grossmann
    Dec 16, 2014 at 0:22
  • $\begingroup$ this sounds like turing machines and our models of computability have problems dealing with real numbers in general $\endgroup$
    – qrzx
    Dec 16, 2014 at 0:28
  • $\begingroup$ Yes, and real numbers are extremely important to our understanding of limits, and hence derivatives. $\endgroup$
    – Ben Grossmann
    Dec 16, 2014 at 0:30
  • $\begingroup$ Are there any models of computation that allow for computation with reals ( or a representation of reals )? I found this Wikipedia entry stating it is probably impossible to realize reals in our universe, but surely there must be approaches to deal with them in an abstract form? $\endgroup$
    – qrzx
    Dec 16, 2014 at 0:36

1 Answer 1

Reset to default
1
$\begingroup$

First of all, we have to be careful here. Just because you and I can solve particular limits by hand, do you have an algorithmic method (by hand or otherwise) to solve limits that'll work for EVERY limit problem?

Also, it would be impossible to represent the result of each limit problem finitely since the cardinality of the reals outnumber the cardinality of finite length strings over any finite alphabet. Because of this, I would say computing limits in general (and thus derivatives) is uncomputable.

Of course however, there are numerical methods that give us good approximations for these kind of things.

$\endgroup$

You must log in to answer this question.

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