MODULE 5
308 CHAPTER 8. INTRODUCTION TO TURING MACHINES
is hello, world. Although might imagine that simulation of the program
we
would allow us does, we must in reality contend with
to tell what the program
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.1.1 Programs that Print "Hello, World"
In Fig. 8.1 is the first C program met by students who read Kernighan and
Ritchie's 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.
main()
{
printf("hello, world\n");
}
Figure 8.1: Kernighan and Ritchie's hello-world program
However, there are other programs that also print hello, world; yet the
fact that they do so is far from 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" = z". 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, z) 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 x, y, and z, by first allowing x to range from 1 to
total-2, and within that for-loop allowing y to range from 1 up to one less
than what x 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 xn + y" = z". If
so, the program prints hello, world, and if not, it prints nothing.
1B. W. Kernighan and D. M. Ritchie, The C Programming Language, 1978, Prentice-Hall,
Englewood Cliffs, NJ.
8.1. PROBLEMS THAT COMPUTERS CANNOT SOLVE 309
int exp(int i, n)
/* computes i to the power n */
{
int ans, j;
ans = 1;
for (j=1; j<=n; j++) ans *= i;
return(ans);
}
main ()
{
int n, total, x, y, z;
scanf ("%d", &n);
total = 3;
while (1) {
for (x=1; x<=total-2; x++)
for (y=1; y<=total-x-1; y++( {
z = total - x - y;
if (exp(x,n) + exp(y,n) exp(z,n)) ==
printf("hello, world\n");
}
total++;
}
}
Figure 8.2: Fermat's 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, x = 3, y 4, and z 5, for which = =
xh + yn = Thus, for input 2, the program does print hello, world.
z".
However, for any integer n > 2, the program will never find a triple of
positive integers to satisfy xn + y" = 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 x" +y^ 2 =
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 "Fermat's last theorem."
Let define the hello-world problem to be: determine whether a given C
us
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