There is a subset of positive integers which no computer program can print

It's said that a computer program "prints" a set $A$ ($A \subseteq \mathbb N$, positive integers.) if it prints every element of $A$ in ascending order (even if $A$ is infinite.). For example, the program can "print":

1. All the prime numbers.
2. All the even numbers from $5$ to $100$.
3. Numbers including "$7$" in them.

Prove there is a set that no computer program can print.

I guess it has something to do with an algorithm meant to manipulate or confuse the program, or to create a paradox, but I can't find an example to prove this. Any help?

Guys, this was given to me by my Set Theory professor, meaning, this question does not regard computer but regards an algorithm that cannot exhaust $\mathcal{P}(\mathbb{N})$. Everything you say about computer or number of programs do not really help me with this... The proof has to contain Set Theory claims, and I probably have to find a set with terms that will make it impossible for the program to print. I am not saying your proofs including computing are not good, on the contrary, I suppose they are wonderful, but I don't really understand them nor do I need to use them, for it's about sets.

There is a really elegant proof for this that requires virtually no math background at all.

All computer programs are a finite sequence of bytes, which is just a number in base 256. So each computer program can be represented as a unique natural number. This statement is elaborated in detail below the divide.

• If a computer program prints its own number, then that program is blue and its number is blue.
• If a program does not print its own number, then that program is red and its number is red.

The set of red numbers is a subset of natural numbers. Now write a program that prints this set. Is that program red or blue?

• Suppose the program is red. Then it must print its own number as part of the set, but this causes it to be a blue program.
• Suppose the program is blue. Then it must print its own number as a blue program, but this causes its output to not be the set of red numbers.

This program is impossible! Therefore, there must exist at least one set which programs can not print.

This is how I learned the Cantor set/subset inequality. I couldn't find a better link, but I got it from a Martin Gardner book.

Addendum

Let's get into the statement

each computer program can be represented as a unique natural number

This will involve some math, particularly working in binary. We are going to create a Gödel numbering for computer programs.

Assume every program can be represented as a finite string of 0's and 1's. This accurately describes real world programs and the input to a Universal Turing Machine.

So any given program X is x₁x₂...x_N where x_i is 0 or 1 for each i.

Let us define Num(X) as the binary number 1x₁x₂...x_N. Num(X) of the program X = '0110' would be '10110' in binary, which is 22.

Num(X) gives each program a unique natural number because...

• If two programs have differing length, then the longer program has a greater Num() than the shorter.
• If two programs have identical length but differ on some bits, then the binary representation is different for that bit, so Num() will differ between the programs.
• In any other case, the two programs have identical length and identical bits, meaning they are identical programs.

Now we can get on to the set theory part of the proof.

That proof assumed binary, but as long as your program is finitely describable in any language which uses a finite number of characters (like English!) you can similarly map it to a unique natural number. This is interesting because it extends the proof from programs to any describable concept (like genie wishes!).

There are countably many programs but the number of subsets of $\mathbb{N}$ is uncountable.

Any known model of computing, and thus any computer we can make, is equivalent to a Turing machine. Since the number of different possible inputs and states of a Turing machine is finite, there are, as Jihad said, countably many possible programs. Since there are uncountably many subsets of the natural numbers, there must be some subsets that the computer can not print.

If you want to find something specific, you should look to uncomputable functions, or undecidable problems.

For example, you could have it try to print A060843, the Busy Beaver numbers. The Busy Beaver function determines the maximum number of steps that an $n$-state Turing machine can take before halting. Basically, it tells you how long a computer can run without getting stuck in an infinite loop. It grows extremely quickly: only the first $4$ elements of this sequence are known exactly, the fifth is known to be more than $47$ million, and the sixth is more than $8$ quadrillion.

Finding a general-case algorithm for this function would be equivalent to solving the halting problem, which is undecidable. This means that while the sequence is well-defined, it is not computable.

Or, given some encoding of logical statements to natural numbers, you could have it print the set of all $n$ where the statement represented by $n$ is true. This is Hilbert's Decision Problem, or Entscheidungsproblem, and is very similar (possibly equivalent, I'm not sure) to WillO's answer about Gödel Numbers.

You could also break it through self-reference, as Mark Bennet suggests.

Jihad's answer proves that some such $A$ exists. For an explicit example, let $A$ be the set of Godel numbers of true statements about arithmetic (after fixing your favorite encoding).