It is a good question. I can say that, briefly, you have to take two things for granted. 1, that the real numbers can be constructed, and 2, that the number of computable numbers is countable because the number of programs describing them is countable. Therefore there must exist uncomputable numbers (and in fact, 'almost all' real numbers are uncomputable).
I can accept the second thing, but how do you mean the first one in a way that doesn’t fall back onto the second one? What is the way to “construct” reals that isn’t a program?
I mean construction in the mathematical sense. If you believe, for example, that the rational numbers exist, then it is easy to construct the real numbers.
Very roughly, we look at the set of all sequences of rational numbers that converge in a specific way (technically, all Cauchy sequences) and call this the "set of real numbers" (technically, after taking an appropriate equivalence class, since intuitively multiple sequences can converge to the same real number). [1] has a few other constructions. This is very different from a program, which has its own definition.
So, if I understand correctly, you are saying that many (actually most) Cauchy sequences converge to uncomputable numbers. I think I understand a bit more, though I still have an issue with defining such a Cauchy sequence, because either I can describe it exactly (in which case the number it converges to can have an infinite expansion but it's computable, like pi) or I cannot define it exactly, in which case I don't know what number it converges to. I think my gap is that I don't understand how these constructions differ from programs. By program I mean a sequence of instructions, which may have an infinite number of steps because of loops, but it still has a finite description. I agree that all such programs are countable. Do you mean programs with an infinite description?
Even programs with infinite descriptions are only countably infinite, but the reals are uncountable.
This construction by Cauchy sequences looks innocent, but it's the diagonalization argument in disguise. (Start with all the rationals, make sequences out of them, make one that picks one from all, sort them into equivalence classes, and try to map them back to the rationals, notice that you will end up with more equivalence classes.)
The trick is basically that between every rational you can fit an infinite number of irrationals (using the rationals via these sequences). And exactly in this way these are "programs" -- like diagonalization itself. The fact that we can't give programs for most of them is because they are non-computable. (And it's the definition, the indirect proof is above via the cardinalities.)
Wait, the number of programs is countable? Are we saying that programs must be of finite length? (because if not a diagonal approach would prove them to be uncountable)
“Countable” as used in mathematics does not necessarily imply finite. The integers are “countably infinite”, and so is anything you can put in a 1:1 correspondence with integers.
Ah yes, of course you're right. I think it does make sense to assume the programs are finite, I don't think numbers described by an infinite program should be considered computable.
Yup! Programs are assumed to have finite length, in the sense that the program must have a finite description. Of course, it may use recursion or include a loop that runs forever, for example.
