Computable Number - Properties

Properties

While the set of real numbers is uncountable, the set of computable numbers is only countable and thus almost all real numbers are not computable. The computable numbers can be counted by assigning a Gödel number to each Turing machine definition. This gives a function from the naturals to the computable reals. Although the computable numbers are an ordered field, the set of Gödel numbers corresponding to computable numbers is not itself computably enumerable, because it is not possible to effectively 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′′. Thus Cantor's diagonal argument cannot be used to produce uncountably many computable reals; at best, the reals formed from this method will be uncomputable.

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,) 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 approximation of a+b.

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 (Bridges and Richman, 1987:58). A sequence with this property is known as a Specker sequence, as the first construction is due to E. 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.

The order relation on the computable numbers is not computable. There is no Turing machine which on input A (the description of a Turing machine approximating the number ) outputs "YES" if and "NO" if . The reason: suppose the machine described by A keeps outputting 0 as 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 an input two Turing machines A and B approximating numbers a and b, where a≠b, and outputs whether a<b or a>b. It is sufficient to use ε-approximations where ε<|b-a|/2; so by taking increasingly small ε (with a limit to 0), one eventually can decide whether a<b or a>b.

Every computable number is definable, but not vice versa. There are many definable, noncomputable real numbers, including:

• The binary representation of the Halting problem (or any other uncomputable set of natural numbers).
• Chaitin's constant, which is a type of real number that is Turing equivalent to the Halting problem.

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.

Every computable number is arithmetical.

The set of computable real numbers (as well as every countable, densely ordered subset of reals without ends) is order-isomorphic to the set of rational numbers.