Outer Limits of Reason (30 page)

Once we have shown that a particular problem is unsolvable, it is not hard to show that another problem is as well. The method used is
reducing one problem to another
, or a
reduction
.
⁵
Suppose there are two decision problems: Problem A and Problem B. Furthermore, assume that there is a method of transforming an instance of Problem A into an instance of Problem B such that an instance of Problem A that has a Yes answer will go to an instance of Problem B with the same answer, and similarly for No answers. (We do not impose the requirement as we did in the last chapter that the transformation be performed in a polynomial number of operations. Here we have no interest in how long such a transformation takes, just whether it can be done.) We might envision this transformation as in
figure 6.6
.

If such a transformation is possible, then

If Problem B is decidable, then Problem A is also decidable.

To decide Problem A, simply place an instance of Problem A through the transformer and see the results of the associated instance of Problem B. What if Problem A is undecidable? In that case, it must be the case that Problem B is also undecidable.

If Problem A is undecidable, then Problem B is also undecidable.

With such a transformation, we can say that Problem B is as hard as or harder than Problem A and write it as:

Problem A ≤ Problem B.

In the last section, I showed that the Halting Problem is undecidable. It is possible to describe transformations that show that

Halting Problem ≤ Printing 42 Problem

and

Halting Problem ≤ Zero Program Problem.

We conclude that these two problems are also undecidable.

Let's move on and show that we can reduce the Zero Program Problem to another problem. Consider the following two programs:

Although these programs look different and have different variables, it is easy to see that regardless of input, the same output is produced. Programs that perform the same task are called
equivalent programs
. It would be nice to be able to recognize when two programs are equivalent. The
Equivalent Program Problem
asks for a computer that accepts two programs and determines whether or not those two programs are equivalent. As you've probably guessed by now, the Equivalent Program Problem is unsolvable. This is actually easy to see by making the following reduction:

Zero Program Problem ≤ Equivalent Program Problem.

I will show that

Equivalent Program Problem is decidable ⇒ Zero Program Problem is decidable.

We showed before (but did not prove) that

Zero Program Problem is decidable ⇒ contradiction.

Putting these two together, we can piggyback on the previous result and show that the Equivalent Program Problem is undecidable.

Before we demonstrate this reduction, consider the short program

x=?

print 0

stop

This program always outputs 0, regardless of the input value. Let's call this program Z (for zero).

Assume (falsely) that you have a way of determining when two programs are equivalent. Suppose that you want to determine whether a program is the zero program.

Simply send the program and the program Z into the imagined equivalent-program decider as in
figure 6.7
. If the program is equivalent to Z—then the equivalent-program decider would tell us so. Using this procedure, we have created a zero-program decider. But we know that no such decider is possible. In conclusion, the assumption that there is an equivalent-program decider is untenable.

 

As you may have noticed, all the problems that we have so far shown to be undecidable have to do with determining different properties about programs. In other words, we have shown that there are no programs to determine certain properties about programs. This follows our theme that there are limitations when there is self-reference. In 1951, Henry Rice proved the granddaddy of all such theorems. In what has come to be known as Rice's theorem, it was shown that there is
no interesting property
about programs that can be determined by a program. This rather sophisticated result is proved by showing that for any interesting property P,

Halting Problem ≤ Property P Problem.

Since the Halting Problem is undecidable, the Property P Problem is also undecidable.

What about computers working in other areas like mathematics and physics? Are there other objective areas in which computers have limitations? In
section 9.3
we will see that there are many other problems in mathematics for which computers are not up to the task.

A reader might be unmoved by this chapter. After all, what was shown is that there are several easily stated problems that a computer cannot solve. One might be led to believe that there are a few strange pathological problems that computers cannot solve, in contrast to the many that they can. Let us think about this more carefully.

Consider the problem of determining whether a number belongs to a set. This problem is easy for the following sets:

• The set of odd numbers

• The set of even numbers

• The set of prime numbers

• The set of numbers that can be written as a sum of five square numbers

For every one of these sets, a program can be written that accepts a whole number as input and—depending on whether the input is in that set—outputs a yes or no answer.

However, there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not. For example,

• The set of numbers of programs that will output 42 for some input

• The set of numbers of programs that always output a 0

So, certain sets of whole numbers are decidable and others are not.

Now let us do some counting. We saw in
section 4.3
that there are uncountably infinite subsets of whole numbers. How many of those sets are decidable and undecidable. I mentioned in the beginning of
section 6.2
that for every program, there is a unique whole number that represents it. Hence, there are only a countably infinite number of programs. Since every decidable set needs a program to decide it, there are only a countably infinite number of decidable sets of whole numbers (see
figure 6.8
). All the other sets of whole numbers are undecidable, so there are an uncountably infinite number of undecidable sets and only a countably infinite number of sets that are decidable.
Chapter 4
showed the immense difference between countably and uncountably infinite.

At the beginning of this chapter, we asked what tasks a computer can perform and what tasks are beyond a computer's ability. We discovered that computers can only do a minuscule amount. In fact, the vast majority of tasks cannot be performed by computers and are beyond the boundaries of reason.

6.4  A Hierarchy of the Unknown

So far, this chapter has shown that many problems are beyond the capabilities of any computer to solve. The obvious question is what is beyond the computability barrier. Turing asked this question in his original paper on the Halting Problem, and he gave an ingenious answer that provides a structure for the unsolvable problems.

We cannot solve the Halting Problem. However, imagine for a moment that we are able to solve it. The process that solves the Halting Problem could not be an ordinary computer, for we have shown that no ordinary computer can do it. Rather, there would have to be something nonmechanical about it, something “spooky.” In ancient Greece (and in almost every other society), there were certain special people through whom the gods communicated. Such people were called
oracles
(from the Latin word “to talk”). On being asked a question, these oracles would fall into a trance and then supposedly give the answers from the gods.

Turing used the concept of an oracle to help classify unsolvable problems. Imagine that there was some type of oracle that could solve the Halting Problem. Use this “spooky” halt oracle in a computer. During a computation, let the computer ask the oracle questions about whether certain programs halt. We might envision this as in
figure 6.9
.

Input enters on the left and the computer performs some regular computations. Along the way, the regular computer could ask the halt oracle a Yes or No question and depending on the answer, perform different computations. The computer might ask the oracle several questions as the computation continues. This extra feature of being able to ask questions might be added to our programming language by adding commands such as

Such commands might happen several times in a program and might happen for different values of
z
. A computer with this power would not only be able to solve the Halting Problem but many other problems that we saw were not computable by regular computers.

With the halt oracle, even problems outside the realm of computer science can be solved. One of the hardest open problems about numbers is called the
Goldbach conjecture
. The problem is to prove or disprove a conjecture about numbers that dates back to the middle of the eighteenth century: