Outer Limits of Reason (29 page)

We will denote the (nonexistent) program for this function as
Halt(y,x)
. Now that we have the ability to reference programs and numbers, let us use this presumed program as part of the following bigger program:

This program is very important and will be called Program D (for “diagonal”). Let's just look at this program as a diagram. The construction of Program D can be visualized in
figure 6.3
, which uses
figure 6.2
as a black box within it.

This program accepts one input, which becomes both the program number and the input (self-reference). If this program halts on its own input, it goes into an infinite loop. In contrast, if the program with the input goes into an infinite loop, it halts and prints a No. Essentially this program gives the wrong answer when asked about input
x.

Formally, the action of Program D on input
x
is as follows:

Program D on input
x
halts if and only if program
x
on input
x
loops.

Hold on! Now comes the interesting part: if
Halt
is a real program, we have no worries using it as a part of another program and can create Program D. If Program D is a real program, then it has a number. We do not know exactly what the number is, but we might as well denote it as
d
₀
. Now let us input the number
d
₀
into Program D. That is, let's see what Program D says about itself.

Program D on input
d
₀
halts if and only if program
d
₀
on input
d
₀
loops.

But program
d
₀
is exactly Program D, so we can restate this line as

Program D on input
d
₀
halts if and only if Program
D
on input
d
₀
loops.

This is a contradiction. We can say that

Program D gives the wrong answer about itself when asked if it will halt or go into an infinite loop.

We are right back to the liar paradox. We have come to a point where a program halts if and only if it does not halt. Human language and human minds might have contradictions but computers do not. Something must be wrong. Only one assumption was made: that it is possible to write a program that decides the Halting Problem. That assumption caused us to reach a contradiction, hence it must have been wrong. It is impossible to solve the Halting Problem with a computer.

The above proof of the undecidability of the Halting Problem is a bit complicated and it will be helpful to look at it from another point of view. It might be easier to visualize it as a diagonalization proof. (If you have already glanced at
chapter 4
, this proof will be more palatable.) Assume for a moment that we have access to a program that decides the Halting Problem. We can write the output of such a program as an infinite matrix (see
figure 6.4
).

The numbers along the left-hand column are the program numbers. The numbers across the top row correspond to the inputs to the program. The Yes's or No's inside tell us whether that program with that input will halt. For example, program 7 with input 2 has a No. This means that if you input number 2 into program 7, the program will go into an infinite loop. In contrast to that, program 4 with input 8 will halt. We used this (supposed) program to create a new program by diagonalization. Program D only has one input and its value is determined by looking at the diagonal elements of the matrix in
figure 6.4
. The program accepts a number as input. On input
x
, Program D determines whether program
x
on input
x
halts and does the exact opposite, as in
figure 6.5
.

The numbers along the edges are the inputs to the program, and the Yes's and No's inside tell us if the program with those inputs will halt or loop.

Although this new (supposed) Program D is easily constructed from the
Halt
program, it can nevertheless be shown that Program D does not exist. If it did exist, it would have a number associated with it. But which number could it be?

• It cannot be program 0 because program 0 on input 0 goes into an infinite loop and Program D on input 0 halts.

• It cannot be program 1 because program 1 on input 1 halts and Program D on input 1 goes into an infinite loop.

• It cannot be program 2 because program 2 on input 2 goes into an infinite loop and Program D on input 2 halts.

• Etc.

• It cannot be program
d
₀
because program
d
₀
on input
d
₀
does “this” and Program D on input
d
₀
does “that.”

• Etc.

In other words, Program D cannot exist because it has the wrong answer on what it will do when we ask it about itself. We conclude that there is no such Program D, so there must be something wrong with our original assumption that the
Halt
program exists.

Summing up, we have shown that if the
Halt
program exists, then Program D exists, and since Program D cannot exist, the
Halt
program cannot exist. In our notation:

Halt
program exists ⇒ Program D exists ⇒ contradiction.

Which means the Halting Problem is undecidable.

6.3  They're All Connected

The Halting Problem is not the only undecidable problem. I will show that there are many other problems that cannot be solved or decided by a computer.

Consider the
Printing 42 Problem
. Given a program, determine whether there is any input to the program that will cause the program to print the number 42.
⁴
Let's look at a sample program:

This program has a loop within a loop. The inner loop adds the number in
z
to
x
. In the outer loop,
z
is set to 10 and this outer loop is done three times. In conclusion, this program adds 10 × 3 = 30 to
x
. So the only way this program will output 42 is if 12 is the input. We conclude that there is an input that will output 42. However, determining what this program does was fairly simple. One can give fairly complicated programs where it is hard to tell if the program will ever print out a 42.

The Printing 42 Problem is also undecidable. While we will not prove this result, we can get an intuition that this problem is harder than the Halting Problem. Our aim with the Halting Problem was to determine if a particular input would get the program to halt. With the Printing 42 Problem we are asking if there is
any
input that would halt and give an output of 42. We would have to search all inputs.

Let us consider the
Zero Program Problem
. Examine the following two programs:

Regardless of what is entered, each of these programs will always print 0. There are millions of other programs that will always perform the same operation: regardless of what is entered, the program will always output a 0 and halt. Such programs are called
zero programs
. It would be nice to be able to tell when a program is a zero program. The Zero Program Problem asks whether a given program is a zero program. That is, we would like a computer that accepts a program and outputs a Yes or No, depending on whether that program always outputs a 0. Alas, this too is unsolvable. It would take us too far afield to prove this result. Suffice it to say that this problem demands to know that the program halts for
every
input. That is a lot harder than the Halting Problem.

It is important to emphasize the difference between the Printing-42 Problem and the Zero Program Problem. In the Printing 42 Problem we ask if there is
at least one input
that will make the program output 42. In contrast, the Zero Program Problem asks if
every input
makes the program output a 0. Either way, both problems are undecidable.