Encyclopedia > Computable number

  Article Content

Computable number

A real number is called computable if its digit sequence can be produced by some algorithm. The algorithm takes a natural number n as input and produces the n-th digit of the real number's decimal expansion as output. A complex number is called computable if its real and imaginary parts are computable.

The computable numbers form an algebraically closed field, and arguably this field contains all the numbers we ever need in practice. It contains all algebraic numbers as well as many known transcendental mathematical constants. There are however many real numbers which are not computable: the set of all computable numbers is countable (because the set of algorithms is) while the set of real numbers is not (see Cantor's diagonal argument).

While the set of computable numbers is countable, it cannot be enumerated by any algorithm, program or Turing machine. Formally: it is not possible to provide a complete list x1, x2, x3, ... of all computable real numbers and a Turing machine which on input (m, n) produces the n-th digit of xm. This is proved with a slight modification of Cantor's diagonal argument.

Every computable number is definable, but not vice versa. An example of a definable, non-computable real number is Chaitin's constant, Ω.

References:

  • Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. online version (http://www.abelard.org/turpap2/tp2-ie.asp). Computable numbers (and Turing machines) were introduced in this paper.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Westhampton Beach, New York

... the village had a total population of 1,902. Geography Westhampton Beach is located at 40°48'32" North, 72°38'46" West (40.808995, -72.646009)1. According ...

 
 
 
This page was created in 36.8 ms