The Unimaginable Mathematics of Borges' Library of Babel (31 page)

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, the 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 25
^1,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 25
^1,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 25
^1,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
possible 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.
¹
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