Recursive Analysis & Computabilty for Real Numbers
This article outlines a standard definition of computability for the real numbers.
Introduction
The classic tradition of Turing computation over the natural numbers pioneered by Turing, Gödel, Church, and others underlies modern approaches to computability. In the classic tradition, the most important boundary limiting what may be computed by a Turing Machine is completeness, or decidability, summarised in another short paper on the topic. The basic problem of incompleteness has been extended to its most general form by Greg Chaitin, and the theory of Turing computation over the naturals can be usefully developed to include algebra and fields (Rabin 1960). But the fact that real physical systems are normally described by functions which take on real values motivates the extension of Turing computation to cover the real numbers R.
Recursion Theory
The field of recursive analysis develops natural number computation into a framework appropriate for the real numbers. Here I describe very briefly the standard recursion theoretic definitions of Pour-El and Richards (1989). (When I get around to sorting out HTML versions of the requisite equations, this will be a bit more precise; until then, it's better to go to Pour-El and Richards for the real story.)
A real number is said to be computable when there is a computable sequence of rationals which converges effectively to it. The upshot of these two requirements is that for any desired level of accuracy, a recursive natural number 'error function' indicates exactly how far through the sequence we must progress to guarantee that the sequence has converged with at least that level of precision. (It is clear, incidentally, that any real number which happens to be rational is, on this definition, straightforwardly computable, but not every computable real need be rational.) Intuitively, a real number is computable if it can be approximated to an arbitrary degree of accuracy by an algorithmic method. It is interesting that the set of all computable reals, like the set of rationals, is of course only denumerably infinite, while the set of all reals is uncountably infinite. Since all reals are either computable or noncomputable, this means that 'most' numbers are noncomputable (Minsky 1967).
Computability for a real-valued function, first formulated nearly four decades ago (Grzegorczyk 1955, 1957; Lacombe 1955a, 1955b), requires sequential computability and effective uniform continuity. A function defined over a closed, bounded, rectangle with computable corner points is sequentially computable when it maps computable sequences to computable sequences. The requirement of effective uniform continuity is satisfied when a particular algorithmic relationship obtains between the Euclidean distance separating points in the domain of the function and the distance between corresponding points in the range. Intuitively, we require that the sizes of neighbourhoods before and after the action of the function are computably related by a natural number function.
An Interesting Connection With Analogue Computation
It's easy to see that, in general, computability for the reals needn't have anything whatsoever to do with chaos (or vice versa). The definition of chaos, given in another of these short papers, refers to properties as different from those used in the definition of computability as apples are different from oranges.
No immediate inconsistency threatens the notion of such a real-valued function which meets the requirements of both sequential computability and effective uniform continuity and which also serves as the basis of a topologically transitive dynamical system with a state space densely covered with periodic points. But another of these short papers explores an interesting case of super-Turing computation in systems which are at once analogue and chaotic.
|
