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 \mathbb ,1/math> to $\mathbb R$ 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. On the other hand, the programs that act on these sequences ''do'' need to be computable in a reasonable sense.

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. The 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 function 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 continuous and computable functions over the computable real numbers that are total, but that map some closed intervals to unbounded open intervals. These functions clearly cannot be extended to arbitrary real numbers without making them partial, as doing so would 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.

Basic results

Every computable real function is continuous (Weihrauch 2000, p. 6).

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 $\mathbb R$ to $\mathbb R$ is continuous (Weihrauch 2000, p. 6). 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-semideciable sets are analogous to closed sets.
* There is a computable analogue of topological compactness. Namely, a subset $S$ of $\mathbb R$ is ''computably compact'' if it there is a semi-decision procedure "$\forall_S$" that, given a semidecidable predicate $P$ as input, semi-decides whether every point in the set $S$ satisfies the predicate $P$.
* The above notion of computable compactness satisfies an analogue of the Heine–Borel theorem. In particular, the unit interval ,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 can be explained by using the fact that computability theory and general topology can both be performed using constructive logic.

See also

* Specker sequence

References

* Oliver Aberth (1980), ''Computable analysis'', McGraw-Hill, .
* 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


Constructivism (mathematics)
Computability theory