The online lecture I am watching stated a proof idea:

The set of all possible programs is countably infinite, yet the set of irrational numbers is uncountably infinite.

I don't think this is sufficient, it assumes one program can only return one irrational number. How to show that I can not write one program that returns all irrational numbers?

  • 3
    $\begingroup$ We are interested in programs which accept an input $n$ and output a digit. Together, these digits form the decimal expansion of some number. $\endgroup$ Dec 29 '18 at 12:24
  • $\begingroup$ There are infinitely many irrational numbers. Just how are you going to return all of them with a single program? $\endgroup$
    – dkaeae
    Dec 29 '18 at 12:29
  • $\begingroup$ @dkaeae obviously if I want to output an irrational number, it will just be to a certain accuracy p which may be input to the program. otherwise, no program can output any irrational number $\endgroup$
    – PascalIv
    Dec 29 '18 at 14:50
  • $\begingroup$ @YuvalFilmus I don't understand your comment. What input n? output only one digit? Why can I not output more digits? $\endgroup$
    – PascalIv
    Dec 29 '18 at 14:51
  • $\begingroup$ @Pascallv I am not talking about the infiniteness of the numbers themselves or their representations. What I am referring to is that there are infinitely many of them―even uncountably many. $\endgroup$
    – dkaeae
    Dec 29 '18 at 14:57

You can't even write a program that outputs one single irrational number. What you can do, is write a program which will output for example every decimal digit of some irrational number, one after the other, assuming unlimited resources and unlimited time, and which will output every single digit eventually (but will never output all digits). We count that as "outputting a number".

If you tried to write a program that first outputs all digits of π, followed by all digits of e, that wouldn't work because it never will finish outputting the digits of π. What you could do is output the first decimal of π, followed by the first decimal of e, followed by the second digits of π and e, and so on. So a program can output two (or three or four or a billion) irrational numbers, if we change the definition a bit.

You could write a program that outputs a countable infinite number of irrational numbers. Start with the first digit of the first number. Then the second digit of the first, followed by the first digit of the second number. Then the 3rd digit of the first, 2nd digit of the second, and 1st digit of the third number, and so on forever. So this program would eventually output each digit of a countable infinite number of irrational numbers.

You can't extend this to an uncountable numbers. Being uncountable, it is impossible for example to output just the first digits of all these numbers.

So the best you can do, with a modified definition of what "outputting an irrational number" means, is that you can have a countable number of programs, which each calculate a countable number of irrational numbers, but countable times countable is still countable, so you cannot output all irrational numbers.


You cannot return all irrational numbers simply because you cannot put/store them all within your program that has countable amount of registers/memory.

Even if you could somehow store the irrational numbers as a concept within your program and return that concept, you could not use it to access/search a specific irrational number because we cannot order/list elements of sets that are uncountable (see Cantor’s diagonal argument), so it wouldn’t be of much use unless you invent some new operation on these “concept outputs”, but this is already too far fetched.

Another point is that we live (as it seems) in at best countable universe so everything that is equal or greater in cardinalty cannot be truly seen/experienced within it, at specific point or finite period of time.

We use approximations, but $3.1415$ is not $\pi$, $3.14159$ is not $\pi$,... If your program returns $3.1415926$, how do you know it is supposed to represent $\pi$ and not $3.14159264$?

You can write a program that, one by one, outputs digits of $\pi$ and call this program a representation of $\pi$. It will never give you $\pi$ truly but it can infinitely run giving you something closer and closer to $\pi$.
For all irrationals, you would need uncountably many such (different) programs or one program with uncountably many instructions, both of which by definition cannot exist.

Well, there are some theories that you could throw a program into a black hole where it would run for infinite amount of time while you would experience this time as $0$, giving you the result of infinite computation instantly. That would also be problematic for the task we are discussing because it would need to create the entire inifinite universe to store the irrational number.

  • $\begingroup$ What is your reason for stating that we live in a countable universe? What does that even mean? $\endgroup$ Dec 30 '18 at 21:02
  • $\begingroup$ @AndrejBauer It is just an illustration of how anything infinite cannot be produced fully with a Turing machine or some equivalent model for writing programs that the OP speaks of, even if the universe is infinite. I meant that the time and/or space are (as far as we know, having in mind the Planck constant) finite or countably infinite, because we can injectively assign a natural number to each smallest portion of time and space. $\endgroup$ Dec 30 '18 at 21:59
  • $\begingroup$ That's a misintepretation of Planck's constant. It doesn't say at all that there are "smallest" portions of time and space. Planck didn't play with Lego blocks. $\endgroup$ Dec 31 '18 at 14:34
  • $\begingroup$ Ok, then I stand corrected. Are you suggesting that spacetime may have cardinality greater than $\aleph_0$ or that it doesn’t make sense talk about universe in this way? Why? $\endgroup$ Dec 31 '18 at 15:09

From discussion in the comments:

obviously if I want to output an irrational number, it will just be to a certain accuracy p which may be input to the program.

Of course, there is a program that infinitely outputs all possible decimal expansions. Any irrational number will eventually appear in this output (within certain accuracy $p$).

But look at the statement of the theorem. Could such a program be used to find decimal expansion of certain irrational number of interest? When exactly should we expect decimal expansion of this number to appear? This is undecidable.

It might be easier to understand this via another example. Consider this problem:

You are given the source code of some (deterministic) program. You're also given a proof that this program terminates and outputs some positive integer. What is this number?

You tried to run the program, but it is still running and there's no progress bar. It might take 10 minutes, it might take 1000 years. You don't know. You only have a proof that the program eventually stops.

Surely, you can write a program that outputs all possible positive integers. Surely, the correct answer to the problem appears somewhere in this infinite list. But does it help to solve the problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.