In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, computable numbers are the
real numbers
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
that can be computed to within any desired precision by a finite, terminating
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
. They are also known as the recursive numbers, effective numbers or the computable reals or recursive reals.
Equivalent definitions can be given using
μ-recursive function
In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as i ...
s,
Turing machines
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, or
λ-calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...
as the formal representation of algorithms. The computable numbers form a
real closed field
In mathematics, a real closed field is a field ''F'' that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
Def ...
and can be used in the place of real numbers for many, but not all, mathematical purposes.
Informal definition using a Turing machine as example
In the following,
Marvin Minsky
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, an ...
defines the numbers to be computed in a manner similar to those defined by
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
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 ''n''th – emphasizes Minsky's observation: (3) That by use of a Turing machine, a ''finite'' definition – in the form of the machine's state 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
Rounding means replacing a number with an approximation, approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with .
Rounding is oft ...
whereas the modern definition is not.
Formal definition
A
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
''a'' is computable if it can be approximated by some
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
in the following manner: given any positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
''n'', the function produces an integer ''f''(''n'') such that:
:
There are two similar definitions that are equivalent:
*There exists a computable function which, given any positive rational
error bound
The approximation error in a data value is the discrepancy between an exact value and some '' approximation'' to it. This error can be expressed as an absolute error (the numerical amount of the discrepancy) or as a relative error (the absolute e ...
, produces a
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
''r'' such that
*There is a computable sequence of rational numbers
converging to
such that
for each ''i''.
There is another equivalent definition of computable numbers via computable
Dedekind cut
In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind but previously considered by Joseph Bertrand, are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of the rat ...
s. A computable Dedekind cut is a computable function
which when provided with a rational number
as input returns
or
, satisfying the following conditions:
:
:
: