22
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Broken_Window He clearly using unsigned integers. The maximum is 4,294,967,296. $\endgroup$ – KSmarts Dec 30 '14 at 18:16
  • 3
    $\begingroup$ This is not set theory, and is not elementary set theory, stop adding the tags. (Yes, sets are mentioned. It does not matter.) $\endgroup$ – Andrés E. Caicedo Dec 30 '14 at 20:08
  • 2
    $\begingroup$ So? You mentioned primes, and yet this is not number theory. You mention sets, and yet... $\endgroup$ – Andrés E. Caicedo Dec 30 '14 at 20:11
  • 6
    $\begingroup$ Okay you are right... So I should go to my teacher and tell him that in the next time he likes to give us a question that is not in the course, it should be about pottery. $\endgroup$ – Meitar Dec 30 '14 at 20:13
  • 3
    $\begingroup$ +1. Fun side question: Is there a set that no computer program can print in ascending order, but you can write a program that prints every element of the set, unordered? (Hint: The answer is yes.) $\endgroup$ – nikie Jan 1 '15 at 9:21
62
$\begingroup$

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 x1x2...xN where xi is 0 or 1 for each i.

Let us define Num(X) as the binary number 1x1x2...xN. 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!).

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ The program that prints the empty set is red. $\endgroup$ – Thom Smith Dec 30 '14 at 19:39
  • 2
    $\begingroup$ @QuestionC: There is no relevant meaning of "program" that is specific to set theory. Assuming that the problem isn't mean to entail developing computability theory from scratch, the intended solution must indeed be to be at the level of "every program is a finite string of symbols ...". However, given that it is a set-theory problem, I don't think the intention is to fold Cantor's proof into the solution; rather to recognize that a counting argument will work. $\endgroup$ – hmakholm left over Monica Dec 30 '14 at 20:02
  • 1
    $\begingroup$ @Meitar: Wasn't that exactly what you were asking? The number of a program is its text interpreted in base 256. $\endgroup$ – hmakholm left over Monica Dec 30 '14 at 20:10
  • 1
    $\begingroup$ I added details which hopefully let you reach the idea that you can assign a distinct natural number to any program. I believe the term for this is "Godel numbering". $\endgroup$ – QuestionC Dec 30 '14 at 21:56
  • 1
    $\begingroup$ Elegance is, of course, in the eye of the beholder. But, to me, the observation that there are countably many programs but uncountably many subsets of $\mathbb{N}$ is much more elegant. $\endgroup$ – David Richerby Jan 1 '15 at 13:13
35
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is about sets...If you take a sequence you have to rearrange the elements in ascending order and exclude elements that repeat themselves... The program uses a set and prints it... Not a sequence... $\endgroup$ – Meitar Dec 30 '14 at 15:40
  • 1
    $\begingroup$ As I understand it there is one program. Could you expand on your answer? $\endgroup$ – David Peterson Dec 30 '14 at 15:41
  • 2
    $\begingroup$ @David: If there is one program, then there is one output sequence. The question asks whether each of the uncountably many output sequences can be produced by one of the countably many programs. This is a fine answer. (The OP refers to "the program", but this is clearly a typo, because if there's only one program, the question makes no sense.) $\endgroup$ – WillO Dec 30 '14 at 15:43
  • $\begingroup$ How come there are only a countable number of programs? Of course there are only a finite number of realized programs, but here we must consider all possible but perhaps not realized programs. $\endgroup$ – Lehs Dec 31 '14 at 16:10
  • 1
    $\begingroup$ @Lehs every program can be coded as a natural number. $\endgroup$ – Jihad Dec 31 '14 at 16:30
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for connecting the problem to decidability and providing a concrete example. $\endgroup$ – Nick Dec 30 '14 at 17:28
  • 2
    $\begingroup$ Paragraph 1 directly contradicts the question - if said computer can print "All the prime numbers", then it must have an infinite number of states. Thus, we're looking at something possibly superior to a Turing machine, and any notion of decidability is off the table until we can prove equivalence. $\endgroup$ – Aaron Dufour Dec 30 '14 at 18:10
  • $\begingroup$ @AaronDufour A Turing Machine has an infinite number of 'states' in the sense that you're talking about: the state of a Turing machine includes the state of its worktape. You're possibly confusing Turing Machines with (pure) Finite State Machines (with no worktape), which can only 'compute' (for whatever definition of that word you want; e.g., recognize) a subset of the Turing-computable sets. $\endgroup$ – Steven Stadnicki Dec 30 '14 at 18:26
  • $\begingroup$ (That said, Paragraph 1 is incorrect - a Turing machine has a countable number of states, but not a finite number.) $\endgroup$ – Steven Stadnicki Dec 30 '14 at 18:26
  • 1
    $\begingroup$ @StevenStadnicki The representation of a Turing machine that I am familiar with distinguishes between the state and the tape or memory. So a Turing machine has an infinite number of states in the sense you mean, but a finite number in the sense that I mean. $\endgroup$ – KSmarts Dec 30 '14 at 19:03
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ That would be Gödel or Goedel, never *Godel. $\endgroup$ – tchrist Jan 1 '15 at 20:14
1
$\begingroup$

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 !
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.