Editing Computable number (section)

==Formal definition==
A [[real number]] ''a'' is '''computable''' if it can be approximated by some [[computable function]] <math>f:\mathbb{N}\to\mathbb{Z}</math> in the following manner: given any positive [[integer]] ''n'', the function produces an integer ''f''(''n'') such that:

:<math>{f(n)-1\over n} \leq a \leq {f(n)+1\over n}.</math>

A [[complex number]] is called computable if its real and imaginary parts are computable.

===Equivalent definitions===
There are two similar definitions that are equivalent:
*There exists a computable function which, given any positive rational [[error bound]] <math>\varepsilon</math>, produces a [[rational number]] ''r'' such that <math>|r - a| \leq \varepsilon.</math>
*There is a computable sequence of rational numbers <math>q_i</math> converging to <math>a</math> such that <math>|q_i - q_{i+1}| < 2^{-i}\,</math> for each ''i''.

There is another equivalent definition of computable numbers via computable [[Dedekind cut]]s. A '''computable Dedekind cut''' is a computable function <math>D\;</math> which when provided with a rational number <math>r</math> as input returns <math>D(r)=\mathrm{true}\;</math> or <math>D(r)=\mathrm{false}\;</math>, satisfying the following conditions:
:<math>\exists r D(r)=\mathrm{true}\;</math>
:<math>\exists r D(r)=\mathrm{false}\;</math>
:<math>(D(r)=\mathrm{true}) \wedge (D(s)=\mathrm{false}) \Rightarrow r<s\;</math>
:<math>D(r)=\mathrm{true} \Rightarrow \exist s>r, D(s)=\mathrm{true}.\;</math>
An example is given by a program ''D'' that defines the [[cube root]] of 3. Assuming <math>q>0\;</math> this is defined by:
:<math>p^3<3 q^3 \Rightarrow D(p/q)=\mathrm{true}\;</math>
:<math>p^3>3 q^3 \Rightarrow D(p/q)=\mathrm{false}.\;</math>

A real number is computable if and only if there is a computable Dedekind cut ''D'' corresponding to it. The function ''D'' is unique for each computable number (although of course two different programs may provide the same function).