[HN Gopher] Unreal Numbers
___________________________________________________________________
Unreal Numbers
Author : surprisetalk
Score : 41 points
Date : 2026-02-17 12:40 UTC (5 days ago)
(HTM) web link (lcamtuf.substack.com)
(TXT) w3m dump (lcamtuf.substack.com)
| emmelaich wrote:
| Previously: https://news.ycombinator.com/item?id=45424648
| koolala wrote:
| A number that can predict the future?
| Reubend wrote:
| > But what would be an example of an uncomputable number? That's
| a good question. Most obviously, we could be talking about
| numbers that encode the solution to the halting problem. It would
| lead to a paradox to have a computer program that allows us to
| decide, in the general case, whether a given computer program
| halts. So, if a procedure to approximate a particular real
| requires solving the halting problem, we can't have that.
|
| This doesn't make sense to me. Given that there's no generic way
| to compute halting, how would we make the leap to saying that
| there's a specific number which represents the solution to that
| problem?
| throwaway27448 wrote:
| I assume this refers to Chaitin's constant:
| https://en.wikipedia.org/wiki/Chaitin%27s_constant
| yorwba wrote:
| Any given computation either halts or it doesn't. You can
| encode that information in a single bit, as a specific number.
| Since there is a countably infinite number of possible
| computations, you'd need a countably infinite number of bits.
|
| So you can never find enough storage to hold the full solution
| of the halting problem in the real world. But you can find
| enough storage in a real number. Because real numbers can have
| a countably infinite number of digits after the decimal point.
| So you can stuff your countably infinite number of bits
| representing the solution of the halting problem in there.
|
| Which specific real number you get depends on the details of
| the encoding, but it's definitely _some_ real number. And it
| cannot be computed, because if it could, you could read the
| solution to the halting problem off its digits, but the halting
| problem is known to be uncomputable.
| moritzwarhier wrote:
| I'm not a mathematician, but constructivists aim to define
| mathematics without uncomputable numbers, see
|
| https://en.wikipedia.org/wiki/Computable_analysis
|
| and
|
| https://en.wikipedia.org/wiki/Computable_number#Use_in_place...
|
| As far as I can understand, the set of all computable numbers
| (including all algebraic numbers and many transcendental
| numbers, such as Pi), even has the same cardinality as the
| rationals, and thus the natural numbers.
|
| The reason we consider uncomputable numbers "numbers" include
| some definitions about infinite series and analysis that would
| need to have stricter requirements for convergence when looking
| only at the computable numbers, not the real numbers.
|
| And defining a concrete bijection between the natural numbers
| and the computable numbers would also solve the halting problem
| and is impossible, we only know that such a bijection exists:
| defining it would mean to have an algorithm that can prove for
| a specific Turing machine that it is the minimal one computing
| it's output, among a given set of universal Turing machines /
| UTM encoding.
|
| (please take this with a grain of salt as I'm stepping outside
| the bounds of my knowledge here)
| adrian_b wrote:
| > Of course, we don't teach about computable numbers in school.
| Instead, the most common "upgrade" from Q are reals:
|
| While "computable" numbers are a recent concept, already for a
| few centuries, since the early 18th century, mathematics has
| taught about another set of numbers intermediate between rational
| numbers and "real" numbers: the algebraic numbers, which are a
| subset of the computable numbers.
|
| Like the "real" numbers, the "complex" numbers have also been
| partitioned since that time into "complex" integer numbers,
| "complex" rational numbers, "complex" algebraic numbers,
| "complex" transcendental numbers.
|
| Everything that is now discussed in terms of "computable" and
| "non-computable" numbers, was previously discussed in terms of
| algebraic numbers and transcendental numbers.
|
| While "computable" numbers is a more general concept that more
| precisely defines the limit between what is countable and what is
| not, the practical importance of this concept is reduced, because
| few of the computable numbers that are not algebraic are
| interesting, the main exceptions being the numbers that are
| algebraic expressions containing "2*Pi" and/or "ln 2".
___________________________________________________________________
(page generated 2026-02-22 16:00 UTC)