Now, let's move out of the plane, return to the Library, and apply these ideas to create the Grand Pattern there. At the conclusion of the first step, we went on hiatus having filled (251,312,000)! libits, each representing an ordering of the Library. Now we boldly expand the Library until there are
((251,312,000)!)!
libits, each one representing a distinct ordering of distinct orderings. In other words, this second step of the Grand Pattern subsumes the first step as just one particular ordering of all orderings of the books of the Library.
And now the iterative process grows clear; the third step of the Grand Pattern must account for all orderings of all orderings of all orderings of the books in the Library There are
(((251,312,000)!)!)!
such orderings. The third step of the Grand Pattern subsumes the second step as just one particular ordering of all orderings of all orderings of the books of the Library And so on, and so on, and so on.
One appealing aspect of the Grand Pattern is that for any conceivable finite assemblage of orderings in libits, infinitely many sections of the Library will contain precisely that same distribution of books. Each new step incorporates the preceding step as one subunit of the new step, and so each step repeats and repeats and repeats.
Another consequence, somewhat amusing, is that there will be abutting libits whose distributions are, in a sense, palindromic. A librarian, fortuitously born by the border between these two libits, would find a vast "wall" of adjacent duplicate hexagons! Moving in one hexagon away from the border in each direction would also reveal duplicate hexagons. Ditto for moving in two hexagons away from the border, and so on. There are as many quirky distributions in bordering orderings as we can imagine; after all, every distribution appears next to every other. Could a human librarian born in such a border locale guess that the Library contained volumes consisting of all possible variations of 25 letters?
A sharp-eyed reader may have noticed that we've consistently written "the Grand Pattern," as opposed to "a Grand Pattern." This is because once we have settled on a libit shape, there is only one such Grand Pattern. (See the Math Aftermath for more about why we must choose a libit shape.) Here is one way of seeing this mild form of uniqueness of the Grand Pattern:
Assume we've already constructed an infinite Library with books distributed in a Grand Pattern. Also assume, for the sake of argument, that a godlike entity also constructs an infinite Library, and for reasons that range from the puckish to the profound, wishes to distribute books in a different Grand Pattern. This Other Entity chooses the same-shaped libit, and after envisioning a tiling of the second Library, starts at an arbitrary hexagon, and for the first step, distributes 251,312,000 books in an allocation varying from ours. Next, for Step 2, the Other Entity distributes books into the remaining
libits in a distribution unlike our second step. And so on.
Let us add omniscience to our list of godlike attributes. Consequently, we know exactly how the Other Entity will distribute the books for the first step, the second step, etc. etc. Since every finite pattern, no matter how large, appears in our Grand Pattern, we simply choose an initial libit from our pattern which has the same distribution of books as the Other Entity's first step. By dint of omniscience, in fact, we chose that initial libit so that, moving outwards, it exactly shadows the Other Entity's second step, too. In fact, for any positive integer n, we chose so well, that moving outwards shows precisely the same distribution as the Other Entity's nth step; and remember, as implausible as this may seem, we must remind ourselves that all finite patterns, no matter how large, appear in a Grand Pattern. Finally, we observe that since our Grand Pattern exactly mimics the Other Entity's Grand Pattern for every positive integer n, it shadows it for all n; therefore, the two Grand Patterns must be the same. (See the Math Aftermath for more about this leap of logic from the finite to the infinite.)
A librarian granted eternal life and a Funes-like infinite capacity for photographic memories, walking a Grand Tour of the Library, reading and distinguishing every book, would discover that no pattern reliably repeats. On the other hand, a librarian of genius, equally endowed with the unimaginable ability to process titanic amounts of information, might well guess that, for a choice of the shape of a libit, the books are distributed throughout the Library in all possible orderings. And all possible orderings of all possible orderings. And all possible orderings of all possible orderings of all possible orderings...
As such, the books of this infinite Library are maximally disordered; and yet this ultimate disorder forms a unique overarching Order of all orderings: the Grand Pattern.
Math Aftermath: Libits, Uniqueness, and Jumping from the Finite to the Infinite
It is hard to be finite upon an infinite subject, and all subjects are infinite.
—Herman Melville, The Piazza Tales and Other Prose Pieces
In what follows, we briefly discuss two subtle points from above. First, we examine why the libits must be the same shape while comparing their respective Grand Patterns. If they are allowed to be dissimilar, we'll use, as an example, the two extreme examples from earlier in the chapter: we'll say a tower libit is a slender tower of stacked single hexagons, while a floor libit is completely contained in one floor. Imagine seven tower libits, six of them adjacent to a central one, that are exactly the same save that in their top hexagons, four books are permuted into slightly different positions. Then the towers are all identical except in the top hexagons, and even there, each top hexagon contains the same books as the others. (See figure 64.)
We claim that no floor libit can accommodate this distribution, for any floor libit that contains any hexagon of the central tower libit necessarily also contains a hexagon of at least one of the adjacent tower libits. By construction, these two hexagons must contain precisely the same books. However, no libit can have duplicate books; thus it follows that a Grand Pattern constructed out of tower libits cannot be replicated by floor libits. (See figure 65.)
In this part of the Math Aftermath, we consider the leap from the finite agreement at "each n" to the infinite agreement at "every n" that arose in the comparison of our Grand Pattern and the Other Entity's Grand Pattern. Here is a sequence ofideas that may help act as a bridge across the unimaginable abyss between the finite and the infinite: suppose our Grand Pattern differed from the Other Entity's. Then, by the well-ordering principle (see below), there is a smallest positive integer—for example, 412—such that our Grand Pattern differs from the Other Entity's Grand Pattern at Step 412. However, we know that the Grand Patterns are exactly the same at each finite step, including step 412. Thus, there can be no smallest integer at which they differ. Therefore, they are everywhere the same!
The well-ordering principle is an axiom of set theory (in some less commonly used logical models of arithmetic, it is a provable theorem). It says, in essence, that any set of positive integers has a smallest member. Although this sounds relatively innocuous, the constructivist school of mathematicians raises nontrivial objections to the well-ordering principle and the theorems which spring from it. It is worth mentioning that although these objections can never be formally refuted, there are few working pure mathematicians who are constructivists. On the other hand, a number of prominent computer scientists and applied mathematicians are in sympathy with the philosophic beliefs of the constructivists; for example, for them, a number doesn't exist unless it can be constructed. A strict constructivist won't admit the actual existence of or in the sense of an endless decimal expansion; rather, such a thinker would only acknowledge rational approximations to these irrational numbers.
SEVEN
A Homomorphism
Structure into Meaning
Because we do not understand the brain very well we are constantly tempted to use the latest technology as a model for trying to understand it. In my childhood we were always assured that the brain was a telephone switchboard. ('What else could it be?') I was amused to see that Sherrington, th
e great British neuroscientist, thought that the brain worked like a telegraph system. Freud often compared the brain to hydraulic and electromagnetic systems. Leibniz compared it to a mill, and I am told some of the ancient Greeks thought the brain functions like a catapult. At present, obviously, the metaphor is the digital computer.
—John Searle, Minds, Brains and Science
What is a divine mind? the reader will perhaps inquire. There is not a theologian who does not define it; I prefer an example. The steps a man takes from the day of his birth until that of his death trace in time an inconceivable figure. The Divine Mind intuitively grasps that form immediately, as men do a triangle. This figure (perhaps) has its given function in the economy of the universe.
—Jorge Luis Borges, "The Mirror of Enigmas," in Labyrinths
THE TIME HAS COME TO RETURN TO THE FIRST person singular voice. I've done my best, up to this chapter, to restrict myself to excavating, extending, enlarging, and explaining mathematical ideas which naturally arise from the story. But now, after scanning critical reviews and interpretations of coded meanings of the story, I find I have another reading to add to the existing constellation: a homomorphism between the structures of two different ideas. In biology, a homomorphism is a correspondence in appearance or form, but not in structure or origin. In mathematics, a homomorphism has almost the exact opposite meaning: it is a formal map between two seemingly dissimilar algebraic objects that illuminates a deep correspondence between their underlying structures. Unfortunately, interesting examples require background information beyond the scope of this book, and I stress that I am using the term "homomorphism" metaphorically. (In fact, I'm using "homomorphism" as a synonym for "metaphor.")
In 1931, by proving his first and second incompleteness theorems, Kurt Gödel inspired a thorough—and ongoing—reconsideration of the logical foundations of mathematics. Many excellent books have been written on Gödel's theorems; for my purposes, it is enough to think of the first incompleteness theorem as saying that if a formal axiomatic system is rich enough to generate the positive integers and the operations of addition and multiplication, then there are statements expressible that are undecidable: they cannot be proven true within the system of axioms, nor can they be proven false. In other words, the system is incomplete. (The second incompleteness theorem is a deep related result about proving the consistency of such axiomatic systems.)
In 1936, Alan Turing became a founder of computer science when he creatively combined his own brilliant ideas with some of Gödel's and published "On computable numbers, with an application to the Entscheidungsproblem." The Entscheidungsproblem was originally posed by Leibniz in the 1600s and formalized by Hilbert in 1928. It wondered whether a mechanical process or machine, manipulating symbols, could correctly assign truth values to statements posed within an axiomatic system such as mathematics. In other words, the problem asked if it is possible to create an automatic process that would determine whether any given theorem is true or false. The mechanical process or machine wouldn't need to provide a proof of a true theorem; it simply needed to correctly identify it as true.
Turing's brilliant tactic was to focus on the halting problem for computers, which hinges on a simple yes/no question: given a program coupled with a starting condition for that program, once it has begun to run, does it ever stop? For example, a program might be called NextPrime, and depending on the starting condition, the output will be the very next prime. If we use 17 as the input, then NextPrime will output 19, as 19 is the next prime after 17. On the other hand, using the current state of number theory and computer technology, if 251,312,000 is input to NextPrime, the program would run for years without giving the next largest prime. In this context, the Halting Problem asks ifthere could be one master program called, say, HALT, which would take the program NextPrime and starting condition 251,312,000 as inputs, and would output YES—because, in fact, given sufficient time and resources, NextPrime will eventually output the first prime larger than 251,312,000.
Let's consider the alternative, a program that never halts. An example of such a program involves finding pairs of twin primes, which are two prime numbers p and (p + 2). For example, {3, 5} and {29, 31} and {59, 61} are pairs of twin primes. The Twin Prime conjecture states that there are infinitely many pairs of twin primes, and in the past 100 years, mathematicians have amassed a fair amount of evidence to suggest that it is true. On the other hand, no proof has yet been found, so it is possible that there is an unimaginably large pair of twin primes that is the last such pair. A point of interest is that the Twin Primes conjecture is not falsifiable by showing the existence of a huge stretch of consecutive primes that have no twins. It's always possible that that the very next prime will have a twin.
Let TwinPrime be a program that finds twin primes, and let the starting input be the prime number two. When TwinPrime starts, it is guaranteed to run forever, either outputting pairs of twin primes until the computer crumbles into dust or, if there is a largest pair of twin primes, continuing to fruitlessly check larger and larger primes to see if they have twins. Whether or not there are a finite number of twin primes is irrelevant: TwinPrime will never halt. Thus, if HALT existed, if we input the program TwinPrime and a starting condition into HALT, the output would be NO—this program will never halt.
However, Turing showed that the halting problem is undecidable; that is, there is no way to construct a master program HALT that will always be able to determine if an input program and starting condition will or will not halt. As a consequence of the undecidability of the halting problem, it follows that the answer to the Entscheidungsproblem is negative: there can be no such process or machine that will decide whether a theorem in arithmetic is true or false.
A key element of Turing's proof is the creation of an abstract computing machine, since dubbed a Turing machine. The Turing machine consists of a black box and an infinitely long strip of tape; if the concept of "infinitely long tape" is distressing, instead think of it as "a very long tape, with dedicated crews of tape-extenders who are always able to add more tape as necessary." The tape is divided into little one-unit squares, and the black box occupies one square at a time. Each square of the tape may contain an orthographic symbol from a finite alphabet on it, or it may be blank (figure 66).
The black box begins sitting at a given spot on the tape, called the initial position, and the black box is in an initial internal state. An internal state is a simple instruction on what to output, given a particular input received. There can only be a finite number—possibly very large—of internal states. The black box reads the symbol in the square that it's sitting on, and this is the input for the Turing machine.
The Turing machine may then do several different things, depending on its internal state and the symbol in the square:
· It can erase the symbol in the square.
· It can write a new symbol from the finite alphabet in the square.
· It can change to a new internal state.
· It can move either to the left or right one square.
· It can halt (permanently).
That's it! Despite their prosaic description, Turing machines are remarkable. Although the Turing machine would run much, much, much slower, a programmer could write instructions for it that would reproduce any program available on the most advanced supercomputer in existence. Every single program for a desktop computer, including any program for word processing, graphics, or internet browsing: all may be converted into a format suitable for a Turing machine, which would then produce exactly the same output. (Of course, without a suitable way of converting the infinite tape's information into a picture on a screen, the output would be difficult to recognize.) Stronger still: any computing task currently imaginable by human intelligence may be performed by a suitably programmed Turing machine.
The Church-Turing thesis captures this state of affairs and projects it into the future; it says that any task done by any possible computing device running any pos
sible software could also be done by a suitably programmed Turing machine. The reason it is called a "thesis" as opposed to a "theorem" is that it can never be proved. There's simply no way to do so, because we have no idea of the possible computing devices or programs that might be dreamt of and implemented at some time in the future. On the other hand, the Church-Turing thesis could be disproved, because someone may invent a new kind of computing device which performs a task beyond the capabilities of a Turing machine. For a few decades, logicians sought to disprove the Church-Turing thesis, but every attempt failed. Thus, the default intellectual position is that the Church-Turing thesis is plausible, and it continues to gain in plausibility as the years go by; the longer it hasn't been disproved, the more plausible it becomes. A veritably Borgesian state of affairs: we know that we don't know and even know precisely that we might never know.
This, then, is the milieu of the Turing machine, the dizzying maze of ideas it inhabits: a welter of halts, non-halts, infinite loops and regresses, computations, equivalences, incompletions, logical indecisions, definitive answers, and potentially eternally unknown truths. These ideas formed part of the Zeitgeist of the 1930s, and while they would not have appeared in any popularization of mathematics, it is probable they entered the general intellectual discourse of the era, and therefore possible that echoes reached Borges.1 Regardless of Borges' conscious knowledge, I propose the following homomorphic mapping: librarians to Turing machines.
A librarian is constrained to move from one room to another. As a careful reading of the description of the Library indicates, a passage through the hexagons on any given floor constitutes a path which allows only the possibility of forward or retrograde motion. (It doesn't matter that the librarian can take stairs up or down; it's been demonstrated that Turing machines with multiple tracks and switchings are equivalent to the one-track version.) Each room is filled with a particular collection of symbols from a finite alphabet, which the librarian reads. The librarian, depending on the librarian's internal state and the books in the hexagon, may then either
The Unimaginable Mathematics of Borges' Library of Babel Page 12
