The Library of Babel

by Kevin J. Lin

The problem of the Library of Babel is actually an analogy to numbers and counting. Consider the ordering method for the books to be some algorithm (If you have no programming background, an algorithm is simply a sequence of steps that a computer could perform). More precisely, the ordering is a function. A function is a sequence of operations performed on some input, which yields some kind of output. In the case of our library, the input is the path to a particular book and page number (its coordinates), and the output is the contents of that page. Expressed in those terms, which of the CD-ROMs described could be finite functions?

It is quite easy to see that a small subset of the library could fit on a CD-ROM. You may have a CD-ROM near you which contains a small encyclopedia. That would qualify. It is somewhat less obvious how you could fit the whole library onto the second CD-ROM.

The trick is in the fact that this library is well ordered. You may have heard that in computers all data is represented as numbers. The letter "A" might be number 01, "B" might be "02"; we could thereby say that "Dancing Queen" was performed by "01020201". Any particular book will be represented by a number- a very large number (over two million digits!) While storing two million digits on a CD-ROM is easy, storing every possible combination of those two million digits would be beyond ludicrous.

Fortunately, we don't need to; we just need to define a function which, given the right input (the path to a particular book) can yield every possible outcome. Since the path to a particular book may also be expressed as a number, any function which makes a one-to-one correspondence between path and book will work. In essence, every time someone goes to a particular book the path they take writes the book! Of course, the path to a certain book will be very long- but this is a BIG library.

Still with us? Unfortunately, the same tactic will NOT work if we require that the books are randomly distributed (CD-ROM 3). By definition, a random distribution is not described by a function. It would be impossible to create, let alone store, the Library of Babel unless we allow for a systematic ordering method.

Now for CD-ROM number 4: since we've solved the problem of storing the entire library for CD-ROM #2, we now must add a few books of infinite length. Maybe you've already figured out the trick we're going to use: these books can repeat themselves. So just add a few books which simply repeat the same page over and over again!

But what about every single text of finite length? Is this still possible? The answer is yes. Remember what we are looking for is a function or algorithm which for some input will produce the desired book. Some of the longer books will require extremely long (almost infinite) paths. Nevertheless it is possible to define an algorithm such that for any book of finite length, there exists an input (or "path") which will produce it.

Now for the final CD-ROM. If you've been following our argument you've seen we can define an algorithm to produce all the books of finite length, which is an infinite number. It seems like a small step to produce all the books of infinite length, which is another infinite number. But it isn't. These two infinities aren't equal. There is no algorithm which can produce all books of both finite and infinite length from the set of all finite inputs. Using our number analogy, the set of possible inputs (or "paths") correspond to the set of integers. Each book represents a number. The books of finite length are the integers. The books of finite and infinite length are the real numbers. It has been proven that the set of reals can not be mapped with a one to one correspondence with the set of integers. Whatever algorithm you choose to define for the library, there will always be books that no possible path can produce!

Back to the Puzzle