Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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?
