COMPUTING SCIENCE
Identity Crisis
Brian Hayes
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.
» Post Comment