Computable analysis

In mathematics and computer science, computable analysis is the study of mathematical analysis from the perspective of computability theory. It is concerned with the parts of real analysis and functional analysis that can be carried out in a computable manner. The field is closely related to constructive analysis and numerical analysis.

A notable result is that integration (in the sense of the Riemann integral) is computable. This might be considered surprising as an integral is (loosely speaking) an infinite sum. While this result could be explained by the fact that every computable function from [math]\displaystyle{ \mathbb [0,1] }[/math] to [math]\displaystyle{ \mathbb R }[/math] is uniformly continuous, the notable thing is that the modulus of continuity can always be computed without being explicitly given. A similarly surprising fact is that differentiation of complex functions is also computable, while the same result is false for real functions.

The above motivating results have no counterpart in Bishop's constructive analysis. Instead, it is the stronger form of constructive analysis developed by Brouwer that provides a counterpart in constructive logic.

Basic constructions

A popular model for doing computable analysis is Turing machines. The tape configuration and interpretation of mathematical structures are described as follows.

Type 2 Turing Machines

A Type 2 Turing machine is a Turing machine with three tapes: An input tape, which is read-only; a working tape, which can be written to and read from; and, notably, an output tape, which is "append-only".

Real numbers

In this context, real numbers are represented as arbitrary infinite sequences of symbols. These sequences could for instance represent the digits of a real number. Such sequences need not be computable — this allowance is both important and philosophically unproblematic. Note that the programs that act on these sequences do need to be computable in a reasonable sense.

In the case of real numbers, the usual decimal or binary representations are not appropriate. Instead a signed digit representation first suggested by Brouwer often gets used: The number system is base 2, but the digits are [math]\displaystyle{ \overline 1 }[/math] (representing [math]\displaystyle{ -1 }[/math]), 0 and 1. In particular, this means [math]\displaystyle{ 1/2 }[/math] can be represented both as [math]\displaystyle{ 0.1 }[/math] and [math]\displaystyle{ 1. \overline1 }[/math].

To understand why decimal notation is inappropriate, consider the problem of computing [math]\displaystyle{ z=x+y }[/math] where [math]\displaystyle{ x = 0.(3) }[/math] and [math]\displaystyle{ y=0.(6) }[/math], and giving the result [math]\displaystyle{ z }[/math] in decimal notation. The value of [math]\displaystyle{ z }[/math] is either [math]\displaystyle{ 0.(9) }[/math] or [math]\displaystyle{ 1.(0) }[/math]. If the latter result were given for instance, then a finite number [math]\displaystyle{ n }[/math] of digits of [math]\displaystyle{ x }[/math] would be read before choosing the digit [math]\displaystyle{ 1 }[/math] before the decimal point in [math]\displaystyle{ z }[/math] — but then if the [math]\displaystyle{ n+1 }[/math]th digit of [math]\displaystyle{ x }[/math] were decreased to 2, then the result for [math]\displaystyle{ z }[/math] would be wrong. Similarly, the former choice [math]\displaystyle{ 0.(9) }[/math] for [math]\displaystyle{ z }[/math] would be wrong sometimes. This is essentially the tablemaker's dilemma.

As well as signed digits, there are analogues of Cauchy sequences and Dedekind cuts that could in principle be used instead.

Computable functions

Computable functions are represented as programs on a Type 2 Turing machine. A program is considered total (in the sense of a total function as opposed to partial function) if it takes finite time to write any number of symbols on the output tape regardless of the input. A total programs run forever, generating increasingly more digits of the output.

Names

Results about computability associated with infinite sets often involve namings, which are maps between those sets and recursive representations of subsets thereof.

Discussion

The issue of Type 1 versus Type 2 computability

Type 1 computability is the naive form of computable analysis in which one restricts the inputs to a machine to be computable numbers instead of arbitrary real numbers.

The difference between the two models lies in the fact that a program that is well-behaved over computable numbers (in the sense of being total) is not necessarily well-behaved over arbitrary real numbers. For instance, there are computable functions over the computable real numbers that map some bounded closed intervals to unbounded open intervals. These functions cannot be extended to arbitrary real numbers (without making them partial), as all computable functions [math]\displaystyle{ \mathbb R \to \mathbb R }[/math] are continuous, and this would then violate the extreme value theorem. Since that sort of behaviour could be considered pathological, it is natural to insist that a function should only be considered total if it is total over all real numbers, not just the computable ones.

Realisability

In the event that one is unhappy with using Turing machines (on the grounds that they are low level and somewhat arbitrary), there is a realisability topos called the Kleene–Vesley topos in which one can reduce computable analysis to constructive analysis. This constructive analysis includes everything that is valid in the Brouwer school, and not just the Bishop school. Additionally, a theorem in this school of constructive analysis is that not all real numbers are computable, which is constructively non-equivalent to there exist uncomputable numbers. This school of constructive analysis is therefore in direct contradiction to schools of constructive analysis — such as Markov's — which claim that all functions are computable. It ultimately shows that while constructive existence implies computability, it is in fact unproblematic — even useful — to assert that not every function is computable.

Basic results

• Every computable real function is continuous.

• The arithmetic operations on real numbers are computable.

• While the equality relation is not decidable, the greater-than predicate on unequal real numbers is decidable.

• The uniform norm operator is also computable. This implies the computability of Riemann integration.

• The Riemann integral is a computable operator: In other words, there is an algorithm that will numerically evaluate the integral of any computable function.

• The differentiation operator over real-valued functions is not computable, but over complex functions is computable. The latter result follows from Cauchy's integral formula and the computability of integration. The former negative result follows from the fact that differentiation (over real-valued functions) is discontinuous. This illustrates the gulf between real analysis and complex analysis, as well as the difficulty of numerical differentiation over the real numbers, which is often bypassed by extending a function to the complex numbers or by using symbolic methods.

• There is a subset of the real numbers called the computable numbers, which by the results above is a real closed field.

Analogy between general topology and computability theory

One of the basic results of computable analysis is that every computable function from [math]\displaystyle{ \mathbb R }[/math] to [math]\displaystyle{ \mathbb R }[/math] is continuous. Taking this further, this suggests that there is an analogy between basic notions in topology and basic notions in computability:

• Computable functions are analogous to continuous functions.
• Semidecidable sets are analogous to open sets.
• Co-semidecidable sets are analogous to closed sets.
• There is a computable analogue of topological compactness. Namely, a subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ \mathbb R }[/math] is computably compact if it there is a semi-decision procedure "[math]\displaystyle{ \forall_S }[/math]" that, given a semidecidable predicate [math]\displaystyle{ P }[/math] as input, semi-decides whether every point in the set [math]\displaystyle{ S }[/math] satisfies the predicate [math]\displaystyle{ P }[/math].
• The above notion of computable compactness satisfies an analogue of the Heine–Borel theorem. In particular, the unit interval [math]\displaystyle{ [0,1] }[/math] is computably compact.
• Discrete spaces in topology are analogous to sets in computability where equality between elements is semi-decidable.
• Hausdorff spaces in topology are analogous to sets in computability where inequality between elements is semi-decidable.

The analogy suggests that general topology and computability are nearly mirror images of each other. The analogy has been made rigorous in the case of locally compact spaces. This has resulted in the creation of sub-areas of general topology like domain theory which study topological spaces very unlike the Hausdorff spaces studied by most people in mathematical analysis — these spaces become natural under the analogy.

See also

• Specker sequence

References

• Oliver Aberth (1980), Computable analysis, McGraw-Hill, ISBN 0-0700-0079-4.
• Marian Pour-El and Ian Richards (1989), Computability in Analysis and Physics, Springer-Verlag.
• Stephen G. Simpson (1999), Subsystems of second-order arithmetic.
• Klaus Weihrauch (2000), Computable analysis, Springer, ISBN 3-540-66817-9.

External links

• Computability and Complexity in Analysis Network