Labyrinths of Reason (4 page)

The sense of paradox is sharper in another famous thought experiment, the “twin paradox.” The theory of relativity claims that time passes at different rates according to the motion of the observer. Let one of a set of identical twins blast off in a rocket, travel at near the speed of light to Sirius, and return to Earth. According to relativity, he will find he is years younger than his twin brother. He will be younger by his calendar watch, by the number of wrinkles and gray hairs, by his subjective impression of how much time has elapsed, and by any other physically meaningful definition of time we know of.

When first formulated, the twin paradox was so contrary to experience that many (including French philosopher Henri Bergson) cited it as proof that relativity must be wrong. Nothing in everyday life leads us to believe that time is relative. A pair of twins are the same age from the cradle to the grave.

Today, the twin paradox is an accepted fact. It has been tested in numerous experiments—not with twins, but with extremely accurate clocks. In a 1972 experiment designed by physicist Joseph Hafele, cesium clocks transported around the globe on commercial jetliners established that the human passengers returned home a minuscule but measurable split second younger than everyone else. No physicist doubts that if an astronaut did travel at near the speed
of light, he would return younger than a stay-at-home originally the same age.

The paradox lies in our mistaken assumptions about the way the world works rather than in the logic of the situation. The unspoken premise of the twin paradox is that time is universal. The twin paradox demonstrates that this premise is untenable: Common sense is wrong. You might not think there is an animal that has fur and lays eggs, but here’s the platypus, a living paradox—sort of. There is, of course, no logical necessity that a fur-bearing animal not lay eggs, nor one that time not depend on the motion of the observer.

This, then, is the second type of paradox, the “common sense is wrong” type. In these paradoxes, the contradiction, while surprising, can be resolved. It is fairly obvious which of the original assumptions must be discarded, and however painful it may be to relinquish that assumption, once it is thrown out, the contradiction vanishes.

There are stronger paradoxes yet. Neither the fallacy nor the “common sense is wrong” variety has the tantalizing quality of the best paradoxes. These most paradoxical of paradoxes defy resolution.

A very simple example of genuine paradox is the “liar paradox.” Devised by Eubulides, a Greek philosopher of the fourth century B.C., the paradox is often wrongly attributed to Epimenides, who is merely the fictionalized speaker (as is Socrates in Plato’s dialogues). Epimenides of Crete allegedly said, “All Cretans are liars.” To convert this into a full paradox, cheat a bit and playfully define a liar as someone whose every utterance is false. Then Epimenides would have been saying in essence, “I am lying,” or “This sentence is false.”

Take the latter version. Is the sentence true or false? Suppose that “This sentence is false” is true. Then the sentence is false because it’s a true sentence, and that’s what it asserts!

All right, then, it must be false. But if “This sentence is false” is false, then it must be true. This gives us two reductio ad absurdum arguments. If it’s true it’s false, so it can’t be true, and if it’s false it’s true, so it can’t be false. The paradox is intrinsic and indelible.

With this third type of paradox, it is not at all clear which premise should be (or
can
be) discarded. These paradoxes remain open questions. The paradoxes to be discussed in this book are at least of the second type, and mostly of the third. Be warned that few have a universally accepted solution.

The best paradoxes raise questions about what kinds of contradictions can occur—what species of impossibilities are possible. Argentine writer Jorge Luis Borges (1899–1986), whose work appeals to all lovers of paradox, explored many such questions in his short stories. In “Tlön, Uqbar, Orbis Tertius,” he describes an encyclopedia, supposedly from another world, created as an elaborate hoax by a group of scholars. Borges’s scholars even imagine the paradoxes of their fictitious world; so alien is the thinking of “Tlön” that their paradoxes are commonplaces to us. The greatest paradox of Tlön is that of the “nine copper coins”:

To the Tlön way of thinking, the “nine copper coins” has the quality of true paradoxes, that it is never fully explained away. It is interesting to wonder if our paradoxes would seem as banal to the inhabitants of another world. Are paradoxes “all in our heads” or are they built into the universal structure of logic?

This book deals with paradoxes of knowledge; paradoxes that illuminate how we know things. At first sight, the idea of knowing what the universe is like is absurd. Penfield’s experiments demonstrated that memories occupy
engrams
, specific physical sites in the
brain. To know about Chief Crazy Horse or frost or Tasmania is to have some part of your brain that represents Chief Crazy Horse, frost, or Tasmania. These brain sites may wander and interpenetrate, and the whole story about how memories are stored and recalled is probably a lot more complicated than we can imagine today. That granted, engrams are not infinitely small. Your mental representation of Chief Crazy Horse occupies a part of your brain’s storage capacity that cannot be occupied simultaneously by anything else.

You might naïvely picture the brain as containing scale models of things in the outside world. It is evident that these models must leave out much detail. The very fact that the universe is so much larger than your head makes universal knowledge unattainable. There is no way a human brain can contain representations of everything in the world.

That our brains work as well as they do indicates that they are selective in what they retain. The primary tool for condensing the complexity of the world is generalization. Our brains do this at many levels. Science is a conscious and collective way of simplifying through generalization. It is a means of packing the great, vast universe into our tiny brains.

Science is a mnemonic device. Rather than remembering what has happened to every apple released from its support, we remember gravity. It is a map of the external world. Like any map, it omits detail. Small towns, trees, houses, and rocks are left out of road maps to make room for highways, coastlines, national boundaries, and other features judged more significant to the map’s users. Comparable judgments face the scientist.

Science must be more than a desultory catalogue of information. It must embrace not only the collecting of information but the understanding of it. What is understanding? Surprisingly, this philosophical question can be given a rather exact, if preliminary, answer.

Often it is easier to draw a boundary around an unknown than to describe it. Thomas Jefferson did not know what was in the Louisiana Territory, only its boundaries. It is convenient to take this approach in describing what it means to understand a body of information.

At a bare minimum
, understanding entails being able to detect an
internal contradiction: a paradox. If you cannot even tell whether a set of statements are self-contradictory, then you don’t really understand the statements; you haven’t thought them through. Think of the querulous schoolteacher who slips a contradiction into the lecture to see if a daydreaming student will agree with it:

“Isn’t that right, Miriam?”
“Uh … yes, ma’am.”
“I see. Someone obviously hasn’t been listening to a word I’ve been saying.”

Spotting contradiction is not all there is to understanding. There is probably much more. But it is certainly a prerequisite. By exposing a contradiction in a set of assumptions, the author of a paradox shows that we don’t understand as much as we think we do.

In logic, the abstract problem of detecting paradox is called SATISFIABILITY. (This and related logic problems are usually printed in capital letters.) Given a set of premises, SATISFIABILITY asks, “Do these statements necessarily contradict?” Another way of phrasing it is, “Is there any possible world in which these premises can all be true?”

SATISFIABILITY deals in logical abstractions, not necessarily the truths of the real world. Consider these two premises:

One’s natural reaction is that both statements are wrong. But something can be wrong without being a paradox. You can at least imagine a world in which both these statements are true. Logicians say a set of statements are
satisfiable
when they are true in some possible world—even if not our own.

The situation is different here:

In no possible world can all three statements be simultaneously true (assuming that colors like purple and green are mutually exclusive). There is a paradox; the statements are said to be unsatisfiable.

Notice that no single statement is to blame for the contradiction. You could strike out any one statement and have a possible state of affairs. The paradox lies in the way the three statements intertwine.

This oddity turns out to be incredibly significant. Because paradox
cannot be localized, SATISFIABILITY is extremely difficult in general. It is in fact notoriously hard, a paragon of difficulty. It is difficult in the sense that as the number of premises is increased, the time required to check them for possible contradiction increases at a staggering rate. The increase is so great that many SATISFIABILITY problems with a hundred or more premises may be for all practical purposes insoluble. Even if these problems were turned over to the fastest computer in existence, they would take practically forever to solve.

We can use paradoxes as a metaphor, a way of marking off the limits of understanding. Science tries to find simple generalizations that account for myriad facts. Whenever we find ourselves unable even to detect blatant contradictions in a body of knowledge or belief, then we do not understand it. The difficulty of SATISFIABILITY is a rough measure of how difficult it is to “compress” empirical information with generalizations. SATISFIABILITY sets a loose limit on the difficulty of acquiring information and deducing conclusions from it.

The early 1970s saw a surprising discovery in mathematical logic. Two seminal papers by computer scientists Stephen Cook (1971) and Richard Karp (1972) revealed that many types of abstract logic problems are really the
same
problem in disguise. They are all equivalent to SATISFIABILITY, the problem of recognizing paradox.

The class of problems equivalent to SATISFIABILITY is called “NP-complete” (don’t worry about the name for now). One surprising thing about the NP-complete problems is how (apparently) dissimilar they are. Karp’s paper listed twenty-one NP-complete problems, including the “traveling-salesman” problem (an old mathematical riddle) and the “Hamiltonian Circuit” problem, based on a puzzle novelty that was a faddish nineteenth-century predecessor of Rubik’s cube. Over the years, the list of problems known to be NP-complete has grown enormously.

Problems of finding your way through a labyrinth, of decoding ciphers, and of constructing crossword puzzles are NP-complete. The NP-complete problems include generalized versions of many classic logic puzzles or brainteasers: the sort of recreational logic most associated with Martin Gardner and Raymond Smullyan in recent years, and Sam Lloyd, Lewis Carroll, Henry Ernest
Dudeney, and many others, known and anonymous, before them. That such diverse problems can be essentially the same was wildly unexpected. It is not too much of a hyperbole to compare Cook and Karp’s discoveries to the discovery that everything is made of atoms. Much of the intellectual difficulty of the world, both profound and frivolous, is made of the same stuff. NP-completeness is a cosmic riddle; a paradigm of the inscrutability of a universe of exponentially vast possibilities to a finite mind.

When logicians say that all NP-complete problems are, in effect, the same problem, they mean that an efficient general solution to
any
NP-complete problem could be transformed in such a way as to solve all the other problems. If ever anyone solved one NP-complete problem, then
all
the NP-complete problems would melt away like cotton candy in a summer rain.

It is as if you discovered that all the famed treasures of the world can be unlocked with the same key—
if
that key exists. Is there an efficient solution to any/all NP-complete problems? This is one of the deepest unresolved questions in mathematical logic today.