donn@utah-cs.UUCP (Donn Seeley) (09/06/84)
This discussion is a bit of a spoiler, so if you hate spoilers and
enjoy fantasy, rush out right now and buy Jorge Luis Borges' FICCIONES
(which contains some really remarkable stories besides 'The Library of
Babel', including 'The Circular Ruins' and 'Pierre Menard, Author of
DON QUIXOTE'), read it, then come back and read this...
'The Library of Babel' is really a fun story, and it's a fun story on
several levels, as a fantasy, as a mathematical game, as philosophical
speculation and as satire (Borges was once a librarian and was (is?)
director of the National Library of Argentina). The story has been
anthologized in numerous places, and has inspired a number of SF
stories; for example Gene Wolfe has admitted in PLAN[E]T ENGINEERING
that the Library was an inspiration for the peculiar library of the
Citadel (and perhaps the House Absolute and who knows how many other
places) in his BOOK OF THE NEW SUN.
One of the more straightforward puzzles is the construction of the
Library. Here is how Borges describes it:
The universe (which others call the Library) is composed of an
indefinite, perhaps an infinite, number of hexagonal galleries,
with enormous ventilation shafts in the middle, encircled by
very low railings. From any hexagon the upper or lower
stories are visible, interminably. The distribution of the
galleries is invariable. Twenty shelves -- five long shelves
per side -- cover all sides except two; their height, which is
that of each floor, scarcely exceeds that of an average
librarian. One of the free sides gives upon a narrow entrance
way, which leads to another gallery, identical to the first and
to all the others. To the left and right of the entrance way
are two miniature rooms. One allows standing room for sleeping;
the other, the satisfaction of fecal necessities. Through this
section passes the spiral staircase, which plunges down into
the abyss and rises up to the heights....
This description is somewhat ambiguous and incomplete; the only other
information we have is the following cryptic Dictum which is passed
down among librarians through the generations:
The Library is a sphere whose consummate center is any hexagon,
and whose circumference is inaccessible.
Let's make some assumptions. From the Dictum, let us assume that the
Library fills space; it extends to an arbitrarily large distance in all
directions in three dimensions (or more?). Let's assume that the
second 'free side' of a hexagon opens onto another gallery directly,
without passing through a hall with a staircase. Without this
assumption it would be difficult to establish an arrangement compatible
with the first assumption. Next, let's assume that given sufficient
time, it is possible to travel from any hexagon to any other; this is
implied but not stated in the course of the story. Finally, to make
tiling convenient, let's assume that the halls which contain stairwells
are hexagonal in shape and the same size as the book hexagons. We can
explain the narrowness of the corridor by the fact that the bedrooms and
bathrooms and stairs take up most of the floor space. We can even put
the stairs in the same position as the central ventilation shaft of the
book hexagons (they were pre-fabricated!).
Then the fun question to ask is: How are the hexagons laid out?
Several possibilities come to mind, depending on what aesthetic
restrictions one chooses to impose on the structure. One really simple
possibility is to lay the rooms out in rows; here is a crude picture
(O's mark stairwell hexagons, ='s and X's mark doors):
\ / \ / \ / \ / \ / \ / \ / \ / Sample closed hexagon:
= O = = = O = = = O =
/ \ / \ / \ / \ / \ / \ / \ / \ / \
= O = = = O = = = O = | |
\ / \ / \ / \ / \ / \ / \ / \ / \ /
= = O = = = O = = =
/ \ / \ / \ / \ / \ / \ / \ / \
In this batik-like pattern the paths through the Library run from left
to right, with a stairwell every third hexagon. This arrangement has a
difficulty -- it's impossible to move from one row of hexagons to
another on the same level. If the same pattern occurs on lower levels,
then the Library ends up being partitioned into planes of hexagons.
This runs against our assumption that every hexagon is accessible from
every other.
Perhaps we can salvage this tiling and preserve its symmetry by
assuming that alternate levels of the Library alternate reflections of
the tiling. Reflecting the tiling across an axis passing through a
column of stairwell rooms preserves the positions of stairwells and
ventilation shafts (which are mutually exclusive by virtue of the
statement that they continue 'interminably') but changes the
orientations of the rows of rooms. This allows you to go down a level,
traipse through a few rooms, then come up a level into a different
row. Does this solve the problem?
It seems that this isn't quite enough. Instead of arbitrarily many
sets of rooms, we now have three sets of rooms. The difficulty is that
stairwells are spaced three rooms apart, so when you go down a level
and skip along to another stairwell, you will always come up a multiple
of 3 rows away from your starting point. Rows that are 1 mod 3 or 2 mod
3 distant are in disjoint sets. Is there any tiling in which all the
rooms are laid out this way and every room is accessible from every
other room? By 'this way', I mean an arrangement where all the stated
assumptions are true, with the additional hypotheses that every hexagon
has an infinite linear path going through it, and various levels may be
rotations or reflections of the basic pattern.
What happens if the paths through the Library need not be straight? An
example of a crooked tiling might be the following (X's and ='s denote
doors):
\ / \ / X / \ / \ / X / \ / \ / Sample closed hexagon:
= O = | = O = | = O =
/ \ / \ / X / \ / \ / X / \ / \ / \
= O = | = O = | = O = | |
X / \ / \ / X / \ / \ / X / \ / \ /
| = O = | = O = | =
/ X / \ / \ / X / \ / \ / X / \
As with the previous pattern, if this pattern were to continue up and
down for indefinite distances, then the Library would be partitioned
into an infinite number of sets. Unlike the previous pattern, if the
levels of the Library alternate with appropriate reflections of the
tiling, any hexagon of the Library can be reached from any other. (Try
to visualize the method.)
While this arrangement satisfies all the assumptions, it is clumsy. If
you want to reach a hexagon that is on the same level as the one you
are standing in, chances are that you can't get there without changing
levels. Is it possible to have a layout of hexagons that will get you
to any other hexagon on the current level without needing to cross
levels?
This is an easy question, so I'll make it somewhat harder: is it
possible to create a layout such that the time it takes to travel
between two hexagons on the same level, without changing levels, is
independent of their location in the Library? Is it possible to design
a layout that has a minimal average path between two hexagons on the
same level? I don't have answers for these...
A liberal interpretation of Borges' description might permit stairwell
hexagons to have more than two entrances. Does this change the
problem? (This is fairly easy.)
That's all I have to say on this at the moment. Corrections and
suggestions are welcome... The next posting I want to make on this
will examine the size of the Library.
Donn Seeley University of Utah CS Dept donn@utah-cs.arpa
40 46' 6"N 111 50' 34"W (801) 581-5668 decvax!utah-cs!donn