Carl Sagan began his epic television series Cosmos with his atheist credo:"The cosmos is all that is or ever was or ever will be."¹ He was wrong, and Kurt Gödel tells us so.

What Gödel tells us is that mathematics is incomplete. The story of this astonishing discovery starts in the eighteenth century, when the Scottish philosopher David Hume (1711–1776) challenged Galileo's idea that mathematics is the language in which God has written the laws of nature. Reacting to Hume, the German philosopher Immanuel Kant (1724–1804) proposed that even if we cannot be sure that mathematics works in the external world, we can know that it does work inside our minds by the laws of reason.

This idea set mathematicians the task of shoring up the foundations, of proving that all mathematics is securely founded on reason. Beginning by establishing that one plus one equals two, a later German philosopher, Gottlob Frege (1848–1925), worked out a system by which he thought he had demonstrated that arithmetic and algebra were reasonable and logically consistent. Frege's system was based on set theory and included the possibility of nesting sets, of having a set made up of other sets. It even allowed for the possibility of establishing a set of all sets that do not contain themselves. But when he was just getting ready to publish his magnum opus, The Foundations of Arithmetic, he got a letter from Bertrand Russell (1872–1970). Russell showed him that the set theory on which Frege had based his whole work was logically inconsistent.

The contradiction Russell demonstrated can be illustrated in a number of ways; one common one is the so-called barber's paradox. Let us say that in the town of Seville there is only one barber, Figaro, and this man shaves every man who does not shave himself. Does Figaro have a beard? If he does, then he must not shave himself. But if he doesn't shave himself, then the barber shaves him, and so he does not have a beard. But Figaro cannot both shave and not shave himself; hence the contradiction. The set of all sets that do not contain themselves is like the barber who shaves everyone who does not shave himself.

No wonder Frege was shaken when he got Russell's letter. "Arithmetic is tottering," he shuddered.²

The Incompleteness Theorem

Wondering what other branches of mathematics were tottering, many mathematicians began searching for previously unrecognized holes in their arguments. Their quest came to an end in 1930, when Kurt Gödel announced his earth-shattering "incompleteness theorem." This idea is one of the intellectual milestones of the twentieth century; thinkers rank it with the discoveries made by Newton, Einstein, and Heisenberg.

Gödel proved that no system of mathematics will be able to prove itself completely. The "incompleteness" consists in the fact that there will always be true mathematical statements that no system will be able prove. How Gödel proved this startling result is beyond the scope of this article, but that it is true is universally recognized.³

A way of demonstrating the incompleteness theorem involves a mathematical system, called S1, which consists of the set of odd and even whole numbers and the addition operation. A true mathematical statement that can be made about this set is that no three odd numbers within it will add up to twenty. But is impossible to prove the truth of this statement within the system, because we are limited to using only addition. If we go outside S1, however, it is easy to show that three odd numbers can never make twenty:

1.   Let X, Y, and Z be any whole numbers.

2.   Then (2X + 1), (2Y + 1), and (2Z+1) are odd numbers.

3.   Assume that (2X + 1) + (2Y + 1) + (2Z + 1) = 20.

4.   Then 2(X + Y + Z) + 3 = 20.

5.   Then 2(X + Y + Z) = 17.

6.   Then (X + Y + Z) = 8.5

7.   But by number theory, the set of whole numbers is closed under addition (one can never get fractions by adding whole numbers) so statement 6 is false.

8.   Therefore statement 3 must also be false, and no three odd whole numbers add up to twenty.

A skeptic might suggest that we modify system S1 to include number theory, fractions, and multiplication, and that we call the new system S2. So now, with system S2, we will be able to prove that no three odd numbers can combine to make twenty.

Okay. But there is at least one true mathematical statement we can make about S2 that is unprovable by that system: S2 cannot tell us the answer to the equation 4(1/1 – 1/3 + 1/5 – 1/7 + 1/9 . . .). (In case you do not recognize the series, the answer is pi.) Now, if we upgrade S2 to S3 by adding transcendental numbers, such as pi, we can prove the statement, but there will still be at least one true statement about S3 that is unprovable in S3. What Gödel proved "indisputably" is that this process can go on forever;⁴ hence, all mathematical systems are incomplete.

A Chess Demonstration

About ten years after Gödel's discovery, Alan Turing (1912–1954), regarded as the father of computer science and artificial intelligence, applied this thinking to computers. He realized that working a mathematical system is what a computer does. Thus, if all mathematical systems are incomplete, then the machines that implement those systems must also be incomplete as well. He showed that even a "Turing Machine," an imaginary computer of infinite speed and capacity that could run forever, could never prove that no three odd numbers add up to twenty, if it were programmed to use only odd and even numbers and addition (our S1). Since there is an infinite quantity of odd and even numbers, both positive and negative, the computer would never run out of integer triplets to evaluate. It would find that none of them equaled twenty, but it could never exhaust the infinite number of combinations, and so it could never prove the theorem.⁵

A real-life example of Turing's findings comes from the world of computer chess. Here is the situation (see below).

It's White's move. Should the pawn on B4 capture the rook?

Answer: White should not take the rook. Black has a strong material advantage with its bishop and two rooks, but White's pawns have formed a wall that cannot be breeched unless White itself creates an opening by taking Black's rook. Otherwise, there is no way for Black to move any of its pieces into a position to threaten White's king. Therefore, White should move its king around behind this impregnable defense until a fifty-move draw occurs.

This solution is obvious to any but a novice human player, but it escaped Deep Thought, the best chess-playing computer of its day (the 1980s). Despite being able to beat several grandmasters, the computer took the rook and suffered the inevitable loss.

The reason a human gets the draw and the computer loses in this situation is that the computer never "sees" the pawn barrier. It "sees" the individual pawns but never "realizes" that they together are invincible. It can follow algorithms and evaluate the possible moves, but it will never "understand" that White is safe as long as the barrier stands.⁶

A Qualitative Difference

Turing's adaptation of Gödel's finding prompted Oxford philosopher John Lucas (b.1929) to realize that if computers could never solve some problems whose solutions are obvious to humans, then there must be an essential difference between human minds and machines. He wrote, "Gödel's theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines."⁷ The difference between a human mind and a computer is not just quantitative but qualitative. It is not simply a matter of degree, but of kind. Minds and computers must therefore be different in their ontology, not just in their power. What Lucas means by "Mechanism" is also called "materialism," the belief that energy, matter, time, and space—the elements of the cosmos—are all there is.

Another Oxford thinker, mathematical physicist Roger Penrose (b.1931), builds on the thought of Gödel, Turing, and Lucas to argue not only that minds and machines are fundamentally different, but also that certain aspects of human thought can never be rivaled by computers. Computers perform "computations," but human minds engage in "conscious thinking."

One suggested way to tell if there is a difference is to run a "Turing test." There are various modes of the test, but a common one is to have a person, called a judge or evaluator, communicate via keyboard with two or more conversation partners who are hidden from view. One of those partners is a computer, and the idea is for the judge to try to structure the conversations in such a way as to be able to tell the real people from the computer. If the computer is able to "fool" the judge into thinking it is another person, that supposedly demonstrates that conscious thought can be reducible to computation, and that therefore, some form of materialism must be right.

Computers have, in fact, on several occasions been able to convince human evaluators that they, too, were human. Some people have concluded that, since people couldn't always tell whether their conversation partner was human or mechanical, it must be true that computers are able to "think" as well as people.

But a little more thought will show this to be a rash conclusion. One victory for the computer happened when it was programed to sprinkle a few typing mistakes into its answers. The judges, assuming that only a real person would make mistakes, were fooled. But this kind of subterfuge simply underscores how different people and computers are. The only reason the computer was able to "fool" the humans was that other human programmers, knowing how people think, were able to build misleading "mistakes" into the computer's output. This clever strategy was imagined by people, not thought up by the computers themselves. So, instead of proving that computers think, this result showed that only people create clever ideas.

More than Material

The creation of new ideas, or "outside the box" thinking, is exactly what Gödel's work envisioned. Computers are designed for systematic thinking, and Gödel showed that such systematic thinking can never produce complete results. The incompleteness theorem shows that the answer to the question, "Can there ever be a general method for solving all mathematical problems?" is "No." Because no mathematical system can prove all of its truths, and all computers depend on mathematical systems, the answer to the question, "Can a computer ever think exactly like a person" is also "No."

Thus, Constance Reid's book on higher mathematics concludes by saying, "Now it is established—with all the certainty of logical proof—that machines will never, even in theory, replace mathematicians."⁸ The reason computers will never replace mathematicians—or even ordinary people—is that people think in ways that computers can never duplicate.

If human minds cannot be reduced to computers made of silicon and steel, then they also cannot be reduced to computers made of protoplasm and protein. Our minds must therefore be more than our physical brains. A mind must have an immaterial component that is different from the physical matter of the brain. Since there is more to the human mind than the material of the physical brain, something immaterial must exist in the universe. The existence of the immaterial, the metaphysical, opens the door to spiritual reality and counteracts Sagan's stark materialism. Once we have opened the door to a more-than-material universe, can God be far behind? •

Notes
1. Carl Sagan, Cosmos (Random House, 1980), 4.
2. Morris Kline, Mathematics: The loss of certainty (Oxford University Press, 1980), 46, 74–76; Stephen M. Barr, Modern Physics and Ancient Faith (University of Notre Dame Press, 2003), 279–280; Roger Penrose, Shadows of the Mind: A search for the missing science of consciousness (Oxford University Press, 1994), 65.
3. Barr, 279–288.
4. Penrose, 65.
5. Barr, 211; Constance Reid, Introduction to Higher Mathematics for the General Reader (Thomas Y. Crowell, 1962), 174–178.
6. J. Seymour and David Norwood, "A Game for Life," New Scientist No. 1889 (Sept. 4, 1993), 23–26, cited in Penrose, 46–47. Of course the computer could be reprogramed to cope with pawn barriers, but because of Turing's insight there will be at least one ploy a person could imagine that the computer could not anticipate. The computer could then be reprogramed to accommodate that strategy, and the person could then find another new one, and so on until the computer had mastered all possible games of chess, a number estimated to be 10120. See "Shannon number" in Wikipedia.
7. John R. Lucas, "Minds, Machines, and Gödel," in K. M. Sayer and J. M. Crossen, eds., The Modeling of Mind (University of Notre Dame Press, 1963), 255.
8. Reid (note 5), 178.

Charles Edward White is Professor of Christian Thought & History at Spring Arbor University in Michigan. He has recently run his 50,000th mile since January 1, 1992.