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:
“Two clergymen disputing whether ordination would be valid without the imposition of both hands, the more formal one said, “Do you think the Holy Dove could fly down with only one wing?””
—Horace Walpole (1717–1797)
“... 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)