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 conviction that the best way to prepare children for a harsh, rapidly changing world is to introduce formal instruction at an early age is wrong. There is simply no evidence to support it, and considerable evidence against it. Starting children early academically has not worked in the past and is not working now.
    David Elkind (20th century)

    According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.
    Ana Castillo (b. 1953)