Computable analysis: Difference between revisions

Revision as of 17:09, 5 January 2025

Latest revision as of 03:21, 7 July 2025

(3 intermediate revisions by 2 users not shown)

Line 3:

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 [[computability theory|computable]] manner. The field is closely related to [[constructive analysis]] and [[numerical analysis]].

A notable result is that [[integral|integration]] (in the sense of the [[Riemann integral]]) is computable.<ref>See {{Citation |last=Simpson |first=Alex K. |title=Lazy functional algorithms for exact real functionals |date=1998 |url=http://link.springer.com/10.1007/BFb0055795 |work=Mathematical Foundations of Computer Science 1998 |series=Lecture Notes in Computer Science |volume=1450 |pages=456–464 |editor-last=Brim |editor-first=Luboš |access-date= |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/bfb0055795 |isbn=978-3-540-64827-7 |editor2-last=Gruska |editor2-first=Jozef |editor3-last=Zlatuška |editor3-first=Jiří|url-access=subscription }}</ref> 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>\mathbb [0,1]</math> to <math>\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 [[differential calculus|differentiation]] of [[complex functions]] is also computable, while the same result is ''false'' for [[real functions]]; see {{section link||Basic results}}.

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

Line 36:

===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 [[Stephen Cole Kleene|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.<ref>{{Cite web |last=Bauer, |first=Andrej |title=The Realizability Approach to Computable Analysis |url=https://math.andrej.com/wp-content/uploads/2006/04/thesis.pdf |access-date=2025-01-06 |website=math.andrej.com |language=en}}</ref> 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 [[Existence property|constructive existence]] implies computability, it is in fact unproblematic — even useful — to assert that not every function is computable.

== Basic results ==