Editing Computable number (section)

==Digit strings and the Cantor and Baire spaces==

Turing's original paper defined computable numbers as follows:

{{quote|text=A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer <math>n \ge 1</math> as input and produces the <math>n</math>-th digit of the real number's decimal expansion as output.}}

(The decimal expansion of ''a'' only refers to the digits following the decimal point.)

Turing was aware that this definition is equivalent to the <math>\epsilon</math>-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 <math>\epsilon</math> sense: if <math>n > \log_{10} (1/\epsilon)</math>, then the first ''n'' digits of the decimal expansion for ''a'' provide an <math>\epsilon</math> approximation of ''a''. For the converse, we pick an <math>\epsilon</math> 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 <math>2^{\omega}</math> (total 0,1 valued functions) instead of reals numbers in <math>[0,1]</math>. The members of <math>2^{\omega}</math> can be identified with binary decimal expansions, but since the decimal expansions <math>.d_1d_2\ldots d_n0111\ldots</math> and <math>.d_1d_2\ldots d_n10</math> denote the same real number, the interval <math>[0,1]</math> can only be bijectively (and homeomorphically under the subset topology) identified with the subset of <math>2^{\omega}</math> not ending in all 1's.

Note that this property of decimal expansions means that it is impossible to effectively identify the computable real numbers defined in terms of a decimal expansion and those defined in the <math>\epsilon</math> approximation sense. Hirst has shown that there is no algorithm which takes as input the description of a Turing machine which produces <math>\epsilon</math> 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.{{sfnp|Hirst|2007}} 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 why the contemporary definition of computable numbers uses <math>\epsilon</math> approximations rather than decimal expansions.

However, from a [[computability theory|computability theoretic]] or [[measure theory|measure theoretic]] perspective, the two structures <math>2^{\omega}</math> and <math>[0,1]</math> are essentially identical. Thus, computability theorists often refer to members of <math>2^{\omega}</math> as reals. While <math>2^{\omega}</math> is [[totally disconnected]], for questions about <math>\Pi^0_1</math> classes or randomness it is easier to work in <math>2^{\omega}</math>.

Elements of <math>\omega^{\omega}</math> are sometimes called reals as well and though containing a [[homeomorphic]] image of <math>\mathbb{R}</math>, <math>\omega^{\omega}</math> isn't even [[locally compact]] (in addition to being totally disconnected). This leads to genuine differences in the computational properties. For instance the <math>x \in \mathbb{R}</math> satisfying <math>\forall(n \in \omega)\phi(x,n)</math>, with <math>\phi(x,n)</math> quantifier free, must be computable while the unique <math>x \in \omega^{\omega}</math> satisfying a universal formula may have an arbitrarily high position in the [[hyperarithmetic hierarchy]].