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

Question

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.

Answer 1

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!).

Answer 2

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

Answer 3

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).

Answer 4

If the number of printable sequences can be taken to be countable, then count the sequences and then create a sequence as follows:

The first term is one greater than the first term of the first sequence The second term is the smallest integer greater than both the first term already determined and the second term of the second sequence

and so forth, in imitation of the Cantor Diagonal Argument and preserving the defining property of the sequence.

---

But the question leaves open whether the elements of $A$ have to be consecutive in the printout - a single program is mentioned. For this note that every sequence of increasing integers is a subsequence, in order, of $1,2,3,4,5 \dots $

It would be possible to organise finite sequences in order so that they are consecutive within the printout, but don't necessarily start in the first place (there are countably many finite sequences - just put them in order of a suitable list) - but this won't work for the infinite sequences

Answer 5

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.

Answer 6

An explicit solution in your system could be :

1. Consider an enumeration of your programs ($P_0$ is the first program, $P_1$ the second, and so on)
2. Let denote by $P_{\! n}(m)$ the m$^\mbox{th}$ number printed by program $P_{\!n}$ (if it exists)
3. Consider the integers $i_n$ defined by $$i_n=n+1+\max_{j,k\le n}\{P_j(k)\}$$ (if the subset is empty, just remember that max of a empty subset is $0$).
4. Hence $i_{n+1}>i_n$
5. The set $\{i_n\}_{n\in\mathbb N}$ can not be printed as you want because if it can be printed in ascending order by some program, then there is a $s$ such that $P_s(n)=i_n$, but then $$P_s(s)=i_s\ge s+1+P_s(s)>P_s(s)$$ This is a contradiction !

Answer 7

The following is an elementary and informal approach which does not use set theory:

First, fix the syntax for your computer programs and enumerate them by natural numbers.

Definition: Denote $A\subset{\mathbb N}$ the set of those numbers which correspond to a computer program that prints out infinitely many numbers (in ascending order), and call such a program observably nonterminating.

Claim: There is no computer program which prints $A$ in ascending order.

Edit: In the following I argue that the printability of $A$ implies the (contradictory) printability of a set as in QuestionC's more direct answer.

Proof of claim: For otherwise, note first that such a program could be used to decide, for any $n$, whether the program with number $n$ is observably nonterminating: namely, pick any $m\geq n$ numbering a program that you know to print out infinitely many numbers, wait for you hypothetical computer program to output $m$, and look if it printed $n$ until then.

However, building on such a decision procedure for observable nontermination, you can write a computer program that prints out $n$ if either $n$ does not number a observably nonterminating program, or if $n$ does number a observably nonterminating program which however does not print $n$. This is well-defined since for any observably nonterminating program it is decidable whether it prints a given number: as above, wait long enough for a larger number to be printed, and look whether the number you are interested in has been printed before. Note that this program is observably nonterminating since there are infinitely programs that print out only finitely many numbers, and the numbers of all these programs will be printed. Finally, this observably nonterminating program itself has a number, and looking at whether or not it prints its own number gives rise to contradiction.

Answer 8

If you can define a function to determine whether a given integer is in the set, then I can write a program that can print integers in the set until it runs out of storage.

Your "question" is actually a statement, but assuming you ask whether the statement is true, the answer is "yes." For example, I know of a way to generate truly random numbers. No program can predict which numbers will not come from this device.