Hacker News Reader

Comment by ziofill | Hacker News Reader

I find it hard to wrap my head around non computable numbers. How can I even “point to one” of them if I can’t express/describe it? And if I cannot communicate which number I’m referring to, does it really exist? In what way do they exist?

View on HN

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.

[1] https://en.wikipedia.org/wiki/Construction_of_the_real_numbe...

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

[but it's dangerously late here, so double check my ramblings ... https://math.stackexchange.com/a/1488502 ]

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.

But as I said, if programs are of infinite length, then a diagonalization argument proves the computable numbers not to be countable I think.

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.

> In what way do they exist?

In a way that makes the real number line continuous. Those numbers have to be there if we want the set to have properties useful for practical applications like algebra.

As far as I understand, if you look at a number between 0 and 1 with a truly random infinite decimal expansion:

    0.22134967842153005356...

then there is absolutely no pattern in the digits, so a program that wants to compute it can do no better than storing all the digits. But then the program would have infinite size.

Not all non computable numbers are undescribable. Chaitin's constant[1] is non-computable but can be described.

[1] https://en.m.wikipedia.org/wiki/Chaitin%27s_constant

I can write a program that will visit every number between 0 and 1, but it will take infinitely long to run and use infinite memory.

But such a program can't visit every real number in the interval, because there are uncountably many, but the program will only run for countably infinitely many steps.

You're right, I actually hadn't grasped this, I realised later on but it was too late to edit my comment. And to be honest I still don't completely get it.

Since you can count the cycles your computer takes, then at any point in time it's outputting a countable digit on a list of numbers that is also countable. Accelerating it to infinity lets you finish both of those tasks, but it doesn't break you into another realm.

If you get a nondeterministic computer, where every digit it splits into 10 identical computers that each picked one of the 10 options, then when you run that for countably infinite cycles you'll find that you have uncountably infinite computers and you have finally calculated every real number.

The cardinality of the real numbers is 2 to the power of the countable numbers.

You can't point to one of them, but you can point to infinite sets of them.

Reply on news.ycombinator.com