COMPUTING SCIENCE

# Identity Crisis

Equality of Beans

Just what *does* it mean for two numbers to be equal? Note
that this is a question about numbers, not numerals, which are
representations of numbers. The numeral 5 in base 10 and the numeral
11 in base 4 and the Roman numeral V all represent the same number;
they are all equal. Numbers can even be represented by piles of
beans, which form a unary, or base-1, notation.

For small enough hills of beans, most people can judge equality at a glance, but computers are no good at glancing. If you want to teach a computer to test bean piles for equality, you'll need an algorithm. There's a very simple one that works on piles of any finite size. The only mathematical skill the computer needs is the ability to count from 0 up to 1: It has to be able to recognize an empty pile and to choose a single bean from a nonempty pile. Then it can determine the equality of two piles by following these rules: First, check the piles to see if they are empty. If both piles are empty, they are obviously equal. If one pile is empty and the other isn't, the piles are unequal. If neither pile is empty, remove one bean from each pile and repeat the whole procedure. Since the piles are finite, at least one of them must eventually be emptied, and so the algorithm will always terminate.

This method is loosely based on a scheme devised a century ago by
the Italian mathematician Giuseppe Peano, who formulated a set of
axioms for arithmetic in the natural numbers (also known as the
counting numbers, or the nonnegative integers). Peano's method can
be generalized, though awkwardly, to the set of all integers,
including negative whole numbers. But the algorithm doesn't work for
the real numbers (those that make up the continuum of the real
number line). Indeed, the very concept of equality among the reals
is perplexing. For the rational numbers, which form a subset of the
reals, equality is no problem. Since every rational can be
represented as a fraction reduced to lowest terms, two rationals are
equal if their numerators are equal and their denominators are
equal. The trouble is, almost all the reals are *irrational*;
if you choose a point at random along the real number line, the
probability of landing on a rational is zero. And no finite process
can show that two arbitrary irrational numbers are equal.

Irrational numbers are usually represented as nonrepeating decimals, such as the familiar 3.14159 for the first few digits of π. Because the pattern of digits never repeats, matching up two irrational numbers digit by digit will never prove them equal; there are always more digits yet to be checked.

Writing numbers in decimal form has another pitfall as well: A single real number can have multiple decimal expansions, which are mathematically equivalent but don't look at all alike. The problem comes up even with rational numbers. A case in point is the pair of values 0.999... and 1.000... (where the three dots signify an infinitely repeated pattern of digits). These numerals have not one digit in common, and yet they denote exactly the same value; there is not the least smidgen of difference between them. (If you doubt this, consider that 0.333... + 0.333... + 0.333... = 0.999..., but 1/3 + 1/3 + 1/3 = 1.) Thus some real numbers look alike but can't be proved equal, while others are equal but look very different.**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Technologue**: The Quest for Randomness

**Perspective**: Searching for Great Adventures

**Computing Science**: New Dilemmas for the Prisoner