Computable number

related topics
{math, number, function}
{school, student, university}

In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. Equivalent definitions can be given using μ-recursive functions, Turing machines or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes.

Contents

Informal definition using a Turing machine as example

In the following, Marvin Minsky defines the numbers to be computed in a manner similar to those defined by Alan Turing in 1936, i.e. as "sequences of digits interpreted as decimal fractions" between 0 and 1:

The key notions in the definition are (1) that some n is specified at the start, (2) for any n the computation only takes a finite number of steps, after which the machine produces the desired output and terminates.

An alternate form of (2) – the machine successively prints all n of the digits on its tape, halting after printing the nth – emphasizes Minsky's observation: (3) That by use of a Turing machine, a finite definition – in the form of the machine's TABLE – is being used to define what is a potentially-infinite string of decimal digits.

This is however not the modern definition which only requires the result be accurate to within any given accuracy. The informal definition above is subject to a rounding problem called the table-maker's dilemma whereas the modern definition is not.

Formal definition

A real number a is said to be computable if it can be approximated by some computable function in the following manner: given any integer n \ge 1, the function produces an integer k such that:

There are two similar definitions that are equivalent:

  • There exists a computable function which, given any positive rational error bound \varepsilon, produces a rational number r such that |r - a| \leq \varepsilon.
  • There is a computable sequence of rational numbers qi converging to r such that |q_i - q_{i+1}| < 2^{-i}\, for each i.

Full article ▸

related documents
Multivariate normal distribution
Hyperreal number
Dynamic programming
Fundamental group
Prime number theorem
Convolution
Continuous function
Group action
Primitive recursive function
Euler's formula
Abelian group
Dual space
Fundamental theorem of algebra
Basis (linear algebra)
Bessel function
Factorial
BCH code
Ackermann function
Frame problem
Probability theory
Halting problem
Fermat number
Lp space
Monte Carlo method
Proofs of Fermat's little theorem
Compass and straightedge constructions
Subset sum problem
Simplex
Central limit theorem
REXX