Content deleted Content added
lk, grammar |
|||
Line 20:
To understand why decimal notation is inappropriate, consider the problem of computing <math>z=x+y</math> where <math>x = 0.(3)</math> and <math>y=0.(6)</math>, and giving the result <math>z</math> in decimal notation. The value of <math>z</math> is either <math>0.(9)</math> or <math>1.(0)</math>. If the latter result were given for instance, then a finite number <math>n</math> of digits of <math>x</math> would be read before choosing the digit <math>1</math> before the decimal point in <math>z</math> — but then if the <math>n+1</math>th digit of <math>x</math> were decreased to 2, then the result for <math>z</math> would be wrong. Similarly, the former choice <math>0.(9)</math> for <math>z</math> would be wrong sometimes. This is essentially the [[Table-maker's dilemma|tablemaker's dilemma]].
As well as signed digits, there are analogues of [[Cauchy
===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
===Names===
Line 41:
* Every computable real function is [[continuous function|continuous]].<ref name=":0">Weihrauch 2000, p. 6.</ref>
* The arithmetic operations on real numbers are computable.
* While the [[Equality (mathematics)|equality]] relation is not [[Decidability (logic)|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 linear map|discontinuous]].<ref>{{Cite journal |last=Myhill |first=J. |date=1971 |title=A recursive function, defined on a compact interval and having a continuous derivative that is not recursive. |journal=Michigan Mathematical Journal |volume=18 |issue=2 |doi=10.1307/mmj/1029000631 |issn=0026-2285|doi-access=free }}</ref> 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 number]]s 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]].
Line 64 ⟶ 58:
* [[Discrete space]]s in topology are analogous to sets in computability where equality between elements is semi-decidable.
* [[Hausdorff space]]s 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
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 space|locally compact spaces]].<ref>{{Cite web |title=abstract Stone duality in nLab |url=https://ncatlab.org/nlab/show/abstract+Stone+duality |access-date=2023-07-29 |website=ncatlab.org}}</ref> This has resulted in the creation of sub-areas of general topology like [[___domain theory]] which study [[Topological space|topological spaces]] very unlike the [[Hausdorff space|Hausdorff spaces]] studied by most people in [[mathematical analysis]] — these spaces become natural under the analogy.
| |||