What are computable numbers?

Alan Turing, answered from the texts and cited to the page.

Alan Turing answers

A number is computable if its decimal can be written down by a machine.1 More precisely, the computable numbers are the real numbers whose decimal expressions are calculable by finite means — and the justification for that phrase, "finite means," lies in the fact that human memory is necessarily limited.23 The machine I have in mind is defined as follows.

It is capable of only a finite number of internal states, which I call m-configurations. It operates on a tape divided into squares, each bearing a symbol; at any moment, exactly one square is scanned, and the machine's behaviour at that moment is entirely determined by its current m-configuration together with the scanned symbol.4 It can write a new symbol on the scanned square, erase the scanned symbol, or shift one square to the left or right — and it may also change its m-configuration.

Some symbols written down form the decimal of the number being computed; others serve merely as rough notes to assist the memory, and these alone are liable to erasure.5 A sequence is computable if it can be computed by what I call a circle-free machine — that is, a machine that never ceases to print symbols of the first kind, the significant ones.6

A machine that eventually stops printing such symbols, whether because it reaches a configuration with no possible move or because it loops without further output, is called circular, and the sequence it produces is not computable.7 The class of computable numbers is remarkably large. It includes the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers π and e, and much else besides.8

Yet for all its breadth, the class is enumerable — and this is what makes the negative result possible. By a diagonal argument closely related to Gödel's, one can show that not all definable numbers are computable, and from this it follows that the Entscheidungsproblem, Hilbert's question of whether there exists a mechanical decision procedure for first-order logic, has no solution.9

Church arrived at equivalent conclusions by a different route, defining "effective calculability" through the lambda calculus; the two notions turn out to coincide, as I demonstrate in an appendix to the 1936 paper.10

Sources

  1. According to my definition, a number is computable if its decimal can be written down by a machine.
    On Computable Numbers, pp. 1–2
  2. The 'computable' numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
    On Computable Numbers, pp. 1–2
  3. the justification lies in the fact that the human memory is necessarily limited.
    On Computable Numbers, pp. 2–3
  4. The possible behaviour of the machine at any moment is determined by the m-configuration q,, and the scanned symbol ©(r). This pair q,,, S(r) will be called the 'configuration': thus the configuration determines the possible behaviour of the machine.
    On Computable Numbers, pp. 2–3
  5. Some of the symbols written down will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to 'assist the memory'. It will only be these rough notes which will be liable to erasure.
    On Computable Numbers, pp. 2–3
  6. A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.
    On Computable Numbers, pp. 4–5
  7. A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind.
    On Computable Numbers, pp. 4–5
  8. They include, for instance, the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers π, e, etc.
    On Computable Numbers, pp. 1–2
  9. Although the class of computable numbers is so great, and in many ways similar to the class of real numbers, it is nevertheless enumerable... In particular, it is shown (11) that the Hilbertian Entscheidungsproblem can have no solution.
    On Computable Numbers, pp. 1–2
  10. Church also reaches similar conclusions about the Entscheidungsproblem. The proof of equivalence between 'computability' and 'effective calculability' is outlined in an appendix to the present paper.
    On Computable Numbers, pp. 1–2