Algebraic numbers can be very handy.
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.
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.
> 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".
> 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.)
> 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?
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)
Enumerate all well formed programs in order. For programs that halt assign the digit 0, and for the ones that don't, the digit 1. Put the digits after a decimal point and interpret in binary.
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.
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.
I assume this refers to Chaitin's constant: https://en.wikipedia.org/wiki/Chaitin%27s_constant
Previously: https://news.ycombinator.com/item?id=45424648
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.
Yup, it's common. (I'm fairly sure this or something very similar was the first way I ever saw it done.)
A number that can predict the future?