Figure 8.3: A hypothetical program H that is a hello-world detector

be decidable. Otherwise, the problem is undecidable. Our goal is to prove that H doesnt exist; i.e., the hello-world problem is undecidable.

In order to prove that statement by contradiction, we are going to make several changes to H, eventually constructing a related program called H2 that we show does not exist. Since the changes to H are simple transformations that can be done to any С program, the only questionable statement is the existence of Я, so it is that assumption we have contradicted.

To simplify our discussion, we shall make a few assumptions about С programs. These assumptions make Hs job easier, not harder, so if we can show a hello-world tester for these restricted programs does not exist, then surely there is no such tester that could work for a broader class of programs. Our assumptions are:

1, AH output is character-based, e,g., we are not using a graphics package or any other facihty to make output that is not in the form of characters,

2. All character-based output is performed using printf, rather than put-char () or another character-based output function.

We now assume that the program H exists. Our first modification is to change the output no, which is the response that H makes when its input program P does not print hello, world as its first output in response to input /. As soon as H prints n, we know it will eventually follow with the o. Thus, we can modify any printf statement in H that prints n to instead print hello, world. Another printf statement that prints an o but not the n is omitted. As a result, the new program, which we call Я1, behaves like Я, except it prints hello, world exactly when H would print no. Hi is suggested by Fig, 8,4,

Our next transformation on the program is a bit trickier; it is essentially the insight that cdlowed Alan Turing to prove his rmdecidability result about Turing machines. Since we are really interested in programs that take other programs as input and tell something about them, we shall restrict Я1 so it:

a) Takes only input P, not P and /.

Most likely, the program would put no in one printf, but it could print the n in one printf and the 0 in another.

hello, world

Figure 8,4: Hi behaves like H, but it says hello, world instead of no

b) Asks what P would do if its input were its own code, i.e what would Hi do on inputs P as program and P as input / as well?

The modifications we must perform on Hi to produce the program H2 suggested in Fig. 8.5 are as follows:

1, H2 first reads the entire input P and stores it in an array A, which it mallocs for the purpose,

2. H2 then simulates Hi, but whenever Hi would read input from P or /, H2 reads from the stored copy in A. To keep track of how much of P and / Hi has read, H2 can maintain two cursors that mark positions in A.

hello, world

Figure 8.5: H2 behaves like Hi, but uses its input P as both P and /

We axe now ready to prove H2 cannot exist. Thus, Hi does not exist, and likewise, H does not exist. The heart of the argument is to envision what Я2 does when given itself as input. This situation is suggested in Fig, 8.6. Recall that H2, given any program P as input, makes output yes if P prints hello, world when given itself as input. Also, H2 prints hello, world if F, given itself as input, does not print hello, world as its first output.

Suppose that the Я2 represented by the box in Fig. 8.6 makes the output yes. Then the H2 in the box is saying about its input H2 that Я2, given itself

*The UNIX malloc system function allocates a block of memory of a size specified in the call to malloc. This function is used when the amount of storage needed cannot be determined until the program is run, as would be the case if ал input of arbitrary length were read. Typically, malloc would be called several times, as more and more input is read and progressively more space is needed.

hello, world

Figure 8.6; What does Яз do when given itself as input?

as input, prints hello, world as its first output. But we just supposed that the first output H- makes in this situation is yes rather than hello, world.

Thus, it appears that in Fig. 8.6 the output of the box is hello, world, since it must be one or the other. But if H-2, given itself as input, prints hello, world first, then the output of the box in Fig. 8.6 must be yes. Whichever output we suppose makes, we can argue that it makes the other output.

This situation is paradoxical, and we conclude that H2 cannot exist. As a result, we have contradicted the assumption that Я exists. That is, we have proved that no program Я can tell whether or not a given program P with input / prints hello, world as its first output.

8.1,3 Reducing One Problem to Another

Now, we have one problem - does a given program with given input print hello, world as the first thing it prints? - that we know no computer progratn can solve. A problem that cannot be solved by computer is called undecidable. We shall give the formal definition of undecidable in Section 9.3, but for the moment, let us use the term informally. Suppose we want to determine whether or not some other problem is solvable by a computer. We can try to write a program to solve it, but if we cannot figure out how to do so, then we might try a proof that there is no such program.

Perhaps we could prove this new problem undecidable by a technique similar to what we did for the hello-world problem: assume there is a program to solve it and develop a paradoxical program that must do two contradictory things, like the program Я, However, once we have one problem that we know is undecidable, we no longer have to prove the existence of a paradoxical situation. It is sufficient to show that if we could solve the new problem, then we could use that solution to solve a problem we already know is undecidable. The strategy is suggested in Fig, 8.7; the technique is called the reduction of Л to Fg.

Suppose that we know problem Pi is undecidable, and P2 is a new problem that we would like to prove is undecidable as well. We suppose that there is a program represented in Fig. 8.7 by the diamond labeled decide ; this program prints yes or no, depending on whether its input instance of problem P2 is or is not in the language of that problem.

Recan that a problem is really a language. When we talked of the problem of deciding