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