Formal Definition
A real number a is computable if it can be approximated by some computable function in the following manner: given any integer, the function produces an integer k such that:
There are two similar definitions that are equivalent:
- There exists a computable function which, given any positive rational error bound, produces a rational number r such that
- There is a computable sequence of rational numbers converging to such that for each i.
There is another equivalent definition of computable numbers via computable Dedekind cuts. A computable Dedekind cut is a computable function which when provided with a rational number as input returns or, satisfying the following conditions:
An example is given by a program D that defines the cube root of 3. Assuming this is defined by:
A real number is computable if and only if there is a computable Dedekind cut D converging to it. The function D is unique for each irrational computable number (although of course two different programs may provide the same function).
A complex number is called computable if its real and imaginary parts are computable.
Read more about this topic: Computable Number
Famous quotes containing the words formal and/or definition:
“Then the justice,
In fair round belly with good capon lined,
With eyes severe and beard of formal cut,
Full of wise saws and modern instances;
And so he plays his part.”
—William Shakespeare (1564–1616)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)