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)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)