Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.1 6/24/83; site utah-cs.UUCP Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!houxm!vax135!cornell!uw-beaver!tektronix!hplabs!utah-cs!donn From: donn@utah-cs.UUCP (Donn Seeley) Newsgroups: net.sf-lovers,net.books,net.math Subject: Fun with Borges' 'The Library of Babel' Message-ID: <3022@utah-cs.UUCP> Date: Thu, 6-Sep-84 06:00:20 EDT Article-I.D.: utah-cs.3022 Posted: Thu Sep 6 06:00:20 1984 Date-Received: Wed, 12-Sep-84 02:08:51 EDT Organization: University of Utah CS Dept Lines: 145 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