How is the set of all programs countable?
I'm having a hard time seeing how the number of programs is not uncountable, since for every real number, you can create a program that's prints out that number. Doesn't that immediately establish uncountably many programs?
Solution 1:
I don't know your definition of 'program', but I'm fairly sure that any program will be a finite length string of characters over some finite alphabet. For any finite set $X$, the set $X^*$ of all finite length strings over $X$ is countable (by the same sort of argument you would use to show the rationals are countable).
Solution 2:
If you are programming in a language having the following restrictions:
- There are only finitely many characters in the language.
- Every program is finite.
Then the set of all programs is countable, as it is a subset of all the finite strings in the language which itself is countable.
Also, what does it mean to "print out a real number"? If it has an infinite decimal expansion (e.g. an irrational number) then printing it never halts, is this a legal behavior for your program? If not then certainly you cannot write a program which prints every real number.
If you are allowed to print an infinite length output, and your program is finite then you have to calculate the number somehow, but there is only a countable number of numbers which you can compute their values. So yet again, you cannot print all the real numbers.