The Library and Gödel
Considerations about permutations, (in)finity, the size of the universe, Gödelization, holographic memory and exponential growth.
Second: The orthographical symbols are twenty-five in number. (1) This finding made it possible, three hundred years ago, to formulate a general theory of the Library and solve satisfactorily the problem which no conjecture had deciphered: the formless and chaotic nature of almost all the books.
These examples made it possible for a librarian of genius to discover the fundamental law of the Library. This thinker observed that all the books, no matter how diverse they might be, are made up of the same elements: the space, the period, the comma, the twenty-two letters of the alphabet. He also alleged a fact which travelers have confirmed: In the vast Library there are no two identical books. From these two incontrovertible premises he deduced that the Library is total and that its shelves register all the possible combinations of the twenty-odd orthographical symbols (a number which, though extremely vast, is not infinite).
I Number of books
Every book consists of 410 pages with 40 lines each and 80 characters in each line. Thus, every book is made out of a total of 1,320,000 characters. If we only use the 25 characters mentioned above and assuming the Library contains every possible permutation of these strings over the alphabet, we find that the number of all books is given by 251,320,000.
Lets rewrite this in standard scientific notation. We want to solve the equation
251,320,000 = 10x,
therefore calculate
log10 ( 251,320,000 ) = x.
Applying the rules for calculating logarithms gives us
loga ( xn ) = n loga ( x ),
therefore in our case
log10 ( 251,320,000 ) = 1,320,000 · log10 ( 25 ),
from which we calculate x as integer:
x = 1,845,281 .
The number of permutations (and therefore the number of books) is given by 101,845,281; rounding up x to the next bigger integer does not significantly distort our numerical results since we are dealing with numbers that greatly exceed any imagination.
II Size of the Library
Following the description in Borges' manuscript, we assume, that every hexagon in the Library has an area of roughly 50 m2 and is 2 m in height. Then every hexagon corresponds to a volume of 100 m3.(2) There are book-shelves on four out of every six walls, containing 32 books each. The number of books in every hexagon is then 640. Since the total number of books in the Library is 101,845,281, we have to find a way to deal with these huge numbers.
Taking 640 = 102.806, which we round up to 103, we need approximately 101,845,278 hexagons to contain all books. Well, even if we could somehow decrease the exponent by thousands, these numbers are still beyond imagination. Lets try a different approach.
Every hexagon has a volume of 100 m3, so the total volume of the Library is given by 101,845,278 · 100 = 101,845,280 m3. Well, apparently cubic meters are no meaningful measure for the Library. Lets calculate the Librarys volume in cubic lightyears. One lightyear is the distance light travels at a speed of 300,000 km/sec within a year. Therefore, one lightyear is equal to a distance of von 300,000 km/sec · (60 sec · 60 min · 24 h · 365 d) = 9.4608 · 1012 km. A cube with edge length of one lightyear has a volume of 8.468 · 1038 km3, which we round up to 1039 km3. The Librarys volume is thus given by 101,845,232 ly3.
Still this number is far to big to imagine. What measure can we apply to get a rough idea of the Librarys vastness? How about the size of the (observable) universe? We assume that the observable universe is a sphere with a radius of 93 billion lightyears.(3) Its volume is then given by
4/3 · PI · r3 = 4 · 1032 ly3.
Divide the Librarys volume by the volume of the observable universe, we obtain
2.5 · 101,845,199
times the volume of the universe.
Okay, now we start to sense how big the Library really is. The entire observable universe is almost two million magnitudes smaller than the Library. Wait a second, we need to stress this differently - the entire observable universe is almost two million magnitudes smaller than the Library, that is a-two-followed-by-one-million-zeros smaller!
For comparison only: one of the smallest structures in our cosmos (the nucleus of hydrogen aka the proton with a diameter of 10-15 m) is roughly speaking 43 magnitudes smaller than the (observable) universe with a diameter of approximately 1028 m. But even this scale is dwarfed when comparing the size of the universe to the size of the Library.
III Gödelization
Lets index the vast inventory of the Library. Granted, this might not make much sense since most of the books contain meaningless gibberish, but we need to put the books in some order, don't we? How do we start?
Our task is to develope some sort of numeric coding to uniquely adress a single book. Well, how about prime numbers? Prime factorization of any given integer is unique which means that the mapping of an integer to its prime factorization is one-to-one and onto. We now apply a method that was originally developed by Kurt Gödel. This so called Gödelization works as follows:
We map each one of the 1,312,000 positions of one book onto a prime number. To achieve this we might take the first 1,312,000 prime numbers and sort them by size, starting with 2. The first position is associated with the first prime number, the second position with the second prime number and so on up to the 1,312,000th position.(4) Now we need to encode information about which of the 25 characters we find at a given position. To do so, we map each character to an integer. Blank space might be given number 0, then A is given 1, B is given 2 etc. Our list of characters might look like this: BLANK-0, A-1 B-2 D-3 E-4 F-5 G-6 H-7 I-8 K-9 L-10 M-11 N-12 O-13 P-14 Q-15 R-16 S-17 T-18 V-19 X-20 Y-21 Z-22.(5) Finally, comma (,) is associated with 23, full stop (.) with 24. In doing so, we have uniquely mapped each character onto a number.
The information, that we find character i on position x in the book is encoded by taking prime number x to the power of i. Here is an example: we arbitrarily take the string O TIME THY PYRAMIDS. This string is made up of 19 characters (since blank space is counted as a character, too). To gödelize this string we need to take the first 19 prime numbers, which are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67.
The entire string is then encoded by taking each prime number (representing position) taken to power of i (the number of the character) and multiplying them. On the first position (prime number 2) we find O (associated number 13), therefore we calculate 213. On the second position (prime number 3) we have a blank space (associated number 0), we calculate 30 etc. After having done so for each of the 19 positions of our string, we multiply all numbers obtained, therefore generating a unique prime factorization which uniquely encodes our string O TIME THY PYRAMIDS.
is the Gödel number of our string. In standard scientific notation that is roughly 2.153889... · 10286. Well, we should not be too puzzled about the fact that this again is a huge number.
We have encoded a string of 19 characters. It is clear, that the Gödel number of a string of length 1,312,000 (the content of a book) is much, much bigger. Still, Gödelization is at least in principle a way to index the books of the Library.
One interesting aspect of our (not so arbitrarily chosen) way to Gödelize is the fact, that the book that consists only of blank spaces, will be given Gödel number 1, since every single of the 1,312,000 prime numbers representing the 1,312,000 positions are taken to the power of 0. Well, from here on it is clear that we can construct an ascending order by which we can enumerate all books, beginning with the blank book and ending with the one book that consists of 1,312,000 full stops. The next book in our order might be the one that starts with an A on first position, followed by 1,311,999 blank spaces. That books Gödel number is
21 · 30 · 50 · ...,
which is equal to 2. The next book, starting with the character B on the first position, followed by 1,311,999 blank spaces has Gödel number
22 · 30 · 50 · ... = 4,(6)
The one book starting with our example string O TIME THY PYRAMIDS, followed by blank spaces, would have the very index number that we calculated for the encoding of this string. It is clear, that this book is not the only one containing our example string. Since the Library contains all possibly permutations, there must also be a book starting with a blank space in position 1, followed by O TIME THY PYRAMIDS, followed by blank spaces. Unfortunately, even if two books have identical contents, their Gödel numbers will almost never have an obvious link to one another.
So the contents of these two books are identical - we have just shifted forward the strings position (we have neither alterted the characters sequence nor have we replaced one character by another). Lets pool books with identical but maybe shifted contents to what I want to call translation groups (translation as a mathematical not linguistical term). All books of a given translation group have identical contents in the sense that all characters appear in the same sequence (we just want to shift the entire string of 1,312,000 characters of a given book back or forth - we do not want to change O TIME THY PYRAMIDS to TTIIYYRR EM MHDSAP or the like). We can imagine this as follows: we take the book that starts with O TIME THY PYRAMIDS (followed by blank spaces to the end) and shift the string of characters, let's say, by one position to the right. The last blank space on the last page does not disappear but reappears on page 1, position 1 as if the string of 1,312,000 characters of each book is arranged as a ring. How many books does a translation group consists of? Well, apparently every translation group contains exact 1,312,000 books since this is the exact number of possible translations.(7)
In his short story, Borges implies that all the books are randomly scattered throughout the Library which might indicate that they are not given in any order based on some Gödelization.(8) Therefore, we can assume that all 1,312,000 books of each given translation group are randomly and evenly distributed. Now we understand why the narrator in Borges' story is not too concerned with the fundamentalists' attempt to destroy the books. The mere vastness of the Library guarantees that there will always remain a sufficiently large number of books with identical contents that are outside the fundamentalists' range (maybe billions of lightyears away?). Additionally, we have to take into account that appart from the books of a translation group (which have identical contents) we have even more books with almost identical contents, which may differ only in some characters. How many books are there that have almost identical contents? Well, that highly depends on the content itself since readability of - let's say - a scientific text might still be provided even if a large number of characters is exchanged randomly (DEOXYRIBONUCLEIC ACID for example is such a technical term that it could still be deciphered even if one exchanged many of its characters).
IV Population
What chance does a hypothetical mankind have to retrieve all the literate treasures burried in the Library? Well, the state of utmost information is reached when one has read all the books. That is certainly impossible for a single human being. Luckily, that is not necessary. Even in our real world no single individual person can know all the books in the world.(9) It is absolutely sufficient if mankind as a whole know all the books. Borges implied something like that by saying that in ancient times, there was one man responsible for every three hexagons. Well, I somehow figure it is time to extend the librarians' duties to the female part of the human population, therefore bringing an end to male chauvinism. Lets swarm out into the depth of the library. In addition to the immediate doubling of the number of librarians after some time we observe that we do not have to advance to the most remote areas of the vast but finite (sic!) Library to learn all about its books. We already stated that there is a huge number of books with identical or almost identical contents that we assumed are distributed evenly over the space. This makes the Library sort of a holographic memory, where every part contains all the information of the whole.(10) The Librarys totality also means high redundancy of its information. Therefore, completely colonizing the Library is not necessary. Since there exist 1,311,999 identical books (identical with respect to translation) to each (!) book that are presumably distributed randomly, mankind would only have to colonize one milionth of the entire space. Instead of every single one of the 101,845,000 hexagons(11), it is sufficient to visit at least 101,844,994 hexagons if we want to obtain all the information stored in the Library. Granted, that is still a lot of space to colonize. Before we finally abandon all hope of ever being able to retrieve all the possible information and surrender to the vast Library, we marshall one last weapon in our battle with huge numbers: exponential growth. The Library is finite, therefore provided a constant growth rate, mankind actually can colonize the entire Library (which is not even necessary) within a finite time frame.(12) How long would that take? Assuming an annual growth rate of 2 per cent (which is significantly higher than the average annual growth rate in the western civilization but still lower than the growth rates on the indian subcontinent or in the middle east), we need to solve the equation
(1.02)x = 101,845,000.
Here, x is the number of years it takes to roughly match the number of people with the number of hexagons. We calculate:
x = log1.02 ( 101,845,000 ),
therefore
x = 1,845,000 · log1.02 ( 10 ),
ergo
x = 1,845,000 · log10 ( 10 ) / log10 ( 1.02 )
thus
x = 214,536,600.
With exponential growth (which means that the growth rate remains constant) the Library can be colonized within approximately 200 million years.(13) Sure, that is a long time, but it is significantly shorter than the time life has been existing on earth. It is also much shorter than the estimated age of the universe. On a cosmological time scale, this is somehow manageable. Here the mightiness of exponentially growing processes manifests once again. The Library of Babel is two million magnitudes bigger than the observable universe and still, an unhampered growth of population would use up all the space within a relatively small time.
I wrote this text in december of 2006. It refers to The Library of Babel by argentine writer Jorge Luis Borges. The first two paragraphs as well as the first footnote (in italics) are excerpts of the original text.
Addendum
weblink
There is an english translation of the original text on the internet.
The Library of Babel translated by J. E. I.
Footnotes
(1)
The original manuscript does not contain digits or capital letters. The punctuation has been limited to the comma and the period. These two signs, the space and the twenty-two letters of the alphabet are the twenty-five symbols considered sufficient by this unknown author. (Editor's note.)
(2)
I have chosen these figures beceause they conveniently fit into my calculations and are somehow realistic. As a matter of fact, it does not really change the principal considerations if the hexagon is given an area of 5 m2 or 500 m2.
(3)
93 billion lightyears is a current estimate for the distance between earth and the edge of the visible universe in any direction.
(4)
Don't worry: it's not a problem to obtain a list of 1.3 million prime numbers. One can (quite easily) prove mathematically, that there are infinitely many prime numbers and every personal computer will be able to calculate tens of thousand of prime numbers within the hour. And even if we need to take very large prime numbers to encode all the positions of our books - well, we simply must not get freaked out by large numbers while sojourning in the Library.
(5)
Borges' original text speaks of 22 characters which is not compatible with the english alphabet. But in the end, it does not really matter what alphabet the books in the Library of Babel are written in.
(6)
In the book with Gödel number 3 (Gödelization: 20 · 31 · 50 · ...) we find on second position in line one on page one an A followed by blank spaces. Unfortunately, that does not conform to our intuitive assumption, that book number 3 would have a B on position one, line one, page one, followed by blanks. But I'm pretty shure, if you have advanced to this point without loosing your mind you will somehow manage to deal with this.
(7)
Strictly speaking, this only holds true for books with distinguishable characters. The one book that contains only blank spaces might be unique since there is no way to distinguish two books entirely consisting of blanks. Well, Borges does not tell us anything about these special cases, so we might as well drop them right here.
(8)
Granted: that is somehow uncertain. Who knows if there might not be a hidden order that follows - maybe - a Gödelization of which we simply do not have the details? But then again, if we grasp to these straws and assume we just have to find the right encoding details to make sense of the Library, we have to face the fact that there might be even more ways to encode than there are books. How are we supposed to find the right encoding method?
(9)
The biggest library on earth, the Library of Congress in Washington, D.C., bears more than 20 million volumes. Compared to the Library of Babel, that is neglectably small but the books in the Library of Congress must be infinitely more rich in content than the vast amount of senseless and chaotic books in the Library of Babel.
(10)
To be more precise: every sufficiently large part of the Library contains all the information of the entire Library. But one might want to stress out that the Library of Babel is the mere sum of permutations of one volume and therefore one single volume already contains all the possible information. That would be a nice task: how long does it take to obtain all the information by means of manual permutation? Maybe we should go and find infinitely many monkeys for this menial task...
(11)
Or one librarian in every three hexagons or one in every three hundred heyagons - we already know that these considerations are meaningless when facing the vastness of the Library.
(12)
Borges does not provide any information about the life span of his Library-universe. Its infinity in time is only taken as an axiom. For lack of more details of the Librarys cosmogony (our should it be librogony?) and the physical laws that govern Borges' universe we just stick to the infinite-age-axiom.
(13)
We do not worry about about the problem of exchanging information among the people of the Library. Any message proclaiming the discovery of an extraordinary book, broadcasted with the speed of light, would take billions of years to travel a significant distance within the Library. Not to talk about the political, economical, sociological, psychological and logistical challenges humankind would face...