PETZOLD BOOK BLOG

Charles Petzold on writing books, reading books, and exercising the internal UTM


Recent Entries
< PreviousBrowse the ArchivesNext >
Subscribe to the RSS Feed

Paradoxes of Infinity in “The Annotated Turing”

January 13, 2009
New York, N.Y.

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:

And check out this brilliant statement:

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:

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:

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:

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:

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 ℵ0. Because each of these ℵ0 digits can be either 0 or 1, then the cardinality of the set of real numbers is:

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

Comments:

Interesting article. I ll probably grab your book. I might post on a subject for which you are very knowledgable but Aleph is a very interesting symbol:

http://www.scribd.com/doc/8218651/Aleph

cheers,

— Carl, Wed, 14 Jan 2009 09:36:13 -0500 (EST)

The HTML rendering on aleph-null is coming out quite poor in my browser (Firefox 2 on Linux) -- the aleph is tiny and the 0 is about three times larger rather than appearing as a subscript. Perhaps substituting texvc generated png images (like what mediawiki does) would provide a better rendition?

Hudson, Wed, 14 Jan 2009 12:37:16 -0500 (EST)

I just hate using bitmaps for text, but I suspect it's necessary in a case like this. — Charles

"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 π."

Of course - because those numbers are greater than 1. Sorry, I couldn't resist. I know what you mean, though. A very interesting post. I learned MANY new things. You just sold another copy of that book. Thanks for all your hard work.

Jim Dodd, Wed, 14 Jan 2009 12:58:30 -0500 (EST)

Yep, shoulda said "never print the square root of 2 divided by 2, or π/10." — Charles

More fun with infinity:

.999... = 1

http://en.wikipedia.org/wiki/0.999...

Dennis Williamson, Sun, 25 Jan 2009 21:09:13 -0500 (EST)

Hm, what if instead of looking at the real numbers in base 2, we looked at them in base 3? Then the cardinality of the real numbers would be 3^(aleph null)? Or how about base 4, in which case it's 4^(aleph null)?

So that's why I suspect that there's a new cardinality called aleph one.

— Fri, 30 Jan 2009 18:54:48 -0500 (EST)

Infinity does not exist, numbers are just a repetition in different orders. every thing comes back to the origin,zero (0).

PI= it can take millions of year to know the full number, but it will come to the origin,PI.

— Edgar 01,10, Thu, 30 Apr 2009 08:12:05 -0400 (EDT)


Recent Entries
< PreviousBrowse the ArchivesNext >
Subscribe to the RSS Feed

(c) Copyright Charles Petzold
www.charlespetzold.com