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.