Computable Number - Formal Definition

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:

    The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.
    Edgar Lee Masters (1869–1950)

    Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.
    Walter Pater (1839–1894)