![]() | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations .(July 2021) |
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. [1] 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 to 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; see § Basic results.
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.
A popular model for doing computable analysis is Turing machines. The tape configuration and interpretation of mathematical structures are described as follows.
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".
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 freedom is both an important one and philosophically unproblematic. [2] 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 (representing ), 0 and 1. In particular, this means can be represented both as and .
To understand why decimal notation is inappropriate, consider the problem of computing where and , and giving the result in decimal notation. The value of is either or . If the latter result were given for instance, then a finite number of digits of would be read before choosing the digit before the decimal point in — but then if the th digit of were decreased to 2, then the result for would be wrong. Similarly, the former choice for 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 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 program runs forever, generating increasingly more digits of the output.
Results about computability associated with infinite sets often involve namings, which are maps between those sets and recursive representations of subsets thereof. A naming on a set gives rise to a topology over that set, as elaborated upon below.
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. [3] These functions cannot be extended to arbitrary real numbers (without making them partial), as all computable functions 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.
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. [4] 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.
One of the basic results of computable analysis is that every computable function from to is continuous. [5] Taking this further, this suggests that there is an analogy between basic notions in topology and basic notions in computability:
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. [7] 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.
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact. Similarly, the space of rational numbers is not compact, because it has infinitely many "punctures" corresponding to the irrational numbers, and the space of real numbers is not compact either, because it excludes the two limiting values and . However, the extended real number linewould be compact, since it contains both infinities. There are many ways to make this heuristic notion precise. These ways usually agree in a metric space, but may not be equivalent in other topological spaces.
In mathematics, a Cauchy sequence is a sequence whose elements become arbitrarily close to each other as the sequence progresses. More precisely, given any small positive distance, all excluding a finite number of elements of the sequence are less than that given distance from each other. Cauchy sequences are named after Augustin-Louis Cauchy; they may occasionally be known as fundamental sequences.
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of unintuitive properties. It was discovered in 1874 by Henry John Stephen Smith and mentioned by German mathematician Georg Cantor in 1883.
In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive reals. The concept of a computable real number was introduced by Émile Borel in 1912, using the intuitive notion of computability available at the time.
In mathematics, a metric space is a set together with a notion of distance between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry.
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members. The number of elements is called the length of the sequence. Unlike a set, the same elements can appear multiple times at different positions in a sequence, and unlike a set, the order does matter. Formally, a sequence can be defined as a function from natural numbers to the elements at each position. The notion of a sequence can be generalized to an indexed family, defined as a function from an arbitrary index set.
In mathematics, a topological space is called separable if it contains a countable, dense subset; that is, there exists a sequence of elements of the space such that every nonempty open subset of the space contains at least one element of the sequence.
In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Other well-known examples of TVSs include Banach spaces, Hilbert spaces and Sobolev spaces.
In mathematics, a (real) interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. An interval can contain neither endpoint, either endpoint, or both endpoints.
Cantor's diagonal argument is a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers – informally, that there are sets which in some sense contain more elements than there are positive integers. Such sets are now called uncountable sets, and the size of infinite sets is treated by the theory of cardinal numbers, which Cantor began.
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
In mathematics, the Gelfand representation in functional analysis is either of two things:
In mathematics, Pontryagin duality is a duality between locally compact abelian groups that allows generalizing Fourier transform to all such groups, which include the circle group, the finite abelian groups, and the additive group of the integers, the real numbers, and every finite-dimensional vector space over the reals or a p-adic field.
In mathematics, the support of a real-valued function is the subset of the function domain containing the elements which are not mapped to zero. If the domain of is a topological space, then the support of is instead defined as the smallest closed set containing all points not mapped to zero. This concept is used widely in mathematical analysis.
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function with domain such that is a non-empty set for every , there exists a function with domain such that for every .
In several mathematical areas, including harmonic analysis, topology, and number theory, locally compact abelian groups are abelian groups which have a particularly convenient topology on them. For example, the group of integers, or the real numbers or the circle are locally compact abelian groups.
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions. Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions.
In mathematics, in the field of potential theory, the fine topology is a natural topology for setting the study of subharmonic functions. In the earliest studies of subharmonic functions, namely those for which where is the Laplacian, only smooth functions were considered. In that case it was natural to consider only the Euclidean topology, but with the advent of upper semi-continuous subharmonic functions introduced by F. Riesz, the fine topology became the more natural tool in many situations.
In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion.