Computable Number - Digit Strings and The Cantor and Baire Spaces

Digit Strings and The Cantor and Baire Spaces

Turing's original paper defined computable numbers as follows:

A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer as input and produces the -th digit of the real number's decimal expansion as output.

(Note that the decimal expansion of a only refers to the digits following the decimal point.)

Turing was aware that this definition is equivalent to the -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 sense: if, then the first n digits of the decimal expansion for a provide an approximation of a. For the converse, we pick an computable real number a and generate increasingly precisce approximations until the nth 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 (total 0,1 valued functions) instead of reals numbers in . The members of can be identified with binary decimal expansions but since the decimal expansions and denote the same real number the interval can only be bijectively (and homeomorphically under the subset topology) identified with the subset of 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 approximation sense. Hirst has shown there is no algorithm which takes as input the description of a Turing machine which produces 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 (see 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 that the contemporary definition of computable numbers uses approximations rather than decimal expansions.

However, from a computational or measure theoretic perspective the two structures and are essentially identical. and computability theorists often refer to members of as reals. While is totally disconnected for questions about classes or randomness it's much less messy to work in .

Elements of are sometimes called reals as well and though containing a homeomorphic image of in addition to being totally disconnected isn't even locally compact. This leads to genuine differences in the computational properties. For instance the satisfying with quatifier free must be computable while the unique satisfying a universal formula can be arbitrarily high in the hyperarithmetic hierarchy.