Searching for Anna Karenina
17th May 2016
... Comments

Let us explore a little thought experiment together which demonstrates how quickly problems involving a search of possible solutions quickly get exponentially out of control.

The Library of Babel is a mythical library that contains all possible 500 page books. Each book in the library contains a unique but random combination of letters and numbers.  Suppose the first book contains entirely A’s. The second book may be entirely A’s with a single B in a random position.  In this way we can imagine all possible combinations of letters and numbers making up a 500 page book.

Most books in the library will be nothing but gibberish. There is actually one book that consist entirely of blank pages. Many books will contain the odd recognisable word or phrase amongst the gibberish. However, it is a certainty that among the books MUST be perfectly rendered copies of classics such as Moby Dick, Bleak House or Anna Karenina.

It is also astonishing that amongst the books there must be the most perfect and accurate biography of your life from your birth up to the moment of your death.

Consider Anna Karenina. There will be thousands of versions where there are only a few misplaced characters – otherwise the book is perfectly legible.  The question is – how long might it take us to search the library and find at least one usable copy of Anna Karenina?

So how many books are we talking about?  A few million perhaps?

If each book has 500 pages of 40 lines with 50 characters per line then each book contains (500 x 40 x 50) 1 million characters.  If each character can be any of 100 possible characters (upper and lower case, numbers and punctuation) then there must be 100 raised to the power of 1 million books!  (written as 100 ^1000000)

To put this into perspective, there are only around 100^ 40 particles in the entire known universe!

How large would the Library of Bable need to be to contain these books. If all the books are placed side by side on a single shelf and each book is sat 2cm thick then the shelf will be 2 x 100 ^1000000 cm long.

Converting this to km we get the astounding fact that the library shelf must be billions and billions of times larger then the entire observable universe.  If you search the self for Anna Karenina in a rocket ship travelling at the speed of light the universe itself would run out of time before you had travelled an infinitesimal fraction of the entire shelf of books!

This problem is very like, but much worse, than the famous riddle of the chessboard with 1 grain of rice in one square, then two in the next and then four etcetera.  The chessboard contains 2 ^64 grains of rice – more than has ever been produced in the history of the universe.

So the moral is of course, to find a readable copy of Anna Karenina use Amazon rather than the Library of Babel.

About the Author

Tim I

Member since: 4th June 2010

Passionate about promoting science, reason and critical thinking.

Popular Categories