Computable number

As a computable number is a real number is called, if there is a computation rule that can generate each of its digits. In particular, there are non- predictable numbers.


A real number, is calculated when the function that each integer i- th digit of the binary representation of maps, can be calculated.

Here, a calculation model, it is assumed, for example, a Turing Machine.


All natural, rational and algebraic numbers are computable, but also many transcendental numbers such as π the loop number or the Euler number e The holding number is defined as the binary number between 0 and 1, indicates the i- th digit after the decimal point if the i-th Turing machine for the input i terminated ( 1) or not (0). The holding number can not be calculated, because the halting problem is undecidable.

Are the phases of a Turing machine set up so that they each spend the next decimal place, so does this correspond to an elemental interpolation. The respective ( irrational ) computable number is the same meaning in the limit of their Cauchy sequence, so you can define the computable numbers by the corresponding computable Cauchy sequences.

Since each program a Turing machine is finite and consists only of a finite number of characters, there are only countably many such programs and thus also only countably many computable numbers. Since, as one can easily considered the sum and the product of two computable numbers is again calculated, and also the inverse of any computable number is calculated again, form the computable numbers a part of the real numbers.