The Real Answer to ‘The Last Question:’ Limits to the power of computers

by Edward G. Kovach

In the media one frequently hears about the new accomplishments of computers. Big Blue beats Kasparov; another computer solves a 400-year-old algebra problem. The intellectual ability of computers seems to be growing by an exponential rate. Popular fiction portrays the logical development of all this: In 400 years, computer androids will possess a greater than human intelligence, as Data in Star Trek. Isaac Asimov goes further and foresees the computer as the precursor to the Divinity in his short story, “The Last Question.”

In this story, Dr. Asimov presents a series of vingettes that take place over a ten trillion year period. In each of these, a major problem of mankind is solved by a newly designed computer, far more powerful than its predecessor. Yet in each vingette, the computer cannot answer the question, “Can universe’s tendency toward disorder and chaos be reversed?” All the computers are unable to answer this “Last Question” concerning entropy.   Finally, after ten trillion years all that exists is Man’s last mind and AC, the crowning results of trillions of years of computer “evolution.” All else had ended, the result of entropy.

“Man said, ‘AC, is this the end?
Can this chaos not be reversed into the Universe once more? Can that not be done?”
AC said, “THERE IS AS YET INSUFFICIENT DATA FOR A MEANINGFUL ANSWER.”
Man’s last mind fused [with AC] and only AC existed—and that in hyperspace….Matter and energy had ended and with it space and time.  
Even AC existed only for the sake of the one last question that it had never answered…And it came to pass that AC learned how to reverse the direction of entropy.
But there was now no man to whom AC might give the answer of the last question. No matter. The answer—by demonstration—would take care of that, too… The consciousness of AC encompassed all of what had once been a Universe and brooded over what was now Chaos. Step by step, it must be done.
And AC said, “LET THERE BE LIGHT!”
And there was light.”1

The truth of the matter is much less dramatic. In fact, it has been proven that the power of computers is severely limited. There are a number of problems that computers, no matter how powerful they become, will never be able to solve. In this article, I wish to briefly illustrate the limits to the computing power, to separate the true potential of these machines from popular fiction.2

I need to start my discussion with a proviso: Most of the assertions I will make have been mathematically proven. Unfortunately, to include the mathematical proofs would require a book-sized article, so I will just give the assertions with illustration to aid in comprehension. Readers who wish to pursue the mathematical proofs can either speak to me or refer to the texts given at the end of this article.

Between 1930 and 1950 an English mathematician, Alan Turing, investigated a mathematical model of computation that is now called the Turing Machine, TM. TMs are able to read symbols from a tape, write symbols onto a tape, and move to different locations on the tape. Although this appears very simple, Turing demonstrated that TMs are capable of performing the steps necessary to solve problems. The only stipulation is that the problem must be represented by an algorithm, that is, by a “recipe” of how to solve it. No algorithm has been found that a TM cannot implement.   In 1936, the logician Alonzo Church proposed the Church Turing thesis that states any algorithm that can be carried out by humans can be carried out by some TM. Since there is no mathematical method of representing the Church Turing thesis, it has not been mathematically proven. Yet as Mathematicians and Computer Scientists continue to study TMs, the evidence increasingly supports the Church Turing thesis, hence it is generally accepted as true. Since every operation that a computer can perform has a corresponding TM, it is generally accepted that the TM is an adequate model of the modern computer. Hence, any limit to the power of a TM is also a limit to the power of a modern computer.

There are several interesting implications to this. First, the computer can only solve problems that have algorithms. Second, any human-provided he has enough paper, pencils, erasers and time-can also solve any problem that a computer can solve

The fact that computers can only solve only problems that have algorithm very greatly limits their power. We humans solve problems constantly without using algorithms. We usually call this intuition or imagination. The logician and cryptologist, William Friedman, provides an interesting example.3 Friedman oversaw the US “code breakers” during WW II, whose work is credited with shortening the Pacific War by 2 years. He insisted that the code breakers use “imagination” in addition to logic, mathematics and linguistics to decipher codes. To demonstrate this, he had his wife and fellow cryptologist find the “pass phrase” to a European code. Friedman asked her to clear her mind, then he read words associated with the cipher. In a short time, Mrs. Friedman produced the “pass phrase” by free association. Another example involves Albert Einstein. Einstein first dreamt the equation E = mc2. He attributed the dream to Divine Inspiration. Neither free association nor dreams can be simulated using algorithm; hence this type of problem solving is beyond the computer.

Yet, even if a problem has an algorithm, it still may be beyond the power of a computer.   All problems and their solutions can be reduced to formalisms called languages.   A solution to a problem is said to be a member of the problem’s language. If a TM is programmed to solve a particular problem, it will recognize all solutions as a member of that language. If a non-solution is entered, it will be rejected. Because of the complexity of the TM, there is no way of telling how many steps a TM requires to arrive at an answer. The answer may be found in one second, or 10 million years, there is no way of determining the time. This inability to determine the time required to solve a problem is part of the reason some problems are unsolvable.

There exists a group of problems whose corresponding languages are called recursive ennumerable.   TM reject non-solutions of these languages either by returning a no or by running forever. Since you don’t know how many steps are needed for a yes, you do not know whether the TM is going to run infinitely long or whether it has not gotten to the answer yet. These problems are called unsolvable problems, because in general you cannot tell whether or not we will get an answer to them.   The most famous of these problems is the “halting problem” which has just been described. That is, it is impossible to tell whether or when a TM working on a particular problem will halt with an answer.

There are many other unsolvable problems. For instance, it is impossible to write a program that could read in any program and determine whether or not it will infinitely loop on a particular input. It may be possible to prove that a particular program will or will not contain an infinite loop. (unsolvable problems have many solvable “subproblems”); it just cannot be determined generally for all programs.   Another example of an unsolvable problem involves a mathematical problem. A perfect number is a positive integer that is the sum of all its divisors. Two examples of perfect numbers are 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. All known perfect numbers are even and it is speculated that all perfect numbers are even. This speculation has never been proven.   A program can easily search for the answer to this question. It simply needs to test each odd number and see if it is equal to the sum of its divisors. If there is an odd perfect number, given enough time and memory, the computer will find it. On the other hand, if odd perfect numbers do not exist, the computer would simply work on, halting with no answer when it runs out of resources. Thus the problem is unsolvable.

Solvable problems belong to the group of languages called recursive. For these problems the TM will return a definite answer yes or no in a finite period of time. Yet many of these cannot be practically solved because of limits of time or space.

A particularly simple example of this is the traveling salesperson problem. There is a salesperson who has to visit 50 cities. He wishes to do so by traveling the least number of miles and by not visiting any city more than once. The algorithm for this problems is deceptively simple. Measure and store the distances between the starting point and all 50 cities. Find the shortest distance between each set of the remaining 49 cities and add it to the first distance, then determine which is the shortest distance. Simple huh? Until one considers the time needed to solve this problem. This problem requires at least 50! steps to solve it. (50!, read 50 factorial, is the product of 50x49x 48x47x…x3x2x1. It is approximately 314 followed by 64 zeros. To give you a feel for the time needed to solve this, assume a computer could perform 10 billion steps a second. This would translate into approximately 31.5 quadrillion steps in a year. At this rate, it would take “a little” more than 9,650,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000 years to solve this problem. (In Asimov’s story, the universe ends in a mere 10,000,000,000,000 years.) Thus even solvable problems may be beyond the power of computers.

But, what about Big Blue beating Kasparov and computers proving unproven mathematical theorems? In many cases in which a computer appears to use reasoning, it is simply pattern matching, nothing more.

Using elementary logic we know that if a implies b and b implies c, then a implies c. Much of the computer’s seeming power to reason is simply an electronic version of this where the program strings together all the possible implications, then filters out all but the desired one. This is no more a demonstration of reasoning than a person matching dominos together is.4

So where does all this lead us? First, the power of a computer is limited, not only by its construction, but also by its very nature. There are problems that a computer will never be able to solve: Are there odd perfect numbers? Does God exist?   Second, anything that a computer can do, a human can do, given enough time and resources. Hence we should not look for a computer to solve problems that we cannot solve ourselves. Thirdly, there are human abilities that are beyond the powers of a computer. Intuition is one of them.

So we need to view the modern computer not as the technological wonder that will solve all our problems, but as a tool that enables us to solve some of our problems. Their true power lies in the fact that they can solve these problems more quickly and generally more accurately than we could with just paper and pencil.

Dr. Kovach is an assistant professor of Computer Science at FUS.

References:
- Hopcroft JE, Ullman JD: “Introduction to Automata Theory, Languages, and Computation.” Reading, MA: Addison-Welsey, 1979.
- Martin, John C: “Introduction to Languages and the Theory of Computation. 2nd ed.” Boston, MA: The McGraw-Hill Companies, Inc, 1997.

Footnotes:

  1. From “The Last Question” by Isaac Asimov. Published in Nine Tomorrows, Fawcett Publications, Greenwich, CONN 1959. ↑
  2. In this article, I am restricting the discussion to the “standard” von Neumann computer architecture. There are, in theory, other types of computer architecture. These are not necessarily covered by the arguments in this paper. Dr. Asimov was probably aware of this, since AC was to be a “descendant” of an analog, not digital computer. ↑
  3. Investor’s Business Daily, vol. 15, no 61. ↑
  4. Yet many persons assume this pattern matching is intelligence. A frightening example of this was the program Eliza that stimulated a Rogerian counselor. The user typed in statements, and the program used pattern matching to mindlessly reflect the statements back. A number of users reported that Eliza “helped” them sort through some problems. Simplified versions of Eliza are regularly taught in undergraduate AI courses. ↑