mainO

>

printf( hello, world\n );

Figure 8.1: Kernighan and Ritchies hello-world program

However, there are other programs that also print hello, world; yet the fact that they do so is far firom obvious. Figure 8,2 shows another program that might print hello, world. It takes an input n, and looks for positive integer solutions to the equation x +y = г . If it finds one, it prints hello, world. If it never finds integers x, y, and z to satisfy the equation, then it continues searching forever, and never prints hello, world.

To understand what this program does, first observe that exp is an auxiliary function to compute exponentials. The main program needs to search through triples {x, y, г) in an order such that we are sure we get to every triple of positive integers eventually. To organize the search properly, we use a fourth variable, total, that starts at 3 and, in the while-loop, is increased one unit at a time, eventually reaching any finite integer. Inside the while-loop, we divide total into three positive integers ж, у, and г, by first allowing x to range from 1 to total-2, and within that for-loop allowing у to range from 1 up to one less than what ж has not already taken from total. What remains, which must be between 1 and total-2, is given to z.

In the innermost loop, the triple {x,y, z) is tested to see if a: -- y - z . If so, the program prints hello, world, and if not, it prints nothing.

B, W, Kernighan and D. M. Ritchie, The С Programming Language, 1978, Prentice-Hall, Englewood Cliffs, NJ,

is hello, world. Although we might imagine that simulation of the program would allow us to tell what the program does, we must in reality contend with programs that take an unimaginably long time before making any output at all. This problem - not knowing when, if ever, something will occur -- is the ultimate cause of our inability to tell what a program does. However, proving formally that there is no program to do a stated task is quite tricky, and we need to develop some formal mechanics. In this section, we give the intuition behind the formal proofs,

8ЛЛ Programs that Print Hello, World

In Fig. 8.1 is the first С program met by students who read Kernighan and Ritchies classic book,-* It is rather easy to discover that this program prints hello, world and terminates. This program is so transparent that it has become a common practice to introduce languages by showing how to write a program to print hello, world in those languages.

int expCint i, n)

/* computes i to the power n */

int ans, j; ans = 1;

for Cj=l; j<=n; j++) ans *= i; return(ans);

>

main () {

int n, total, X, y, z; scanf( y,d , &n); total = 3; while (1) <

for (x=l; x<=total-2; x++)

for Cy=l; y<=total-x-l; y++) -[ 2 = total -x-y;

if Cexp(x,n) + exp(y,n) == exp(z,n)) printf( hello, world\n );

total++;

Figure 8.2: Fermats last theorem expressed as a hello-world program

If the value of n that the program reads is 2, then it will eventually find combinations of integers such as total = 12, ж = 3, у = 4, and г = 5, for which x 4- = z . Thus, for input 2, the program does print hello, vorld.

However, for any integer n > 2, the program will never find a triple of positive integers to satisfy -I- j/ = z , and thus will fail to print hello, world. Interestingly, until a few years ago, it was not known whether or not this program would print hello, world for some large integer n. The claim that it would not, i.e., that there are no integer solutions to the equation z + y - z if n > 2, was made by Fermat 300 years ago, but no proof was found until quite recently. This statement is often referred to as Fermats last theorem.

Let us define the hello-world problem to be: determine whether a given С program, with a given input, prints hello, world as the first 12 characters that it prints. In what follows, we often use, as a shorthand, the statement about a program that it prints hello, world to mean that it prints hello, world as the first 12 characters that it prints.

It seems likely that, if it takes mathematicians 300 years to resolve a question

Why Undecidable Problems Must Exist

While it is tricky to prove that a specific problem, such as the hello-world problem discussed here, must be undecidable, it is quite easy to see why almost all problems must be undecidable by any system that involves programming. Recall that a problem is really membership of a string in a language. The number of different languages over any alphabet of more than one symbol is not countable. That is, there is no way to assign integers to the Ijmguages such that every language has an integer, and every integer is assigned to one language.

On the other hand programs, being finite strings over a finite alphabet (typically a subset of the ASCII alphabet), are countable. That is, we can order them by length, and for programs of the same length, order them lexicographically. Thus, we can speak of the first program, the second program, and in general, the ith program for any integer i.

As a result, we know there are infinitely fewer programs than there are problems. If we picked a language at random, almost certainly it would be an undecidable problem. The only reason that most problems appear to be decidable is that we rarely are interested in random problems. Rather, we tend to look at fairly simple, well-structured problems, and indeed these are often decidable. However, even among the problems we are interested in and can state clearly and succinctly, we find many that are undecidable; the hello-world problem is a case in point.

about a single, 22-line program, then the general problem of telling whether a given program, on a given input, prints hello, world must be hard indeed. In fact, any of the problems that mathematicians have not yet been able to resolve can be turned into a question of the form does this program, with this input, print hello, world? Thus, it would be remarkable indeed if we could write a program that could examine any program P and input / for P, and tell whether P, run with I as its input, would print hello, world. We shsdl prove that no such program exists.

8.1.2 The Hypothetical Hello, World Tester

The proof of impossibifity of making the hello-world test is a proof by contradiction. That is, we assume there is a program, call it H, that takes as input a program P and an input /, and tells whether P with input / prints hello, world. Figure 8.3 is a representation of what H does. In particular, the only output H makes is either to print the three characters yes or to print the two characters no. It always does one or the other.

If a problem has an algorithm like Я, that always tells correctly whether an instance of the problem has answer yes or no, then the problem is said to