This article outlines a standard definition of computability for the real numbers.
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.
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.
- Research Archive
- About the Research Archive
- Drafts and Unfinished Papers
- International Workshop on Robot Cognition
- Mind Out of Matter
- Research Bibliography
- Supplementary Bibliography from Mind Out of Matter
- Tutorials and Introductions
- Biological Cognition & Universal Computation
- Chaos Theory
- Complexity & Information Theory
- Computability and Completeness
- Emergence and Levels of Description
- Models of Computation: Turing Machines and Finite Automata
- Philosophers’ Zombies and their Role in Cognitive Science
- Quantum Decoherence
- Recursion Theory
- Soul Searching (TV Documentary)
This article was originally published by Dr Greg Mulhauser on .on and was last reviewed or updated by