This post is, first and foremost, an introduction to state machines (also called “automata”) via an extended Borgean allegory about an existence in a labyrinth, a sort of infinite gallery of mazes. It introduces several significant concepts—equivalence, finitude, acceptance, determinism, and the powerset construction—as a succession of realizations about that existence.

Why Borges? I picked up Labyrinths in early February, an anthology and a maze of furtive interreferences in its own right. Borges toys with combinatorics. He writes that “Lully’s machine, Mill’s fear and Lasswitz’s chaotic library can be the subject of jokes, but they exaggerate a propension which is common: making metaphysics and the arts into a kind of play with combinations.” He joins them, even reconstructing Lasswitz’s library in The Library of Babel. The stories and essays are replete with villas subdivided into infinitely many rooms, repetitions collapsed into single events, points that contain all points, and so on.

I realize adding the allegory risks muddling the subject matter. My hope is that the metaphysical confusion of the labyrinth is relatable in a way that makes the mathematics feel more familiar. If I get away with that binding, it’ll work in reverse: if the math resembles familiar philosophy, we can use the mathematical concepts as a grammar for their philosophical doubles.

All the parts of the house are repeated many times, any place is another place. There is no one pool, courtyard, drinking trough, manger; the mangers, drinking troughs, courtyards, pools are fourteen (infinite) in number. The house is the same size as the world; or rather, it is the world.

The House of Asterion¹

Imagine, if you will—though you can relate to this freely if it sounds familiar—that you live your life in a vast labyrinth of circular rooms, with marked doors that open into passageways which bring you from one room to the next. Each room is indistinguishable, except maybe by the number and labels of its exits. You’re so disoriented that you can’t know how you entered the room you’re in. In fact, there may be no way to return to the room from whence you came—the passages seem to close up behind you as you step out of them. There’s no backtracking; you can only progress into the labyrinth, choosing among the doors each room affords you.

In your heart you know this is not a labyrinth one leaves. The labyrinth is the same size as the world; or rather, it is the world.

In one of the maze’s innumerable connected rooms you’re visited by the whisper of a blind sorcerer. The sorcerer explains he built the labyrinth—designed its general schematic, its endless succession of identical rooms, the workings of its corridors, the labels on its innumerable doors, etc.—but, blind, he can’t read the signs, can’t travel the monotonous expanse of corridors and galleries he devised.

This is the sorcerer’s proposition: starting in some fixed room in the maze, you are to travel through a series of doors, following exactly his instructions for which door to select. If, at any point, he gives you an instruction you can’t follow—gives you some label that does not match any door out of the room you’re in—you can cry out, and (zap!) he will teleport you back to the starting room to receive a new set of instructions. When a set of instructions can be followed to the end, you are (zap!) also teleported back.

In this way, with you as a proxy, the sorcerer explores the great maze. In return, he promises, the many forms of the labyrinth and the meaning of your hermitude will be revealed.

Naturally curious, you accept.

This assemblage—you in your maze, following instructions—is essentially a state machine:

1. Each room is a state; you can be in one state at a time.

2. The fixed topology of the labyrinth determines which state transitions are allowed. A given room does not necessarily allow passage into every other room in the labyrinth; you can only move to a successive state available from your present state.

3. Your task is to discover whether the sorcerer’s inputs can be followed, whether they’re acceptable to the state machine.²

Equivalence

The universe (which others call the Library) is composed of an indefinite and perhaps infinite number of hexagonal galleries, with vast air shafts between, surrounded by very low railings. From any of the hexagons one can see, interminably, the upper and lower floors. The distribution of the galleries is invariable.

The Library of Babel

The first room has two doors: one marked left, the other marked right. The sorcerer’s first instruction, left, takes you through that left door and its narrow passageway, into another room with two doors: one marked left, the other marked right.

In fact, every door—left or right—opens on another indistinguishable room with identical doors; there is always a left door and a right door to pass through. Each foray ends either with some unfollowable instruction (e.g. to take a door marked south, or salad bar, or de Broglie: none of these doors is ever available) or with the exhaustion of the sorcerer’s sequence, at which point (zap!) you begin, with a new sequence, from the start. A lifetime of lefts and rights passes. The sorcerer’s instructions are inexhaustible; some sequences take eons to follow.

In fact, if it’s constructed how it appears—each room leading to two more rooms—this labyrinth must fork infinitely towards the horizon, right? And, since only one set of left-right instruction sequences leads you to any one of the infinite rooms, the sorcerer has a literally inexhaustible list of routes to explore: one route for each room.³ We can diagram the start of this maze as follows:

While it explains what you observe of the maze, this seems a bleak existential outlook… but you’re rightfully suspicious of existential certitudes! In fact, out of the mire of indistinguishable rooms and doors and passageways surfaces a suspicion about the maze itself.

The sorcerer’s instructions seem farsical. Predictably, choosing the left door or the right door makes no difference: they lead to indistinguishable rooms. What if the left and right doors mark, in truth, two passageways into the one room?

Here, it seems, there are fewer rooms to see. Whereas before there was one room for every acceptable sequence of instructions, now there is only one room for every length of acceptable instructions. Any sequence of three instructions—be it left-left-right, right-right-right, or some other—leads you to the third room. There are precisely 2ⁿ paths to the n^th room.

This does little to relax the absurdity of your agreement with the sorcerer. First of all, no sequence of sorcerers’ instructions will ever disambiguate an infinite Braid from an infinite Garden of Forking Paths, even though their diagrams look different. An instruction valid in one is always valid in the other; an instruction invalid in one is correspondingly invalid.

Second, and more importantly, an infinite Braid is still infinite. Though there may be more than one path to a given room in the sequence, there is still an infinite number of rooms; the sorcerer will never visit them all. If you were to draw out a map of this labyrinth which admits an infinite number of paths, the map would extend infinitely to one side (this map would, you realize, expand to cover the labyrinth itself, no matter how small its lines and letters).

In one of your travels, after an eternity, something occurs to you about the indistinguishability of the rooms: just as two doors may be identical aside from their labels, as in the Braid diagrammed above, perhaps two indistinguishable rooms…

You stop the blind sorcerer between instructions. You explain to him that he has, in visiting this room, visited the labyrinth. In fact, for all the vertigo of his infinite acceptable sequences, this room is equivalently the labyrinth.

The sorcerer, with an air of didactic satisfaction, asks for an explanation.

It’s a little roundabout to start an explanation of finite state machines with an allegory involving infinite rooms—infinitely many states, a sort of “infinite state machine.” These don’t have any practical application except to illustrate the relationship between the topology of the maze and the set of instructions it accepts. First we have a maze that accepts an infinite number of instruction sequences, and where no distinct sequences lead to the same room; then we have another maze that accepts an infinite number of instruction sequences (the very same!), but where distinct sequences can lead us to the same place.

These two labyrinths, the Garden and the Braid, also introduce the idea of equivalence. If two state machines accept the same inputs—if there’s no series of instructions from the sorcerer that reveals, via its acceptability in one and unacceptability in the other, in which maze we’re trapped—then the two state machines are equivalent.

From here on we’ll deal with finite state machines (labyrinths with a finite number of rooms and doors), beginning with your answer to the sorcerer. Finite state machines are more useful: we can actually write programs that implement them, we can draw them out in finite diagrams, and there’s nothing we can express in an infinite maze that we can’t equivalently express in a finite one.

Finitude

Today, one of the churches of Tlön Platonically maintains that a certain [room with two doors is] the only reality. All men, in the vertiginous moment of coitus, are the same man. All men who repeat a line from Shakespeare are William Shakespeare.

Tlön, Uqbar, Orbis Tertius

This is your explanation: these rooms are indistinguishable to your explorations; every state permits the same two state transitions as the start state, so every state transition is essentially a return to the start state. Framing the state machine this way simplifies it: we can think of a single room instead of an infinite number of rooms!

Importantly, this simplification doesn’t change what instructions the maze allows: any among the infinite number of instruction sequences accepted by the infinite state machines diagrammed above is also accepted by the one-room simplified state machine diagrammed here. It’s a finite maze with an infinite number of paths.

In fact, any finite maze with a cycle—any way to leave a room and eventually return to it—accepts an infinite number of paths, because you can validly move through the cycle once, twice, or any number of times. This one is a one-room cycle: you can transition from the one state to itself.

This dynamic is what makes finite state machines so useful: they’re concise.

Sometimes they offer minimal notations for sequences that are otherwise hard to describe.⁴ It’s easy to describe “any sequence of lefts and rights,” but sometimes we want to describe more complicated families of instructions. Compare the following diagrams to the verbal descriptions of the instructions they allow:

Description	Diagram
Any sequence of lefts and rights where odd-indexed instructions are right.
Any sequence of lefts and rights, but where every third instruction can also be up.
Any number of up instructions, followed by any number of repetitions of the order right-up-left.

Each of these mazes describes a distinct infinite set of instruction sequences. The diagrams are clearer than the verbal descriptions.

The set of instructions the maze allows is locked into the maze’s topology; the maze is a grammar for its own instructions. We can use the maze to generate instructions, not just test them: if the sorcerer were to ask you to produce a valid instruction sequence for a maze (some “syntagm” in the maze’s grammar), you can take an arbitrary series of doors to build one.

Note, these state machines’ properties are stable independent of their labels. We’ve been working with directional labels (left and right) because they suit the labyrinthine theme, but nothing changes if we replace left with 0 and right with 1.

In fact, there are more equivalent finite labyrinths—labyrinths with a finite number of rooms, that admit any sequence of binary instructions—than those covered here. Their construction is left as an exercise for the reader.⁵

The blind sorcerer listens quietly to your explanation of the infinite maze with one room, which perfectly describes every instruction you could ever accept from him—every path in the Garden of Forking Paths. He smiles, apparently satisfied with the explanation; “if all its infinite rooms are one room, this is a crummy corner of my labyrinth. Let’s find someplace with variety.”

As he says these words (zap!) you are transported to a wholly different maze.

Acceptance

When it was proclaimed that the Library contained all books, the first impression was one of extravagant happiness. All men felt themselves to be the masters of an intact and secret treasure. There was no personal or world problem whose eloquent solution did not exist in some [room].

The Library of Babel

In the interest of difference, the sorcerer introduces a new rule. At first you were to accept any set of instructions you could follow; now you are to reject unfollowable instructions, but also to object if the last instruction in a followable sequence doesn’t lead you to a room containing a MacGuffin.

Two rooms with the same doors—up to this point, indistinguishable—might now be different: perhaps one contains a MacGuffin and the other one does not. Moreover, two rooms which are indistinguishable to their occupant at a point in time (two rooms with the same doors, neither of which contains a MacGuffin) may be provably distinct because they have different positions relative to MacGuffin rooms in the maze’s topology.

As you explore these mazes, you’re struck by their insistence on their own size. If an infinite braid of rooms has a single MacGuffin in the hundredth rooms, the rooms before the MacGuffin can’t be summarized as a single room: one is just before the MacGuffin room; the room before that is two rooms before the MacGuffin; and so on. Even though they have the same doors, these rooms are clearly distinguishable.

Past the MacGuffin, though, you have no such information. You know there is a room after the MacGuffin, but since you will never encounter another MacGuffin you can never know whether there are rooms after that one (e.g. in an infinite braid) or whether it’s a single trick room with exits that lead you back into it.

Before this introduction of MacGuffins, in the language of state machines, every node was an acceptor—it was as if every room contained a MacGuffin. Now only certain nodes are acceptor states. If, after exhausting input, a state machine is an acceptor state, it “accepts” the input sequence.

State machine diagrams denote acceptors with double-walled circles (which is why the diagrams before this section have all had double-walled rooms: every room was an acceptor). Single-walled circles are not acceptors—these are the rooms we can pass through but don’t want to end in.

If this dynamic isn’t clear, take a moment to pretend to be the sorcerer. The room you’re in is colored cyan; you can use the 0 and 1 buttons to provide input (to select doors to take. The checkbox at the bottom indicates whether the state machine accepts the input: it’s checked when you’re in the acceptor state R₁, but not when you’re in any other state.

Significantly, these mazes can more finely restrict what instruction sequences they accept. Without these special MacGuffin rooms, any prefix of an acceptable instruction was itself an acceptable instruction; if less than every room contains a MacGuffin, that’s not necessarily the case! Before, every room was an acceptor, every state an acceptable terminal state. Now there are nonterminal states: valid instructions can take us through them, but can’t end there. Now we can design mazes where a prefix of a valid instruction sequence isn’t guaranteed to be acceptable:

Description	Diagram
Any nonempty binary string that begins and ends with the same digit. This accepts 1-0-0-0-1, but not 1-0-0-0.
Any binary string ending in 0-0. This accepts 1-1-1-0-0, but not 1-1-1 or 1-1-1-0.

As your understanding of the labyrinths deepens, your exploration with the sorcerer seems to accelerate, as if freed from ponderous existential questions. Your juvenile dread that the great labyrinth might be meaningless is supplanted by a vertigo of interpretations: a din of instructions, a nauseating race through passageway after passageway, MacGuffin and non-MacGuffin rooms, accepted and rejected sequences, and the blind sorcerer’s increasingly frenetic jumps (zap! zap! zap!) from one maze to the next.

Determinism

In all fictional works, each time a man is confronted with several alternatives, he chooses one and eliminates the others; in the fiction of the almost inextricable Ts’ui Pên, he chooses—simultaneously—all of them. He creates, in this way, diverse futures, diverse times which themselves also proliferate and fork.

The Garden of Forking Paths

That nausea is interrupted, suddenly, by a dilemma. In a new maze, you’re confronted with choice: one door is marked 0, and two doors are marked 1. When the sorcerer instructs you to pass through the door marked 1, through which door should you pass?

“You will take both doors,” explains the blind sorcerer. Your task is to find out whether the instructions lead you to a MacGuffin through either door. This puzzles you, but the sorcerer explains that there are a couple ways to take it literally:

1. Whenever you encounter several identical door, the sorcerer can conjure an avatar of you to pass through each door in parallel. If two avatars would meet in some room down the line, they are consolidated into one.

   This prospect deeply unsettles your sense of self (are you the avatar? or the original?), and the sorcerer admits it gives him migraines: conjuring avatars takes time and effort, and delivering simultaneous instructions to innumerable (and maybe ever-multiplying!) avatars is, he says, “a pain in the ass.”

2. You can pass through both doors by backtracking. When you choose one door over another identical one, note the decision; then, if the first door doesn’t lead you to accept the instructions, you can return to take the second door.

   This constant retracing, of course, takes time: you have to return to a room once for each identical door, and subsequent rooms can themselves have identical doors. Before, you would pass through at most n rooms to (in)validate a sequence of n instructions. Now you may need to pass through many more

You commit to backtracking (since, if you have to spend your existence trying to make sense of an infinite labyrinth for a mad sorcerer, you might as well feel existentially unique while you do it). The vertigo returns, but you have the kernel of an idea to eliminate the problem of choice.

These mazes—with several indistinguishable exits from a given room—are nondeterministic finite state machines (NFAs). They’re “nondeterministic” because your state at a given time isn’t totally determined by a set of instructions; you could be in several states at a given time, depending on which doors you chose. The two strategies proposed by the sorcerer correspond to two strategies available to a program implementing an NFA: they can evaluate possible states sequentially, or they can track multiple states in parallel. Both of these strategies are undesirable: you can have avatars in up to every room of a maze at once, which makes applying inputs burdensome. Regular expression implementations use NFAs; these dynamics are what make certain regular expressions inefficient.

You think, in all the time you now spend backtracking, about the avatars. Some number of avatars, in certain rooms in a finite maze, receive a certain instruction and at once spring into certain other rooms. In this process, some avatars will split, some will consolidate, and those for whom the instructions are unfollowable will blink out of existence.

It’s difficult to imagine the possible configurations of avatars in rooms because there are so many⁶, but a marvelous fact occurs to you: from the sorcerer’s perspective, a configuration of avatars behaves deterministically. If avatars are in some set of rooms, then after receiving a certain instruction they will be in a certain determinable second set of rooms regardless of how they traveled to that prior arrangement.

Is this passage from configuration to configuration really so different from you passing, deterministically, from one room to the next?

You interrupt the sorcerer a second time, and you make him an offer: for any finite maze confused with choice, you say, any maze burdened with identical doors, you can design for him a finite equivalent maze devoid of choice.

This is what the avatars reveal: every nondeterministic finite state machine is equivalent to some deterministic one!

Your proposal:

1. For every configuration of avatars in rooms in the nondeterministic maze, build a room in our new deterministic maze. If a configuration has an avatar in a room with a MacGuffin, then put a MacGuffin in the new room corresponding to that configuration.

2. For each configuration of avatars, consider each instruction that at least one avatar could validly follow (in other words, consider the set of door-labels the avatars see at once). For each instruction I:

   1. Figure out what every avatar would do if given this instruction: some move simply into another room, some split and move into several. This gives you a successor configuration.

   2. In the new deterministic maze, build a door out of the room corresponding to the initial configuration that leads to the successor configuration. Label it with the instruction I.

3. Some rooms in our new maze may not be reachable from the maze’s start. Demolish these; they’re superfluous.

Since we never repeatedly assess the same instruction applied to the same configuration of avatars, we will never build two doors in the same room of our new maze that have the same label. Thus, the new maze can be explored deterministically.

Since any configuration in the nondeterministic maze accepts the same instructions as its corresponding room in the deterministic one, we haven’t changed the followability of any instructions. Because every room with a MacGuffin in the new maze corresponds to a configuration in the nondeterministic maze where some avatar is in a room with a MacGuffin, the mazes make the same terminal judgements of followable sequences. They’re equivalent!

Of course, since there are so many possible configurations of avatars in mazes, the new deterministic maze may be considerably larger than the nondeterministic maze it models.

This algorithm—the powerset construction, adapted for our allegory—is best explained with an example. Consider the following nondeterministic finite maze, with rooms labeled A, B, and C:

Our first step is to plan out the rooms in the new maze, a finite state machine with one state for each possible configuration of avatars in the nondeterministic maze. We can use set notation to describe the arrangements of avatars:

• {C} is the state corresponding to the configuration with a single avatar in room C,
• {A, B} is the state corresponding to the configuration with an avatar in room A and another in room B,

and so on. Any state with an avatar in room C is an acceptor state, and at the start there is only one avatar (in room C). We can list out the seven states corresponding to the seven possible arrangements of avatars in the three-room maze:

Next, we need to consider the possible transitions out of each of these states. Thankfully this is a pretty simple maze: we only need to consider what happens to each of these states if the sorcerer delivers the instruction 0 or the instruction 1:

Finally, we prune the unreachable states and diagram our deterministic finite state machine. It’s worth taking a moment to compare it to the tables above: confirm that each of the acceptor states includes an avatar in room C; check that the state transitions correspond to those described in the instruction table.

This process lets us do away with all the complexity of avatars and backtracking, without changing which instructions are accepted and rejected, for any finite state machine, no matter how complex. You and the sorcerer can explore these deterministic mazes without any insufferable nondeterminisms; though this deterministic state machine looks nothing like the equivalent it models, exploring it is essentially exploring the collective experience of the avatars in their nondeterministic maze. For any arrangement the avatars would realize collectively, you reach a corresponding state.

If you need to convince yourself of this correspondence, you can use the interactive demo below to provide simultaneous inputs to the nondeterministic and deterministic equivalent state machines. Cyan nodes indicate the presence of an avatar in a room; note that the state of the deterministic machine always identifies the occupied rooms in the nondeterministic one.

Allegory

Augustine had written that Jesus is the straight path that saves us from the circular labyrinth followed by the impious; these Aurelian, laboriously trivial, compared with Ixion, with the liver of Prometheus, with Sisyphus, with the king of thebes who saw two suns, with stuttering, with parrots, with mirrors, with echoes, with the mules of a noria and with two-horned syllogisms. […] Like all those possessing a library, Aurelian was aware that he was guilty of not knowing his in its entirety; this controversy enabled him to fulfill his obligations to many books which seemed to reproach him for his neglect.

The Theologians

The sorcerer (Borges) and his mazes are an indulgent conceit for an explanation of state machines. For a reader really interested in the mathematical concepts, the comparison might confuse more than it makes clear: it may be harder to imagine yourself splitting into multiple indistinguishable avatars than it is to imagine a multi-node state, and so my explanations in this essay become less allegorical as the concepts become more disorienting.

I’m satisfied with my exploration of the correspondence between state machines and sequences, but the allegory says nothing about the “meaning of your hermitude” in the maze. To do so requires stepping back out of the diegetic “you” in the allegory, the little traveler in the labyrinth, and considering the you reading the allegory.

First, I can offer you a shallow meaning: state machines are useful tools for turning seemingly complex grammars or agents into simple, applicable programs. That’s how they were covered in my undergraduate computer science curriculum. It’s not a wrong justification—these applications are worthwhile—but it’s partial.

The other justification is to recognize that this essay is a reversal of work Borges has already done. His stories don’t discuss mathematics explicitly (they’d be worse—more gimmicky—if they did) but they rework topology and combinatorics into phenomenological and existential puzzles. I can explain topology via a phenomenological puzzle about a maze because Borges establishes, in various narrative guises, the structure of the allegory. Even if Borges hadn’t, at certain touchpoints the allegory is obvious. Topology connects intuitively to the everyday way one moves between physical spaces; surprising topological twists, like the equivalence of an infinite maze and a minimal one, correspond to uncanny views of the everyday.

Borges skillfully extends these allegories beyond their natural correspondences. The magic of A New Refutation of Time is that it imagines a kind of spatialized time, wherein two indistinguishable moments are ontologically one:

That pure representation of homogeneous objects—the night in serenity, a limpid little wall, the provincial scent of the honeysuckle, the elemental earth—is not merely identical to the one present on that corner so many years ago; it is, without resemblances or repetitions, the very same. Time, if we can intuitively grasp such an identity, is a delusion: the difference and inseparability of one moment belonging to its apparent past from another belonging to its apparent present is sufficient to disintegrate it.

This is precisely the same radical idealism that lets us say an infinite maze is a single room. If you prefer a philosophical connection, Borges treats the phenomenology of time the way Augé treats place.

Where does Borges’s labyrinth lead? To a dizzying metaphysics, as compelling as it is disconcerting. The Borgean maze is a trap, an entanglement of symbols and experiences, reflections and repetitions. I hope that following his allegories in the opposite direction—beginning with the existential allegory, but taking it as a point of departure into the mathematics Borges adapts but elides—has the opposite effect: mazes can be games, too. The trick is to enjoy them.