Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG

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.

Figure 1. Peano's algorithmClick to Enlarge Image

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.


comments powered by Disqus
 

EMAIL TO A FRIEND :

Of Possible Interest

Computing Science: Belles lettres Meets Big Data

Technologue: Quantum Randomness

Technologue: The Quest for Randomness

Subscribe to American Scientist