Labyrinths of Reason (16 page)

Everyone concurs that replacing a plank on a ship does not change its identity. It is still the same ship after the replacement. Replacing still another plank on the repaired ship should not make a difference either. At some point, perhaps, Theseus’ ship contained not a single plank of the original ship. Then surely the Athenians were deluding themselves in calling it Theseus’ ship. Had the ship
not
been preserved, and had the latter-day Athenians constructed a ship directly from those same nonoriginal planks, no one would dream of calling it anything but a good replica of Theseus’ ship.

Minor paradoxes of this type were popular with the ancient Greeks. A millet seed falling makes no sound, said Zeno. Then how can a bushelful of millet seeds make a sound when it falls, if it contains nothing but millet seeds? Of kindred spirit is the “paradox of the heap”: Whenever you remove a grain of sand from a heap of sand, you still have a heap of sand. Picture a heap of sand, and take away a single grain. Is there any possible way, based on your past experience, that removing a grain of sand could leave you with something other than a heap of sand? Of course not. Then start with a heap of sand and subtract the grains one by one. Eventually the heap dwindles to a single grain. It still must be a heap! Then remove the lone grain, leaving nothing. The nothing still must be a heap!

Sure, the way out is to set a minimum size for a heap. “A heap must have at least 1000 grains, so the rule should be: ‘Removing a grain of sand from a heap containing at least 1001 grains leaves a heap.’”
That
leaves a bad taste in your mouth even as you utter it. Doesn’t it miss the point? A word like “heap” is supposed to be vague.

A modern counterpart is Wang’s paradox (after Hao Wang). Wang claims that if a number
x
is small, then
x
+ 1 is also small. Does everyone agree that 0 is a small number? Okay; then 1 (0 + 1)
is small. And 2 (1 + 1) is small. And 3 (2 + 1) is small. And so on
… every
number is small, which is ludicrous.

A
sorites
(pronounced
suh-RYE-teez)
is a chain of linked syllogisms—the form of argument in which the predicate of each statement is the subject of the next. In other words, it’s this:

The premises of a sorites join up and lead to an obvious conclusion (“all ravens need oxygen”). Recognizing sorites (the plural is spelled the same way) is the key to many logic puzzles. The company-grapevine solution of the previous chapter is an elaborate sorites.

The sorites is named for the Greek word for heap, since it is the form of reasoning used (fallaciously) in the paradox of the heap:

Here the number of distinct logical steps may be millions.

Sorites paradoxes are possibly the simplest paradoxes of deduction. None qualifies as baffling. All derive from the way the slight inaccuracy of a premise can accumulate when the premise is applied over and over. What charm the sorites paradoxes have is that they use (abuse) a very common and important type of reasoning. Most of what we know or believe is through sorites.

One day you see a raven that neither you nor any ornithologist has ever seen before. Even so, you know a lot about that raven. You know (or have strong reason to believe) that it is warm-blooded, that it has bones underneath the feathers and skin, that it was hatched from an egg, that it needs water, oxygen, and food to survive,
etc., etc. You know all this neither through direct experience nor through being told it explicitly. Did you ever put a raven (much less
that
particular raven) in a room full of pure nitrogen? Did you ever read in a book the flat-out statement: “All ravens have bones”? You know these facts about the raven through sorites you construct as needed.

Science is founded on sorites. Through this type of deduction, anyone may generate a lot of information from a few remembered generalizations. Reliance on sorites permits an economy of experimentation. Quite possibly, no one has ever done an experiment to see if ravens need oxygen. Experiments
have
shown that diverse species of animals need oxygen, and had there been any reason to believe that ravens might be anaerobic creatures, that contingency would have been tested. As it is, we rely on the sorites above.

Scientists look for “all X’s are Y’s” generalizations because they lend themselves to quick deductions. The notion of a controlled experiment (where causes are isolated and identified with effects) presupposes that the important facts of the world are of this type. However, it does not follow that
all
truth can be formulated so simply. As we carve out a part of the truth, it is well to reflect that our slice of reality may not have the same shape as the whole.

Holmes’s complaint about the
UND
riddle in the previous chapter—that it is impractical to solve it “logically”—typifies the opposite type of logical process. There the step-by-step deduction of a sorites does not apply.

The
UND
riddle is apropos of a branch of mathematical logic known as
complexity theory
. Complexity theory studies how difficult problems are in an objective, abstract sense. It was founded on the experience of computer programmers, who discovered that some types of problems are much more difficult than others to solve by computer.

Complexity theory would be less useful if it applied only to computers. It applies no less to humans solving problems. A human must solve a problem by some method, and these methods (rather than hardware) are the concerns of complexity theory.

It may appear futile to look for an objective measure of how difficult a problem is. Most of the problems that arise in the real world are easy for some people and hard for others. Solution of many problems depends on making various mental connections between
the problem and certain other facts. You either make these connections or you don’t.

In a sense, riddles requiring a specific mental connection (such as Watson’s land-division problem) are the most difficult sort of logic puzzles, for it is all but impossible to say
how
to solve them. In another sense, they are the easiest. If and when you make the connection, there is nothing to it.

Complexity theory is mostly concerned with problems that are difficult even when a methodical means of solution exists. There are inherently difficult problems that cannot be solved by the human mind or by the computers of a science-fictional distant future. Yet these problems are solvable, not paradoxes or “trick questions” without a solution.

A central notion of complexity theory is the
algorithm
. An algorithm is an exact, “mechanical” procedure for doing something. It is a set of directions so complete that no insight, intuition, or imagination is required. Any computer program is an algorithm. So is a recipe for vegetable soup, the directions for assembling a bicycle, and the rules to many simple games. The rules of arithmetic taught in elementary school are an algorithm too. You know that when you add two numbers, no matter how large, the rules will always produce a correct solution. If you get a wrong answer, you know you must have applied the rules incorrectly. No one doubts the algorithm itself.

An algorithm must be exact. “If you get lost in the woods, keep your cool, use common sense, and just play it by ear” is advice, but not an algorithm. The Boy Scouts’ prescription—

If you get lost in the woods, walk downhill until you come to a stream. Then walk downstream; you’ll eventually come to a town.

—is an algorithm.

It’s tough to come up with effective algorithms. Unforeseen situations arise. It isn’t hard to think of cases where the Boy Scouts’ algorithm would fail. You could be in a desert basin where your walk downhill would lead to a dry lake bed, not a stream. In some remote parts of the world, there are streams that lead to a lake or the ocean without ever nearing human habitation. Worse yet, the instructions are silent on what to do if you find yourself on a plane so flat there is no obvious “downhill.” An ideal algorithm would work no matter what the circumstances.

We do not always use algorithms. There are cooks who follow recipes, and there are cooks who improvise so freely that they claim
to be unable to describe how a dish is made. Neither approach is right or wrong. Only the algorithmic approach lends itself to analysis, though.

Logic puzzles are a microcosm of the deductive reasoning we use to understand the world. Let’s see how a logic problem can be solved methodically. One of the oldest genres of logic puzzles concerns the inhabitants of a distant island, some always telling the truth and some always lying. Members of the Truth Teller tribe always tell the truth. The Liars always lie. You must understand that there’s no subtlety to the Liars: They don’t try to conceal a lie by sometimes telling the truth.
Every
statement they make is the exact opposite of the truth. No characteristic dress or other clues allow outsiders to tell to which tribe a person belongs. Perhaps the most repeated Liars and Truth Tellers problem was devised by Nelson Goodman of grue-bleen fame and published (uncredited) in a Boston
Post
puzzle feature in 1931. Slightly modified, it goes like this:

On the island of Liars and Truth Tellers, you meet three people named Alice, Ben, and Charlie.

You ask Alice whether she is a Liar or a Truth Teller. She answers in the local dialect, which you do not understand.

Then you ask Ben what Alice said. Ben, who speaks English, says, “She said she’s a Liar.” You then ask Ben about Charlie. “Charlie is a Liar too,” Ben insists.

Finally, Charlie adds, “Alice is a Truth Teller.”

Can you figure out to which tribes the three belong?

As in a syllogism, the basic logic of a Liars and Truth Tellers problem transcends the subject matter. Had the story began with the protagonist bailing out of a plane and landing on the island, it would make no difference. Had different names been chosen for the trio, it would make no difference beyond the fact that those names would appear in the solution. The essential problem is one of logical relationships, and these are all that really count.

You are interested in one thing only—determining the tribes of the three natives. When solving arithmetic problems, we often write something like x = 12 + 5y. There
x
and
y
are variables, unknown
quantities that may have any of a range of possible values. Solving the problem is a matter of deciding what specific values
x
and
y
must have. A logic problem can be treated the same way. There are three unknowns in this logic puzzle: whether Alice is a Truth Teller, whether Ben is a Truth Teller, and whether Charlie is a Truth Teller.

You could just as well say the unknowns are whether Alice, Ben, and Charlie are Liars. It makes no difference, but let’s give them the benefit of the doubt and work with the Truth Tellers formulation. Then we have three simple propositions that may be true or false:

These statements are as fundamental as any can be about the situation. They are atoms of the situation’s logic; no simpler statements exist. Since these sentences are not things we know for a fact, but only dummy statements that may be true or false, the role these sentences play is much like that of the variables of algebra. The “values” these sentences may have are, of course,
true
or
false
. In logician’s jargon, such statements are called
Boolean variables
, after British logician George Boole (1815–64).

The problem’s first question is directed to Alice. Since her reply is unintelligible to us, we can deduce nothing from it.

The first real information comes from Ben. He says that Alice said she’s a Liar. As you probably gather, you can’t take this at face value. Ben may be lying about what Alice said, and Alice may be lying about herself. Ben’s statement is possible only under certain tribe assignments—under certain suppositions about who’s a Liar and who’s a Truth Teller.

Let’s see. Alice and Ben can’t
both
be Truth Tellers. If they were, Alice would have honestly said she was a Truth Teller, and Ben would have honestly translated the statement. Since Ben said Alice said she is a Liar, we know both aren’t Truth Tellers.

Can Alice and Ben both be Liars? Yes. Alice, asked if she was a Liar, would say she was
not
Then knee-jerk liar Ben would negate that for a double negative. Ben would say that Alice had said she
was
a Liar. That’s just what he did say.

In fact, no one ever says, “I am a Liar.” A Truth Teller would not tell that lie, and a Liar would not tell that truth. When asked straight out, everyone insists that he is a Truth Teller (as in real life).

Ben’s statement that Alice said she was a Liar is a dead giveaway. No matter what Alice is, she must have said she is a Truth Teller. Ben is a Liar for saying otherwise.

(What if Alice didn’t understand the question at all? Then she probably would have said, “I don’t understand English,” or—if a Liar!—“I do understand English.” Ben would report one of these responses, the wrong one if he in turn is a Liar. Because the Liar tribe is so unimaginative, we know from Ben’s actual answer that Alice must have understood the question and responded with a statement about her tribe.)