Unreal numbers

Previously: https://news.ycombinator.com/item?id=45424648

> 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?

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.

> Of course, we don’t teach about computable numbers in school. Instead, the most common “upgrade” from ℚ 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".

Busy beavers are a classic example. They're mostly-hypothetical numbers that tell you "if any Turing machine of size s runs for longer than this, it doesn't halt." There's a link to that in the sentence you quoted.