Most real numbers are impossible to compute, even with an infinite amount of time.
In short: In mathematics, computable numbers are real numbers that can be approximated to any desired precision by a finite algorithm. While they include familiar constants, they represent only a tiny, countable fraction of the real number line. Almost all real numbers remain forever beyond the reach of any possible calculation.
The concept of a computable real number, introduced by Émile Borel in 1912, relies on the idea that a number can be defined by a finite, terminating algorithm. Whether using Turing machines, lambda calculus, or recursive functions, the core requirement is that a machine can produce the number's digits or approximate its value to any specified degree of accuracy. Marvin Minsky later framed this as using a finite state table to define a potentially infinite string of decimal digits.
Modern definitions focus on approximation. A real number is computable if a function can provide a rational value within a specific error bound for any given integer. This framework extends to complex numbers, where both real and imaginary components must be computable. These numbers form a real closed field, meaning basic arithmetic operations like addition, subtraction, multiplication, and division remain within the set of computable numbers.
Despite their utility, computable numbers are rare. Because there are only countably many Turing machines, there are only countably many computable numbers. In contrast, the set of all real numbers is uncountable. This implies that almost all real numbers are non-computable. Furthermore, while the computable numbers are ordered, identifying them is difficult; there is no algorithm to determine which Turing machine definitions correspond to computable reals, as the decision problem sits at Turing degree 0''.
The distinction is profound: even though we can define computable numbers through methods like computable Dedekind cuts—such as the program defining the cube root of 3—we cannot constructively list all computable numbers. Henry Gordon Rice proved in 1954 that they form a field, yet they do not constitute a computable field because they lack effective equality. Ultimately, the computable numbers represent a structured, finite island in an uncountable sea of mathematical values that defy algorithmic capture.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Computable number
To cite this card, link to https://intellectplus.co.uk/app/science-computable-number.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Basics · More in Science · Latest · A–Z · All topics