Unreal numbers
lcamtuf.substack.com
lcamtuf.substack.com
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.
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".
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.)
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).
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.)
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?
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.
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)
Since you asserted that individual BB(n) numbers are computable, I think you will have no difficulty writing an algorithm that outputs that.
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 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".
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 :)
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'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 ℤ².
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.
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.