Countability and Uncountability of Computer Programs

Question

I'm having trouble with countability and uncountability. I'm stuck on a homework question without an idea how to approach it.

Argue the following:

• The set of computer programs in any language must be at most countably infinite. What do we know about computer programs?
• For a given programming language, most real numbers cannot be computed as the (potentially infinite) output of any program.

Anything would be of help!

Answer 1

Each program is a finite sequence of a finite number of symbols.
Each program is a finite sequence of a finite number of operations. There are an finite number of programs of length n.
Add the number of all these groups of programs
to conclude there are denumberable many programs.

As each program has a finite output, all together all
the possible programs has denumberable many outputs.

Thus, most of the real numbers are beyond human and machine reach.

Answer 2

A language is a set of words, which are themselves finite sequences of elements of some alphabet, say $\Sigma$. I assume that the alphabet $\Sigma$ is finite (it has to be finite or countable otherwise otherwise claim 1 is wrong). Let's assume that $\Sigma \neq \emptyset$ (I like alphabets that actually allow you to write something, don't you?).

Let $\Sigma^*$ be the set of words using alphabet $\Sigma$. $\Sigma^*$ is at most countable since it is a countable union of finite sets :

$$\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n$$

Hence, there are at most countably many computer programs using alphabet $\Sigma$.

There are uncountably many real numbers (cf Cantor's proof), and only countably many programs. Hence, most of the real numbers can't be written by computer programs using a given finite alphabet.