computable analysis

study of mathematical analysis from the perspective of computability theory

Uses your system voice; voice and rate in settings.

≈ 10 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

  • eokomputebla analitiko
  • Englishcomputable analysis
  • Españolanálisis computable
  • Françaisanalyse calculable
  • Portuguêsanálise computável
  • 日本語計算可能解析学
  • 中文可計算性分析

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 [0,1] 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.

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.

  • 2 Discussion
  • 3 Basic results
  • 4 Analogy with topology
  • 5 See also
  • 6 Notes
  • 7 References
  • 8 External links
  • Basic constructions

    edit edit source

    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

    edit edit source

    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

    edit edit source

    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 1‾ (representing −1), 0 and 1. In particular, this means 1/2 can be represented both as 0.1 and 1.1‾.

    To understand why decimal notation is inappropriate, consider the problem of computing z=x+y where x=0.(3) and y=0.(6), and giving the result z in decimal notation. The value of z is either 0.(9) or 1.(0). If the latter result were given for instance, then a finite number n of digits of x would be read before choosing the digit 1 before the decimal point in z, but then, if the (n+1)st digit of x were decreased to 2, then the result for z would be wrong. Similarly, the former choice 0.(9) for z 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

    edit edit source

    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.

    Names

    edit edit source

    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.

    Discussion

    edit edit source

    The issue of Type 1 versus Type 2 computability

    edit edit source

    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.

    Realisability

    edit edit source

    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.

    Basic results

    edit edit source

    Analogy with topology

    edit edit source

    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:

    • 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 S of ℝ is computably compact if it there is a semi-decision procedure "∀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 [0,1] 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.
    • There is a close analogy between the degrees of discontinuity of functions in the Borel hierarchy and the degrees of incomputability provided by the Weihrauch hierarchy.

    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 that study topological spaces very unlike the Hausdorff spaces studied by most people in mathematical analysis — these spaces become natural under the analogy.

    See also

    edit edit source

    Notes

    edit edit source
    1. ^ Simpson (1998). Wikipedia revision 1368992915, retrieved 2026-11-20
    2. ^ An uncomputable real number can be generated with near certainty by sampling each digit at random in an infinite unending process. Wikipedia revision 1368992915, retrieved 2026-11-20
    3. ^ Bauer, Andrej. "Kőnig's Lemma and Kleene Tree" (PDF). Wikipedia revision 1368992915, retrieved 2026-11-20
    4. ^ Bauer, Andrej. "The Realizability Approach to Computable Analysis" (PDF). math.andrej.com. Retrieved 2025-01-06. Wikipedia revision 1368992915, retrieved 2026-11-20
    5. ^ a b Weihrauch (2000), p. 6. Wikipedia revision 1368992915, retrieved 2026-11-20
    6. ^ Myhill (1971). Wikipedia revision 1368992915, retrieved 2026-11-20
    7. ^ "Abstract Stone duality". nLab. Retrieved 11 August 2026. Wikipedia revision 1368992915, retrieved 2026-11-20

    References

    edit edit source edit edit source

    Text derived from https://en.wikipedia.org/w/index.php?oldid=1368992915 under CC BY-SA 4.0; modifications have been made.

    Words in each sectionBasic constructionsBasic constructionsBasic constructions: 437 words437DiscussionDiscussionDiscussion: 305 words305Analogy with topologyAnalogy with topologyAnalogy with topology: 258 words258Basic resultsBasic resultsBasic results: 181 words181NotesNotesNotes: 101 words101See alsoSee alsoSee also: 5 words5
    Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

    Provenance

    snapshot computable-analysis-587633-9d2850c3e8fbb018 · hash 9d2850c3e8fbb01842107c208a64e58939f4ec961e0f952d1ebc0f99d65bcad3 · captured 2026-08-12 · ledger · version history

    Cite this page as: encyclopegia.org, “computable analysis”, snapshot computable-analysis-587633-9d2850c3e8fbb018. https://encyclopegia.org/a/computable-analysis