Computable number

In mathematics, computer science, and computability theory, a computable number is a real number for which there exists an algorithm that, given any required degree of precision, produces a rational approximation of the number within that precision in finite time. Equivalently, the number’s decimal (or binary) expansion can be generated digit-by-digit by a terminating computation procedure. Computable numbers form a countable subfield of the real numbers and include all algebraic numbers, as well as many transcendental numbers such as π and e. The concept was introduced in 1936 by Alan Turing to formalize the notion of “effectively calculable” real numbers and to prove the existence of uncomputable numbers.

Formal definitions

There are several equivalent characterizations of computable numbers, all rooted in the theory of computable functions.

Turing-machine definition

A real number \( r \) is computable if there exists a Turing machine that, on input \( n \) (a positive integer), halts and outputs a rational number \( q_n \) such that \( |r - q_n| < 1/n \). The function \( n \mapsto q_n \) must be a total computable function. Alternatively, one can require the machine to produce the \(n\)-th digit of the number’s decimal expansion, though care must be taken with repeating 9s: one often demands a machine that never outputs a terminating infinite sequence of 9s unless the number itself is a terminating decimal.

Recursive-function definition

Using the Church–Turing thesis, a real number is computable if and only if there exist computable functions \( a, b \colon \mathbb{N} \to \mathbb{N} \) such that the sequence of rational approximations \( \frac{ a(k) - b(k) }{ b(k)+1 } \) converges to the number with an effectively known rate of convergence, e.g., \( \left| r - \frac{a(k)}{b(k)+1} \right| < 2^{-k} \). More generally, a real number is computable if its left Dedekind cut is a computable set of rationals.

Equivalent formulations

A real number is computable precisely when its binary expansion is computable (allowing for the non-uniqueness of expansions). It is also equivalent to the existence of a program that enumerates all rational numbers less than the number (making the number lower‑semi‑computable) and all rational numbers greater than it (upper‑semi‑computable). A number with only one of these properties is called semi‑computable.

History

The systematic study of computable numbers began with Alan Turing’s 1936 paper “On Computable Numbers, with an Application to the Entscheidungsproblem.” Turing defined a real number to be computable if its decimal expansion could be written down by a Turing machine. At the same time, Alonzo Church developed a parallel definition using λ‑definability, and Emil Post and Stephen Kleene contributed equivalent formulations via recursive functions. Turing’s central application was to show that the set of computable numbers is countable and that there exist definable but uncomputable real numbers, such as those encoding the halting problem. This laid the groundwork for the modern understanding of incomputability.

Earlier anticipations of computable real analysis can be found in the work of Borel, Brouwer, and others on constructive mathematics, but the precise formalization of computability for real numbers was a landmark of 1930s logic.

Examples

• Rational numbers: Every rational number is computable, because its finite or ultimately periodic decimal expansion can be generated by a simple program.
• Algebraic numbers: All algebraic numbers (roots of non‑zero polynomials with integer coefficients) are computable. For instance, \( \sqrt{2} \) is computable by the digit-by-digit algorithm for square roots.
• Familiar transcendental numbers: π, e, and the Euler–Mascheroni constant γ (if it is a normal computable number) are computable. Algorithms (e.g., Machin‑like formulas, spigot algorithms) exist to calculate their digits to arbitrary precision.
• Computable limits: Any real number defined as the limit of a computable sequence that converges with a computable modulus of convergence is computable. This covers series like \( \sum_{n=1}^\infty 1/n^2 \) and many constants of analysis.
• Non‑computable examples: Chaitin’s constant Ω (the halting probability of a universal prefix‑free Turing machine) is a well‑known non‑computable number. A Turing machine cannot compute its binary digits. The set of computable numbers is countable, so “almost all” real numbers are non‑computable in the sense of Lebesgue measure. Specifically definable non‑computable numbers include Specker sequences, which are bounded, strictly increasing computable sequences of rational numbers whose limit is not a computable real number.

Properties

Algebra and order

The computable numbers form a real closed field: they are closed under addition, subtraction, multiplication, division (by a non‑zero computable number), and the extraction of roots of polynomials with computable coefficients. They are also closed under computably convergent sequences (with a computable modulus of convergence). However, the order relation is not computable: there is no general algorithm that, given two computable numbers, decides whether they are equal or which is larger. Equality of computable numbers is a co‑recursively enumerable but not decidable relation. Comparisons become decidable when the numbers are known to be apart (i.e., their difference is bounded away from zero by a known rational).

Cardinality and measure

The set of computable numbers is countable, because each computable number is generated by a finite program (Turing machine) and there are only countably many such programs. Since the real line is uncountable, almost every real number is uncomputable. Nonetheless, one cannot explicitly exhibit a single uncomputable number without additional assumptions (e.g., the halting problem). In terms of Lebesgue measure, the set of computable numbers has measure zero; moreover, no algorithm can list an infinite sequence of pairwise distinct computable numbers that includes a positive-measure set of reals.

Complexity

Computable numbers can be classified by the time or space complexity of their generating algorithms. A number is polynomial‑time computable if its first \( n \) bits can be computed in time polynomial in \( n \). Many common constants lie in the class of polynomial‑time computable real numbers, though some, such as those defined via rapidly growing functions, may require exponential time.

Subclasses and generalizations

• Computable reals vs. left‑/right‑computable: A left‑computable (or lower‑semi‑computable) real number is the supremum of a computable sequence of rational numbers. Chaitin’s Ω is left‑computable but not computable. Right‑computable numbers are defined analogously via infimums.
• Polynomial‑time computable reals: As noted, these are computable reals with efficient digit‑generation algorithms.
• Arithmetical and hyperarithmetical reals: Basing computation on oracles extends the notion to higher levels of the arithmetical hierarchy, giving rise to \( \Delta^0_2 \)-computable, \( \Delta^1_1 \)-computable, etc., numbers.
• Computable elements of metric spaces: The concept generalizes to elements of any separable metric space equipped with a computable structure; computable real numbers are the computable points of \( \mathbb{R} \) with the standard Euclidean metric.

Relevance and applications

Computable numbers form the theoretical foundation of computable analysis, which studies analysis with algorithms that manipulate real numbers exactly via approximations. In practice, symbolic computation and arbitrary‑precision arithmetic libraries (e.g., MPFR) implement computable reals by representing numbers as functions that produce rational bounds on demand. The theory also clarifies which mathematical constants can be “named” by finite data and which properties of real numbers can be algorithmically verified. In algorithmic randomness, computable numbers serve as a baseline: a real is called random (in the sense of Martin‑Löf) if it avoids all effectively null sets; such random reals are always non‑computable. The undecidability of equality and order among computable numbers reinforces the constructive view that equality of real numbers is a non‑trivial notion requiring explicit proofs.