Numerical Analysis

It has been suggested that "[infinitesimal] calculus" is an example of NonTuringComputation?, in the sense that there are mathematical techniques within that domain that cannot be represented by a halting program on a TuringMachine because there are infinities involved.

By "calculus" that author seems to mean "finding exact solutions to problems in mathematical analysis from first principles", and on that basis is probably correct.

Mathematical analysis relies completely on the closely related notions of limit and continuity. Programs that terminate on a Turing machine do not have access to these notions. Informally, limits, for example, are understood as processes involving infinitely small increments (formally, they are defined in terms of open sets). Clearly, the discrete and finite nature of a halting computer program means that such processes may only be approximated.

At root, the problem is that it is not meaningful to ask if two machine representations of real numbers are equal. The subject area NumericalAnalysis exists to circumvent this limitation and arrive at useful results with well-understood error bounds using reasonable resources.

See also NumericNotations


CategoryMath


EditText of this page (last edited April 28, 2008) or FindPage with title or text search