Computable number
In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive reals. Equivalent definitions can be given using μ-recursive functions, Turing machines, or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes. Informal definition using a Turing machine as example. In the following, Marvin Minsky defines  the numbers to be computed in a manner similar to those defined by Alan Turing in 1936; i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1: The key notions in the definition are (1) that some "n" is specified at the start, (2) for any "n" the computation only takes a finite number of steps, after which the machine produces the desired output and terminates. An alternate form of (2) – the machine successively prints all "n" of the digits on its tape, halting after printing the "n"th – emphasizes Minsky's observation: (3) That by use of  a Turing machine, a "finite" definition – in the form of the machine's state table – is being used to define what is a potentially "infinite" string of decimal digits. This is however not the modern definition which only requires the result be accurate to within any given accuracy. The informal definition above is subject to a rounding problem called the table-maker's dilemma whereas the modern definition is not. Formal definition. A real number "a" is computable if it can be approximated by some computable function formula_1 in the following manner: given any positive integer "n", the function produces  an integer "f"("n") such that: There are two similar definitions that are equivalent: There is another equivalent definition of computable numbers via computable Dedekind cuts. A computable Dedekind cut is a computable function formula_8 which when provided with a rational number formula_9 as input returns formula_10 or formula_11, satisfying the following conditions: An example is given by a program "D" that defines the cube root of 3. Assuming formula_15 this is defined by: A real number is computable if and only if there is a computable Dedekind cut "D" corresponding to it. The function "D" is unique for each 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. Properties. Not computably enumerable. Assigning a Gödel number to each Turing machine definition produces a subset formula_18 of the natural numbers corresponding to the computable numbers and identifies a surjection from formula_18 to the computable numbers. There are only countably many Turing machines, showing that the computable numbers are subcountable. The set formula_18 of these Gödel numbers, however, is not computably enumerable (and consequently, neither are subsets of formula_18 that are defined in terms  of it). This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals. In order to produce a computable real, a Turing machine must compute a total function, but the corresponding decision problem is in Turing degree 0′′. Consequently, there is no surjective computable function from the natural numbers to the computable reals, and Cantor's diagonal argument cannot be used constructively to demonstrate uncountably many of them. While the set of real numbers is uncountable, the set of computable numbers is classically countable and thus almost all real numbers  are not computable. Here, for any given computable number formula_22 the well ordering principle provides that there is a minimal element in formula_18 which corresponds to formula_24, and therefore there exists a subset consisting of the minimal elements, on which the map is a bijection. The inverse of this bijection is an injection into the natural numbers of the computable numbers, proving that they are countable. But, again, this subset is not computable, even though the computable reals are themselves ordered. Properties as a field. The arithmetical operations on computable numbers are themselves computable in the sense that whenever real  numbers "a" and "b" are computable then the following real numbers are also computable: "a + b", "a - b", "ab", and "a/b" if "b" is nonzero. These operations are actually "uniformly computable"; for example, there is a Turing machine which on input ("A","B",formula_25) produces output "r", where "A" is the description of a Turing machine approximating "a", "B" is the description of a Turing machine approximating "b", and "r" is an formula_25 approximation of "a"+"b". The fact that computable real numbers form a field was first proved by Henry Gordon Rice in 1954. Computable reals however do not form  a computable field, because the definition of a computable field requires effective equality. Non-computability of the ordering. The order relation on the computable numbers is not computable. Let "A" be the description of a Turing machine approximating the number formula_6. Then there is no Turing machine which on input "A" outputs "YES" if formula_28 and "NO" if formula_29 To see why, suppose the machine described by "A" keeps outputting 0 as formula_25 approximations. It is not clear how long to wait before deciding that the machine will "never" output an approximation which forces "a" to be positive. Thus the  machine will eventually have to guess that the number will equal 0, in order to produce an output; the sequence may later become different from 0. This idea can be used to show that the machine is incorrect on some sequences if it computes a total function. A similar problem occurs when the computable reals are represented as Dedekind cuts. The same holds for the equality relation : the equality test is not computable. While the full order relation is not computable, the restriction of it to pairs of unequal numbers is computable. That is, there is a program that takes  as input two Turing machines "A" and "B" approximating numbers "a" and "b", where "a" ≠ "b", and outputs whether formula_31 or formula_32 It is sufficient to use "ε"-approximations where formula_33 so by taking increasingly small ε (approaching 0), one eventually can decide whether formula_31 or formula_32 Other properties. The computable real numbers do not share all the properties of the real numbers used in analysis. For example, the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number. A sequence with this property is known as a Specker sequence , as the first construction is due to Ernst Specker in 1949. Despite the existence of counterexamples such as these, parts of calculus and real analysis can be developed in the field of computable numbers, leading to the study of computable analysis. Every computable number is arithmetically definable, but not vice versa. There are many arithmetically definable, noncomputable real numbers, including: Both of these examples in fact define an infinite set of definable, uncomputable numbers, one for each Universal Turing machine. A real number is computable if and only if the set of natural numbers it represents (when written in binary  and viewed as a characteristic function) is computable. The set of computable real numbers (as well as every countable, densely ordered subset of computable reals without ends) is order-isomorphic to the set of rational numbers. Digit strings and the Cantor and Baire spaces. Turing's original paper defined computable numbers as follows: Turing was aware that this definition is equivalent to the formula_25-approximation definition given above. The argument proceeds as follows: if a number is computable in the Turing sense, then it is also computable in the formula_25 sense: if formula_39, then the first "n" digits of the  decimal expansion for "a" provide an formula_25 approximation of "a". For the converse, we pick an formula_25 computable real number "a" and generate increasingly precise approximations until the "n"th digit after the decimal point is certain. This always generates a decimal expansion equal to "a" but it may improperly end in an infinite sequence of 9's in which case it must have a finite (and thus computable) proper decimal expansion. Unless certain topological properties of the real numbers are relevant it is often more convenient to deal with elements of formula_42 (total 0,1 valued functions) instead of reals numbers  in formula_43. The members of formula_42 can be identified with binary decimal expansions but since the decimal expansions formula_45 and formula_46 denote the same real number the interval formula_43 can only be bijectively (and homeomorphically under the subset topology) identified with the subset of formula_42 not ending in all 1's. Note that this property of decimal expansions means it's impossible to effectively identify computable real numbers defined in terms of a decimal expansion and those defined in the formula_25 approximation sense. Hirst has shown there is no algorithm which takes as input the description of a Turing machine  which produces formula_25 approximations for the computable number "a", and produces as output a Turing machine which enumerates the digits of "a" in the sense of Turing's definition. Similarly it means that the arithmetic operations on the computable reals are not effective on their decimal representations as when adding decimal numbers, in order to produce one digit it may be necessary to look arbitrarily far to the right to determine if there is a carry to the current location. This lack of uniformity is one reason that the contemporary definition of computable numbers uses formula_25 approximations rather than decimal  expansions. However, from a computational or measure theoretic perspective the two structures formula_42 and formula_43 are essentially identical, and computability theorists often refer to members of formula_42 as reals. While formula_43 formula_42 is totally disconnected, for questions about formula_57 classes or randomness it's much less messy to work in formula_42. Elements of formula_59 are sometimes called reals as well and though containing a homeomorphic image of formula_60 formula_59 in addition to being totally disconnected isn't even locally compact. This leads to genuine differences in the computational properties. For instance the formula_62 satisfying formula_63 with formula_64 quantifier free must  be computable while the unique formula_65 satisfying a universal formula can be arbitrarily high in the hyperarithmetic hierarchy. Use in place of the reals. The computable numbers include the specific real numbers which appear in practice, including all real algebraic numbers, as well as "e", "π", and many other transcendental numbers. Though the computable reals exhaust those reals we can calculate or approximate, the assumption that all reals are computable leads to substantially different conclusions about the real numbers. The question naturally arises of whether it is possible to dispose of the full set of reals and use computable numbers  for all of mathematics. This idea is appealing from a constructivist point of view, and has been pursued by what Errett Bishop and Fred Richman call the "Russian school" of constructive mathematics. To actually develop analysis over computable numbers, some care must be taken. For example, if one uses the classical definition of a sequence, the set of computable numbers is not closed under the basic operation of taking the supremum of a bounded sequence (for example, consider a Specker sequence, see the section above). This difficulty is addressed by considering only sequences which have a computable modulus of convergence . The resulting mathematical theory is called computable analysis. Implementations of exact arithmetic. Computer packages representing real numbers as programs computing approximations have been proposed as early as 1985, under the name "exact arithmetic". Modern examples include the CoRN library (Coq), and the RealLib package (C++). A related line of work is based on taking a real RAM program and running it with rational or floating-point numbers of sufficient precision, such as the iRRAM package.