Computable number

In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm. They can be defined equivalently using the axioms of recursive functions, Turing machines or lambda-calculus. In contrast, the reals require the more powerful axioms of Zermelo-Fraenkel set theory. The computable numbers form a real closed field and can be used in the place of real numbers for many, but by no means all, mathematical purposes.

Related Topics:
Mathematics - Theoretical computer science - Mathematical logic - Real numbers - Algorithm - Recursive functions - Turing machines - Lambda-calculus - Zermelo-Fraenkel set theory - Real closed field

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The computable numbers are countable and the uncountability of the reals implies that most real numbers are not computable. The computable numbers can be counted by assigning a Gödel number to each Turing machine / lambda expression / recursive function definition. Then we have mapping from the naturals to the computable reals. Note however that while computable numbers are an ordered field it is not possible to computably order them, as this would require us to decide which natural numbers correspond to halting Turing machines, which is an uncomputable problem. Because of this fact, the Cantor diagonalization argument does not work for the set of countable, computable reals: the diagonal element corresponds to a non-computable number. (Interestingly, we can define this diagonal number in a finite amount of English, such as this paragraph - though it is uncomputable! This is perhaps due to the assumption that we can 'imagine ordering the computable numbers' for the Cantor proof, while this is not algorithmically possible in practice.)

Related Topics:
Gödel number - Cantor diagonalization

~ ~ ~ ~ ~ ~ ~ ~ ~ ~