Editing Computable number (section)

==Properties==

===Not computably enumerable===
Assigning a [[Gödel number]] to each Turing machine definition produces a subset <math>S</math> of the [[natural number]]s corresponding to the computable numbers and identifies a [[surjection]] from <math>S</math> to the computable numbers. There are only countably many Turing machines, showing that the computable numbers are [[subcountable]]. The set <math>S</math> of these Gödel numbers, however, is not [[computably enumerable]] (and consequently, neither are subsets of <math>S</math> 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&prime;&prime;'''. Consequently, there is no surjective [[computable function]] from the natural numbers to the set <math>S</math> of machines representing computable reals, and [[Cantor's diagonal argument]] cannot be used [[Constructivism (mathematics)|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 <math>x,</math> the [[well ordering principle]] provides that there is a minimal element in <math>S</math> which corresponds to <math>x</math>, 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 [[Injective function|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'',<math>\epsilon</math>) 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 <math>\epsilon</math> approximation of ''a'' + ''b''.

The fact that computable real numbers form a [[field (mathematics)|field]] was first proved by [[Henry Gordon Rice]] in 1954.{{sfnp|Rice|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 <math>a</math>. Then there is no Turing machine which on input ''A'' outputs "YES" if <math>a > 0</math> and "NO" if <math>a \le 0.</math> To see why, suppose the machine described by ''A'' keeps outputting 0 as <math>\epsilon</math> 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 cut]]s. 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 <math> a</math> and <math> b</math>, where <math>a \ne b</math>, and outputs whether <math>a < b</math> or <math>a > b.</math> It is sufficient to use <math>\epsilon</math>-approximations where <math> \epsilon < |b-a|/2,</math> so by taking increasingly small <math>\epsilon</math> (approaching 0), one eventually can decide whether <math>a < b</math> or <math>a > b.</math>

===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.{{sfnp|Bridges|Richman|1987|p=58}} A sequence with this property is known as a [[Specker sequence]], as the first construction is due to [[Ernst Specker]] in 1949.{{sfnp|Specker|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 number|arithmetically definable]], but not vice versa. There are many arithmetically definable, noncomputable real numbers, including:
*any number that encodes the solution of the [[halting problem]] (or any other [[undecidable problem]]) according to a chosen encoding scheme.
*[[Chaitin's constant]], <math>\Omega</math>, which is a type of real number that is [[Turing degree|Turing equivalent]] to the halting problem.
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.