Unreal numbers(lcamtuf.substack.com)
lcamtuf.substack.com
Unreal numbers
https://lcamtuf.substack.com/p/unreal-numbers
31 comments
> 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".
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".
> 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".
I don’t think this is true at all. For example: the solution to a generic PDE that has no closed form solution at some point of import is likely transcendental, not algebraic, but definitely computable. (Think, say, Navier-Stokes being used for weather predictions in some specific place.)
I don’t think this is true at all. For example: the solution to a generic PDE that has no closed form solution at some point of import is likely transcendental, not algebraic, but definitely computable. (Think, say, Navier-Stokes being used for weather predictions in some specific place.)
True, but with such numbers you will normally not do anything else except computing an approximate value of them.
They are not comparable with numbers like 2*Pi or various irrational nth roots that can appear in a lot of relationships and formulae in symbolic computations.
That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.
What I have said is equivalent to saying that there are only a few transcendental numbers for which you need symbols.
The number of symbols that are really needed is much less than the number of symbols that happened to be used during the history. For instance a single symbol related to Pi is needed, and it would have been much better if it was a symbol for 2*Pi, not for Pi. When using decimal numbers, one may want to use the value of the decimal logarithm of "e", or of its inverse, but there exists no need whatsoever to use decimal numbers anywhere, this is just a historical accident. Etc., there are various other examples of superfluous constants, which are not needed in any practical application, unlike "2*Pi" and "ln 2", which are ubiquitous (because they appear in the derivation formulae for the trigonometric and exponential functions).
They are not comparable with numbers like 2*Pi or various irrational nth roots that can appear in a lot of relationships and formulae in symbolic computations.
That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.
What I have said is equivalent to saying that there are only a few transcendental numbers for which you need symbols.
The number of symbols that are really needed is much less than the number of symbols that happened to be used during the history. For instance a single symbol related to Pi is needed, and it would have been much better if it was a symbol for 2*Pi, not for Pi. When using decimal numbers, one may want to use the value of the decimal logarithm of "e", or of its inverse, but there exists no need whatsoever to use decimal numbers anywhere, this is just a historical accident. Etc., there are various other examples of superfluous constants, which are not needed in any practical application, unlike "2*Pi" and "ln 2", which are ubiquitous (because they appear in the derivation formulae for the trigonometric and exponential functions).
> True, but with such numbers you will normally not do anything else except computing an approximate value of them.
That's what I think people do with other numbers like "pi" at the end of the day, no? :)
> That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.
It's very much an encoding problem, I think. Though we probably, on aggregate, use "unnamed computable numbers" implicitly on the order of as much as we use "named computable numbers" the former just has way more of a "tail" of uses where the "encoding of the symbol" is, e.g., "here's the PDE you use to compute this number"!
(It gets a little weird since we're kind of not distinguishing between the approximation that can be used to construct said numbers to arbitrary precision vs the specific program instance that constructs one specific approximation, but the idea is mostly there.)
That's what I think people do with other numbers like "pi" at the end of the day, no? :)
> That is what I meant by "interesting", i.e. the necessity of using symbols of such numbers, obviously for use in symbolic computations, since in numeric computations you would never use the actual numbers, but only some approximations of them.
It's very much an encoding problem, I think. Though we probably, on aggregate, use "unnamed computable numbers" implicitly on the order of as much as we use "named computable numbers" the former just has way more of a "tail" of uses where the "encoding of the symbol" is, e.g., "here's the PDE you use to compute this number"!
(It gets a little weird since we're kind of not distinguishing between the approximation that can be used to construct said numbers to arbitrary precision vs the specific program instance that constructs one specific approximation, but the idea is mostly there.)
> 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?
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.
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.
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)
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)
Here’s a nice concrete construction. To start, fix some enumeration ϕ of Turing machines. Let’s define a sequence of rational numbers x_k as $\sum_{i=0}^k 2^{-(i+1)} * halts(ϕ(i),k)$, where $halts(M,k)$ returns 1 if the machine M halts before taking k steps when fed the empty tape, and 0 otherwise. This is perfectly computable, as we only ever need to run a finite number of machines a finite number of steps for each k.
This sequence of rationals is monotonic and is upper-bounded by 1, but does not have a computable least upper bound. If such an upper bound existed, then it would encode solutions to the halting problem for every program. However, the reals have least upper bounds of all upper bounded subsets under mild classical assumptions, so we’ve made ourselves an uncomputable real out of computable data.
Sequences of this form are called Specker sequences, and are how you cook up most uncomputable numbers. There are models of constructive logic that do not admit any Specker sequences and admit only computable reals, but that is beyond the scope of a single comment :)
This sequence of rationals is monotonic and is upper-bounded by 1, but does not have a computable least upper bound. If such an upper bound existed, then it would encode solutions to the halting problem for every program. However, the reals have least upper bounds of all upper bounded subsets under mild classical assumptions, so we’ve made ourselves an uncomputable real out of computable data.
Sequences of this form are called Specker sequences, and are how you cook up most uncomputable numbers. There are models of constructive logic that do not admit any Specker sequences and admit only computable reals, but that is beyond the scope of a single comment :)
[deleted]
I assume this refers to Chaitin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant
[deleted]
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.
Individual busy beavers BB(n) are finite natural numbers and thus quite computable. A related uncomputable number is the halting probability Omega of a universal prefix machine (whose programs form a prefix free set). By collecting enough halting programs to accumulate a probability of at least the first n bits of Omega (as a binary fraction), you will have determined all programs of length at most n that halt and thus also the busy beavers up to that size.
"A real number in which each decimal digit at position n is equal to the first digit of BB(n)."
Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.
Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.
Such an algorithm would be computing the (uncomputable) function BB : Nat -> Nat, and not the computability of a given BB(n). Every fixed natural number is computable: just print out the number.
This is a subtlety of doing computability theory in classical foundations. It’s akin to how every concrete instance P(x) of a decision problem P is decidable: just use excluded middle to figure out if P(x) is true or false, and then use the Turing machine that immediately accepts or rejects regardless of input. This is very different from writing a machine that has to decide P(x) when given x as an input!
This is a subtlety of doing computability theory in classical foundations. It’s akin to how every concrete instance P(x) of a decision problem P is decidable: just use excluded middle to figure out if P(x) is true or false, and then use the Turing machine that immediately accepts or rejects regardless of input. This is very different from writing a machine that has to decide P(x) when given x as an input!
I did just that for the first 37 BB numbers at https://oeis.org/A333479
I could write a few more given enough time, but writing later ones will take someone more omnipotent than me.
You may be confusing the true statement "for each n, BB(n) is computable" with the false statement "\n -> BB(n) is computable".
I could write a few more given enough time, but writing later ones will take someone more omnipotent than me.
You may be confusing the true statement "for each n, BB(n) is computable" with the false statement "\n -> BB(n) is computable".
I was thinking about the ability of representing different kinds of numbers. Imagine that we had a certain CPU that could process algorithms, and the final output of the algorithm is a number. The CPU has a certain number of operations (At least https://en.wikipedia.org/wiki/One-instruction_set_computer). Then, if the algorithm can be described with an integer (since the algorithm can be described with binary), then... can integers describe Real numbers?
I think this article should’ve used the Cauchy sequence method to construct the reals instead of Dedekind cuts. It would’ve built on the earlier mention of equivalence classes.
This is the first time I've seen this way to show that Q does not have a higher cardinality than N, is it a common method?
I don't remember exactly how I learned about it in high school, infinity cardinalities have rarely come up since then, but it was some other method or at least another form of presentation, i.e. symbols and prose.
I don't remember exactly how I learned about it in high school, infinity cardinalities have rarely come up since then, but it was some other method or at least another form of presentation, i.e. symbols and prose.
Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)
Indeed, it's always presented that way.¹ It's very unsatisfying because it doesn't establish a 1:1 correspondence; it depends on the idea that if set A has the same cardinality as a superset of set B, then set B's cardinality cannot exceed set A's. Add the assumption that the natural numbers have the lowest possible infinite cardinality and the proof is technically complete.
I've read about an actual bijection between naturals and rationals, but I don't remember how it was done.
¹ Possibly in the more general form of showing the bijection between ℕ and ℤ².
I've read about an actual bijection between naturals and rationals, but I don't remember how it was done.
¹ Possibly in the more general form of showing the bijection between ℕ and ℤ².
For the construction of a bijection between natural numbers and another set, when you already know that the sets have the same number of elements, it is enough to define an order relation on the other set.
There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ...
For instance, after reducing the numerator and denominator, so that you have unique rational numbers, you could define that they are ordered based on the sum of the number of digits of the numerator and of the denominator. This ensures that for each N that is the sum of digits, there are only a finite number of rational numbers. Inside this finite set, you can choose various rules, e.g. that positive numbers precede negative numbers, that a number with fewer digits in the denominator precedes another, etc. Then among the numbers with e.g. K digits in the numerator and L digits in the denominator, you could choose a lexicographic ordering, when the numerator is written before the denominator.
It does not matter which ordering rules you choose, the point is that you can always find such an order, which will arrange all rational numbers in a sequence, which describes thus a bijection with the natural numbers.
For algebraic numbers, you can establish such an order for the polynomials whose solutions they are, again finding a bijection. The easy solution is the same, to first establish an order between subsets of numbers that contain only a finite number of elements, and then define an order inside the subsets (e.g. with unique polynomials, where the coefficients do not have common factors, you can order them based on the sum of the number of digits of all coefficients).
The same technique works with any power of the set of rational numbers, or of the set of algebraic numbers.
For computable numbers, which are determined by programs written with an alphabet having a finite number of characters, you can define an order for the programs, e.g. first based on the length of the program, and then, among the finite number of programs having the same length, with lexicographic order.
With real numbers such methods do not work, because any attempt to arrange the real numbers into a sequence of subsets results in subsets that do not have a finite number of elements, like above, but which have an infinite number of elements.
There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ...
For instance, after reducing the numerator and denominator, so that you have unique rational numbers, you could define that they are ordered based on the sum of the number of digits of the numerator and of the denominator. This ensures that for each N that is the sum of digits, there are only a finite number of rational numbers. Inside this finite set, you can choose various rules, e.g. that positive numbers precede negative numbers, that a number with fewer digits in the denominator precedes another, etc. Then among the numbers with e.g. K digits in the numerator and L digits in the denominator, you could choose a lexicographic ordering, when the numerator is written before the denominator.
It does not matter which ordering rules you choose, the point is that you can always find such an order, which will arrange all rational numbers in a sequence, which describes thus a bijection with the natural numbers.
For algebraic numbers, you can establish such an order for the polynomials whose solutions they are, again finding a bijection. The easy solution is the same, to first establish an order between subsets of numbers that contain only a finite number of elements, and then define an order inside the subsets (e.g. with unique polynomials, where the coefficients do not have common factors, you can order them based on the sum of the number of digits of all coefficients).
The same technique works with any power of the set of rational numbers, or of the set of algebraic numbers.
For computable numbers, which are determined by programs written with an alphabet having a finite number of characters, you can define an order for the programs, e.g. first based on the length of the program, and then, among the finite number of programs having the same length, with lexicographic order.
With real numbers such methods do not work, because any attempt to arrange the real numbers into a sequence of subsets results in subsets that do not have a finite number of elements, like above, but which have an infinite number of elements.
This doesn't really help you if you want to calculate the index associated with a rational number.
The cantor pairing function is a bijection though between (N, N) -> N so it does establish a bijection in cardinality between positive rationals and N.
The approach you mentioned would be if you used a non-bijective function to map from (N, N) to N like 2^a 3^b which can show that the cardinality of positive rationals is a subset of the cardinality of the naturals, and then you get your version of the proof.
Edit: Wait unless the objection was that actually the bijection from (N, N) -> N is not sufficient since e.g. (1,1) and (2,2) all map to the same rational. You could probably skip duplicates when enumerating, but if you insist on a explicit constructive version I have no idea how you'd find the inversion formula for that.
The approach you mentioned would be if you used a non-bijective function to map from (N, N) to N like 2^a 3^b which can show that the cardinality of positive rationals is a subset of the cardinality of the naturals, and then you get your version of the proof.
Edit: Wait unless the objection was that actually the bijection from (N, N) -> N is not sufficient since e.g. (1,1) and (2,2) all map to the same rational. You could probably skip duplicates when enumerating, but if you insist on a explicit constructive version I have no idea how you'd find the inversion formula for that.
For bijection, the path through the rationals can just jump over and skip any numbers that have already been visited by the path.
Ever since I learned about them I found the Surreals a far more natural construction than the more classical one shown here. They don't just stop the logical induction at arbitrary points.
A number that can predict the future?
I was making myself toy, tapered kaleidoscopes using one piece cardboard plans. One needed to ensure that the dihedral angles between the mirrors be precise.
This is not easy to do with the usual middle-school geometry-box rulers and protractors. Graduations not fine enough, precise enough, extending long straight lines using a small ruler not straight enough ...
However the dimensions being all algebraic numbers one could use entirely straight edge and compass constructions. Had much better luck this way, with a pointy enough pencil.
A proper drafting board and a T-square or a drafter would have made things easier for parallel and perpendicular translations. But one can do those with compass too.