Outer Limits of Reason (31 page)

Every positive even number greater than 2 is a sum of two primes.

This statement is easily shown to be true for small numbers:

• 4 = 2 + 2

• 18 = 5 + 13

• 220 = 23 + 197

• 8206 = 59 + 8147.

In fact, mathematicians have shown that this conjecture is true for all even numbers less than 10
¹⁷
. However, that is not good enough. The conjecture says that it is true for
every
even number. After more than 250 years, this easy-to-state problem still taunts mathematicians.

Determining whether this conjecture is true would be very easy if we had access to the halt oracle. Consider the following program:

This simple program searches for a counterexample to the Goldbach conjecture. If no such counterexample exists, the program will go on forever. In contrast, if a counterexample does exist, then the program will halt. So, all you have to do is ask the halt oracle if this program will halt. Notice that saying there is no counterexample to the Goldbach conjecture will not earn you much fame. The problem is to
prove
that the conjecture is true.

There are many other problems in mathematics that could be solved if we had access to the mythical halt oracle. We will meet some of these problems in
section 9.3
.
⁶

There are other possible oracles besides the halt oracle. For any oracle X, all programs that can ask questions of that oracle will be called
X oracle programs
. In particular, programs that pose questions to the halt oracle will be called
halt oracle programs
. Many unsolvable problems would be solved with halt oracle programs. The question then arises: Can halt oracle programs solve all unsolvable problems? Turing showed that they cannot. Just as we demonstrated that there is a unique number for every regular program, so too is there a unique number for every halt oracle program. With these numbers in hand, we can ask whether a particular halt-oracle program with a given number will halt. This decision problem is called the
Halting Problem for Halt Oracle Programs
. Using arguments similar to those in
section 6.2
, it can be shown that the Halting Problem for halt oracle programs cannot be solved by any halt oracle program. This problem is another unsolvable problem, but it is not computable even with access to the halt oracle.

Turing wasn't finished. Imagine that we had an oracle that can solve the Halting Problem for halt oracle programs. Call such an oracle the
halt′ oracle.
With this oracle we can solve many more problems. Any program that employs this oracle is called a
halt oracle program
. And, once again, we may pose the question of whether all problems can be solved by halt´ oracle programs. As you probably guessed by now, the answer is no. It can be shown that no halt´ oracle program can solve the Halting Problem for halt´ oracle programs. For that, one would need a
halt˝ oracle
. And this goes on and on . . .

A hierarchy of unsolvable problems has been described. One can say that certain unsolvable problems are harder than others and certain problems are easier than others. Computer scientists have been able to characterize certain problems as halt´-computable problems, but not as halt
˝
-computable problems. They have described different problems in each part of the hierarchy. We have been concerned with the limits of reason and here we have some clear structure of what is beyond the limits of reason.

Figure 5.18
in chapter 5 can now be extended to include problems that are not computable to form
figure 6.10
.

The set of easy, hard, and harder problems can all be considered one set that we called “computable problems.” This section shows that the set of noncomputable problems has a hierarchical structure. Putting all this together gives us
figure 6.11
.

At the end of
section 5.3
of the last chapter, we introduced the
P
=?
NP
question and showed why it is important and exciting. It would be interesting to know whether this question is solvable if we take oracles into account.

First some definitions.
P
was defined as the set of problems that can be solved by a regular computer in a polynomial number of operations. Let us generalize. Consider any oracle X. Define
P
^X
to be the set of X-oracle problems that can be solved in a polynomial number of operations.
NP
was defined as the set of all problems that can be solved by a regular computer in at most an exponential or factorial number of operations. Let
NP
^X
denote the set of X oracle problems that can be solved in at most exponential or factorial number of operations.

In 1975, three researchers named T. P. Baker, J. Gill, and Robert Solovay published a paper containing two very interesting results. They described two oracles, A and B, such that

P
^A
=
NP
^A

and

P
^B
≠
NP
^B
.

The first result shows that there is an oracle, A, where hard problems can be done in few operations. The second result states that there is an oracle, B, where there is a hard problem that can be shown to require a large number of operations. So the long-standing
P =? NP
question is solved if you assume different oracles.

Results along these lines continued. In 1976, Juris Hartmanis and John E. Hopcroft showed that an oracle C exists such that the question of whether

P
^C
=
NP
^C
or
P
^C
≠
NP
^C

cannot be resolved by the usual axioms of mathematics.
⁷
It is not very clear what relevance these theorems have to the original
P
=?
NP
question, but it remains an interesting topic.

6.5  Minds, Brains, and Computers

This chapter is concerned with what is beyond the ability of computers. We might ask whether the human mind can perform tasks that computers cannot perform. Is the human mind more than just a machine? Is it limited like a computer?

We showed that a computer cannot solve the Halting Problem. Can a human being solve it? After all, isn't the human brain a type of computer? For small programs human beings usually can solve the Halting Problem. That is, we can look the program over and see if it will halt. But what about large programs? The Halting Problem is about
any
program. There are thousands of very smart people who work at Microsoft and many of them look over their large programs but fail to see that there are times when the programs will go into infinite loops. Does that mean that human beings cannot find all such infinite loops? What about other computing problems?

These questions are related to the question of the relationship between the human brain and the human mind. The human brain is a highly complex physical machine. In fact, it is probably the most complex physical machine in the entire universe. There is no doubt that mind is somehow related to brain. Whatever happens to the brain definitely affects what happens to the mind. If you doubt that, try to read this chapter after taking a few shots of tequila! Nevertheless, the relationship between the two is not clear. Our mind and our thoughts seem to be something more. We feel like we are more than just a bunch of firing brain synapses. We imagine ourselves to be far more than physical machines following the laws of physics. Human beings feel like they are conscious beings with free will and independence of thought. But are we really free? Do we really have control over ourselves? Ambrose Bierce defines the brain as “an apparatus with which we think we think.”
⁸
Do we really think freely, or are our minds trained to think that they are free of the brain?

If a human mind is simply a physical brain following physical processes, then a human mind will also not be able to solve any of the problems presented here. In contrast, if the mind is more than physical brain, then perhaps the mind can perform more. Which is it?

Kurt Gödel felt that the human mind is more than just a machine. He felt that there are certain statements that cannot be proved by any mechanical system but that these results are nevertheless known/understood by human beings. Gödel said that this shows that human minds are more than just finite machines. If our brains are not finite machines, what are they?

Sir Roger Penrose, a famous professor of mathematics, offers similar arguments that the brain is more than just a machine. Penrose goes on to speculate that perhaps the brain uses the mysterious concept of quantum gravity to explain the seeming ability of humans to perform tasks that machines cannot. He claims that a computer that uses quantum gravity might be able to solve the Halting Problem. Penrose also says that this might help explain consciousness.

Douglas R. Hofstadter, an American researcher, speculates that the human mind has consciousness because it has the capability of self-reference. Since we can think about ourselves and think about ourselves thinking about ourselves, etc., we are capable of feeling that we are an “I.” Contrast that with what we have learned in this chapter. This chapter tries to show that the computer's ability to perform self-reference is the cause of its limitations. Can we say that self-reference in computers brings limitations while in humans it causes consciousness? Perhaps. Do human beings really have self-reference? Do we really know what is going on inside our minds?
⁹

Many great minds have thought about these questions without reaching any clear consensus.

One can turn around the questions posed above. Rather than asking if the human mind is more than a machine, ask if we can ever get a machine to act more like the human mind. An entire field of computer science, namely
artificial intelligence
, is dedicated to this question. The answer, in a way, depends on the answer to the previous questions. If a human mind is something more than a machine, there is no way to get a machine to really have a mind. On the other hand, if the mind is simply a fancy machine and it only seems like it is doing more than a machine, then we can expect that with enough time and ingenuity, we can get a computer to also seem like it is doing more than a machine. Is artificial intelligence possible? Even if we get a computer to act just like a human being, does that mean the computer will have consciousness?

The problem with trying to achieve artificial intelligence is recognizing whether this achievement has been made. One would need a legitimate definition of intelligence. Computers currently do amazing things that they could not do thirty years ago. Back then, it was largely believed that a computer would never win a match with a world chess master. In May 1997, this prediction was shown to be false. Deep Blue, a supercomputer developed by IBM, won a six-game chess match against the world champion Garry Kasparov. So computers can beat human beings at chess. And yet at present, no robot can beat a human at tennis. What if we looked thirty years into the future? There is no doubt that we would be shocked if we were given a chance to see what computers can do then. As time goes on, and computers gain more skills, we are less impressed with them and say that they are “just following a program.” We always want more from our machines. “If only it could do this,” then they would have “real intelligence.” It seems that the boundary between what is “just following a program” and what is “real intelligence” moves as time goes on. Perhaps we have already achieved artificial intelligence.