Outer Limits of Reason (28 page)

This means that the value of
x
should be incremented by 1. Since some programs demand inputs, we will write

x=?

when the computer should stop and ask the user for a number. Variable
x
will be given the value that the user entered. Some lines will have a label like
A
,
B
, or
C
. These labels will be used to control the execution of the programs. Programs that only go from top to bottom are not very interesting. There is a need for loops so that a program can perform actions repetitively. Labels allow us make loops by using the
goto
statement.

To get a good intuition about programs, let's look at a few examples:

x=?

x=x+1

x=x+1

print x

stop

What task does this program perform? If 15 is the input to this program, then the variable
x
would contain 15 because of the first line. The next three lines would each increment
x
by 1 with a combined effect of adding 3. The computer would then print the contents of
x
, namely 18. Once this is done, the computer would halt. If 56 were entered, the program would print 59. In general, the function this program computes is
f
(
x
)
=
x
+
3.

This is fun! Let's try some more examples.

First focus on the left-hand program. If the user inputs 23, what happens? The variable
x
would have the value 23 and the variable
y
would have the value 10. The next two lines of the program work in tandem:
x
gets incremented to 24 and
y
decrements to 9. The next line is a conditional statement. Since
y
is 9 and hence more than 0, the computer would go back up to the line with the label
A
. From there,
x
would go up to 25 and
y
would go down to 8. This loop continues until
x
is 33 and
y
is 0. At this point, the conditional statement fails and the print statement is executed. The number 33 will be outputted since that is the value of
x
. If
x
started off as 108, then 118 would be printed. In general, this program computes the function
f
(
x
)
=
x
+
10.

Now for the right-hand program. It is almost the same as the left-hand program, with a single difference. Rather than having
y=10
, there is
y=?
. This program demands two inputs, as opposed to one. Rather than counting down from 10, this program will count down from any starting value of
y
. It is not hard to see that this program will compute the function of two values
f
(
x,y
)
=
x
+
y
. One does not need much convincing to see that programs written in this programming language can perform most of the tasks that calculators can perform. In fact, with enough encoding, programs like these can perform any task that any computer can perform.

Let us examine some more programs.

If one enters 5 in the left-hand program, the conditional statement will fail and this program will immediately terminate. In contrast, if one enters 15, the program will go into an infinite loop. In fact, entering any number less than or equal to 9 for
x
will halt the program, and for any number 10 or above, the program will go into an infinite loop.

What about the right-hand program? Can you determine when this program will halt and when it will get lost wandering around its loops? Neither can I! How about getting a computer to solve this problem . . .

6.2  To Halt or Not to Halt?

Let us formulate the Halting Problem. Given any program and an input for it, determine whether the program with that input will halt or go into an infinite loop. It is a decision problem—that is, it gives a Yes or No answer. Can a computer solve the Halting Problem?

The question was described by Alan M. Turing (1912–1954) and in 1936 he gave a definitive negative answer: there is no program that can solve the Halting Problem. There is no way for a computer to determine for any given program, and for any given input into that program, whether the program will halt on that input. If a computer can solve a decision problem, we say the problem is
decidable
. In contrast, if a computer cannot solve it, we say the problem is
undecidable
. The Halting Problem is undecidable.

A few minutes of meditation are in order. We first have to differentiate between problems being infeasible, which we focused on in the last chapter, and problems being undecidable. In the last chapter, problems could be solved, but for large inputs, an unreasonable amount of time is demanded. We are not saying that here. The Halting Problem cannot be solved in any amount of time. It is not a
hard
problem; it is an
impossible
problem.

Furthermore, observe that there is an objective answer to the question of whether a program for a given input will halt. It is not some subjective, wishy-washy idea like artistic taste or morality. Either the program will eventually halt or it will continue in an infinite loop, and yet computers cannot decide that objective question. Even human beings might have a hard time determining it (more about this in
section 6.5
). Nevertheless, there is a real, objective answer.

Another point to notice is that Turing did not say that he is incapable of writing such a program. Nor did he say that no one else is clever enough to find such a program. Rather, he proved that no such program could exist. The difficulty was not the lack of technology or ingenuity. Turing showed that no amount of technological innovation or ingenuity can ever solve this problem. On a deeper level, he was saying that neither computers nor any other physical devices obeying reason would be able to solve the Halting Problem.

You might think of an easy way to show that the Halting Problem is decidable: run the program with the given input and see whether it halts or goes into an infinite loop. Alas, this method will not work. If you run the program for ten minutes and it halts, you can safely say that this program for this input will halt. But what happens if the program is still running after ten minutes? That does not mean that the program is in an infinite loop because many programs require more than ten minutes to terminate. Perhaps you should run the program for twenty minutes. Again, if it halts, you are done. However, if it does not halt, what do we know? We are still not sure that it is in an infinite loop. How long should we run the program? For any given time limit, there are programs that need a little more time before they terminate.
²
The only way we can tell if a program is in an infinite loop is to wait an infinite amount of time and see if it is still running. But who has that much time?

One of the most amazing aspects of Turing's result is that it was demonstrated in 1936, long before any computer existed. Turing, a brilliant theoretical mathematician, demonstrated limits on the power of computers years before the practical engineers figured out how to create a computer. Theoreticians rock!

 

Now that we have meditated and absorbed why the undecidability of the Halting Problem is interesting and worthy of deeper understanding, let us go about actually proving it. The undecidability is proved using the fact that computers can talk about themselves. That is, computers have self-reference. Since programs can discuss programs, there is an element of self-reference and hence a limitation. By now, we have seen self-reference many times in our book—for example, with the liar paradox, where self-referential English sentences discuss themselves:

This sentence is false.

We showed that the sentence is true if and only if it is false. Here we will create a self-referential program that essentially says the following:

This program will give the wrong answer when asked if it will halt or go into an infinite loop.

As we will see, the existence of such a program will cause a contradiction. Such contradictions are not permitted in the real world of computers, hence we have a limitation: the Halting Problem cannot be solved. The proof is a type of proof by contradiction. Assume that the Halting Problem is not undecidable (i.e., that a computer
can
decide this problem); with this assumption we derive a contradiction:

The Halting Problem is decidable ⇒ contradiction.

We have to conclude that our assumption must be incorrect.

Notice that the programs we talked about in the last section are very simple creatures. They are easy to describe and it turns out that we can encode such programs as whole numbers.
³
For any program, there is a unique number that corresponds to the program. For a given program the associated number will be called the “program number.” We can also go the other way: from a number, we can find its program. For number
x
, we call the program associated with it “program
x
.” The idea is that the programs deal with numbers and numbers represent the programs; therefore we will have programs deal with programs as in
figure 6.1
. This is the core of self-reference.

Let us imagine that the Halting Problem is decidable and we can actually create a program that decides it. That would mean that we could sit down and write a computer program that works as follows: input a program number
y
and an input number
x
and the computer will output a Yes or No depending on whether program
y
with input
x
will halt. We write this function as

The program that determines the halt(
y,x
) function is a black box that takes two inputs and outputs a Yes or No, as in
figure 6.2
.