Editing Computable number (section)

===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>