Charles Petzold

A couple readers have emailed me about an apparent contradiction on page 32 of my recent book The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine, and of course the problem area involves that nasty thing we call "infinity."

Mathematicians, metaphysicians, philosophers, and just plain folk have been wrestling with infinity for at least a couple thousand years. The big problem is that we can't make any analogies with the real world because infinity does not exist in the real world. The universe consists of a finite amount of mass/energy and occupies a finite (although expanding) space.

One of the wisest people to illuminate the subject of infinity was Aristotle, mostly in Chapters 4 though 8 of Book III of Physics, which I quote in Chapter 16 of The Annotated Turing. Aristotle differentiates an actual or completed infinity — which he contends does not exist — and a potential infinity, which is the type of infinity we associate with the natural numbers:

Generally speaking, the infinite exists by one thing being taken after another. What is taken is always finite on its own, but always succeeded by another part which is different from it. (trans. by Robin Waterfield, Oxford World Classics ed.)

And check out this brilliant statement:

Infinity turns out to be the opposite of what people say it is. It is not "that which has nothing beyond itself" that is infinite, but "that which always has something beyond itself."

Regardless of Aristotle's warnings, we still toss around words like "infinite" and "infinity" as if these concepts actually mean something. When we refer to an "infinite set" we do not mean that the set contains an infinite number of elements. What we really mean is that we are never finished constructing the set.

For example, consider the set of natural numbers:

{ 0, 1, 2, 3, ... }

The ellipsis suggests the process of constructing the set. Constructing this set is a never-ending process, a fact that is clearly demonstrated by a little computer program written in pseudo-code to generate the natural numbers:

num = 0
while (true)
{
     print num
     num = num + 1
}

I'm assuming that num can get as big as it needs to get, but obviously at some point we'll run out of available resources in the universe. At some point there will not be enough mass or energy in the universe to continue running the program.

Does it make sense to discuss the number of elements in this set of natural numbers (referred to as the set's cardinality)? Perhaps not, but if we feel we must, let's use the symbol Georg Cantor chose for this purpose. The cardinality of the set of natural numbers is

ℵ₀

called "aleph null." That's the first of Cantor's transfinite numbers.

Now let's construct another infinite set: the set of real numbers. Oh, too big? Let's make it easier: Let's construct the set of real numbers between 0 and 1. We can symbolize such as set similar to the way we symbolized the set of natural numbers — by writing down the first few elements followed by an ellipsis, like this:

{ 0,

and Yikes! What's the second element? We don't know, and this problem is serious: Not only will we never finish constructing the set of real numbers between 0 and 1; we can't even get started!

That's why we can't symbolize the set of real numbers like we symbolize the set of natural numbers. That's why there's a special symbol for the set of real numbers:

ℝ

The set of real numbers is a non-enumerable set. We can't list the elements of the set the way we can begin listing the elements of the set of natural numbers. We can't construct the set of real numbers, and for that reason, some mathematicians (like L.E.J. Brouwer) do not consider the set of real numbers to be a set at all! (And I tend to agree, in case you're curious about my personal philosophy of mathematics.)

If you think about this stuff long enough, you might suddenly bolt out of bed at 3:30 AM one morning and shout "Eureka! I know how to write a program that generates all the real numbers between 0 and 1!" It looks something like this:

denominator = 2
while (true)
{
     numerator = 1
     while (numerator < denominator)
     {
          print numerator / denominator
          numerator = numerator + 2
     }
     denominator = denominator * 2
}

The first time through the outer loop, the program prints 0.5. The second time, it prints 0.25 and 0.75. The third time, it prints 0.125, 0.375, 0.625, and 0.875. Et cetera.

It appears that this program is progressively filling up the real number continuum between 0 and 1, but it's not quite adequate. Every number printed by this program is a rational number. The program never never never prints a non-rational number. It will never print the square root of 2, for example, or π. This is not a way to generate the set of real numbers between 0 and 1. (And this is what I assert in the footnote on page 32 of The Annotated Turing.) Georg Cantor proved that there is no way to generate a set of real numbers, and this fact is essential to the proofs in Turing's paper.

The problematic part of page 32 isn't the footnote, but the main text the footnote hangs on. This is where I attempt to derive the cardinality of the set of real numbers. This derivation isn't really necessary to the rest of the book, but it's an interesting result nonetheless. Unfortunately, I make a statement that sounds as if a process of generating numbers conceptually similar to my second program does indeed generate all the real numbers between 0 and 1. This is only true if it's treated as a completed infinity, and that is not proper.

It makes more sense to view this problem from the other direction: Even if we can't actually construct the set of real numbers between 0 and 1, let's assume we have such a set anyway. Let's represent these numbers in binary. Each of these real numbers consists of a infinite string of digits, where the digits are 0 and 1. In each of these real numbers, the number of digits is ℵ₀. Because each of these ℵ₀ digits can be either 0 or 1, then the cardinality of the set of real numbers is:

2^ℵ₀

But the most important lesson is that the cardinality of the real numbers is way bigger than the cardinality of enumerable sets like the rational numbers. That's the essential knowledge for understanding Turing's paper.

	Wiley	Amazon US	Barnes & Noble
	Amazon Canada	Amazon UK	Amazon Deutsch
	Amazon Français	Amazon Japan	Blackwell
	“Petzold will be a stalwart companion to any reader who undertakes to read Turing's classic with his aid. The Annotated Turing will also be quite enjoyable to a more casual reader who chooses to dip into various parts of the text.” — Martin Davis in American Scientist