The Reachable Set: A Unified Concept of Possibility

What are the absolute limits of what a system can do? Whether steering a spacecraft, designing a computer chip, or programming a living cell, understanding the boundaries of possibility is a central challenge in science and engineering. The answer lies in a profound and unifying concept: the reachable set. This is the complete collection of all states a system can possibly get to, given its starting point, its rules of evolution, and the controls at its disposal. This article addresses the fundamental need for a formal framework to analyze and predict the behavior of dynamic systems.

Across the following sections, we will embark on a journey to understand this powerful idea. In the "Principles and Mechanisms" chapter, we will build the concept from the ground up, starting with the discrete logic of simple computers and progressing to the smooth motion of physical systems described by differential equations. We will uncover the mathematical tools that allow us to precisely define and calculate these sets. Then, in "Applications and Interdisciplinary Connections," we will witness the reachable set in action, seeing how it provides a common lens to ensure the safety of digital hardware, enable the control of rockets, describe the strange possibilities of quantum mechanics, and navigate the uncertainty of synthetic biology.

Imagine you're playing a video game. Your character stands at a starting point, and you have a set of moves—run, jump, use an item. The "reachable set" is the collection of all the spots on the map you can possibly get to, given your abilities and the time you have. It's a simple idea, but it turns out to be one of the most profound and unifying concepts in science and engineering. It's the key to understanding everything from the logic of a computer chip to the steering of a spacecraft. Let's embark on a journey to understand this concept, starting with the simplest of worlds and gradually moving to the complex reality we inhabit.

Let's begin not with a spacecraft, but with a much more abstract machine, a kind of simple-minded computer called a ​​Nondeterministic Finite Automaton​​ (NFA). Think of it as a board game with a token on a set of squares, say $\{q_0, q_1, q_2, \dots\}$. The rules, given by a "transition function" $\delta$, tell you where you can move your token. For example, from square $q_0$ on input 'a', the rules might let you move to either $q_1$ or $q_2$.

This "either/or" is the heart of nondeterminism. After that first move, where is your token? It's not in one place; it's in a cloud of possibilities. The state of our game is no longer a single square, but a set of squares. If we start at $q_0$ and the input is 'a', our new state is the set $\{q_1, q_2\}$.

What happens on the next move? Suppose the input is 'b'. We look at every square in our current set of possibilities and see where 'b' can take us. Maybe from $q_1$, 'b' leads to $\{q_3\}$, and from $q_2$, 'b' leads to $\{q_2, q_4\}$. To get the new cloud of possibilities, we simply pool all these outcomes together. The union of $\{q_3\}$ and $\{q_2, q_4\}$ is $\{q_2, q_3, q_4\}$. So, after the input string "ab", the set of states our machine could possibly be in—its reachable set—is $\{q_2, q_3, q_4\}$. This process of tracking the "cloud of possibilities" is the most basic form of reachability analysis.

This idea is so powerful that we can build a whole new game from it. Imagine a new, bigger board where each "square" is one of these sets of possibilities. For our NFA, we'd have squares labeled $\{q_0\}$, $\{q_1, q_2\}$, $\{q_2, q_3, q_4\}$, and so on. A move in this new game, say from the square $\{q_1, q_2\}$ with input 'b', takes you deterministically to the single square $\{q_2, q_3, q_4\}$. This process, known as ​​subset construction​​, creates a completely deterministic machine (a DFA) that is equivalent to the original nondeterministic one. The states of this new, deterministic machine are the reachable sets of the old one. This is a beautiful piece of intellectual judo: the very notion we invented to track possibilities becomes the fundamental building block of a new, more structured reality. We've formalized our thinking about reachability into a concrete mathematical object.

So far, we've asked "where can we get after a specific sequence of inputs?" But a more interesting question is, "what are all the states that are reachable by any possible sequence of inputs?" How do we find this ultimate reachable set?

We can't possibly test every infinite sequence of moves. Instead, we can be clever and perform an iterative search. This is precisely how engineers perform ​​formal verification​​ to prove that a computer chip design is free of bugs. They model the chip as a giant state machine and try to determine if any "bad" state (like one representing a crash) is reachable from the initial state.

The algorithm is wonderfully simple.

1. Start with a set of known reachable states, which initially contains only the starting state, let's call this set $\chi_0$.
2. In each step, find all the new states you can get to in one move from any state currently in your known set. Let's call the operator that does this $Img(\cdot)$.
3. Add these newly discovered states to your set. The new set of reachable states, $\chi_{k+1}$, is the old set $\chi_k$ combined with the newly imaged states, $Img(\chi_k)$.

This gives a recurrence relation: $\chi_{k+1} = \chi_k \cup Img(\chi_k)$.

You repeat this process. The set of known reachable states grows, like an inkblot spreading on paper. Since the total number of states in our machine is finite, this process can't go on forever. Eventually, a step will come where $Img(\chi_k)$ only produces states that are already in $\chi_k$. At this point, the set stops growing; it has saturated. We have found the complete set of all reachable states.

The reason this algorithm is guaranteed to terminate so cleanly lies in a fundamental property of the "union" operation: idempotency. This fancy word hides a trivial truth: adding something to a set that is already there doesn't change the set ($A \cup A = A$). When our search re-discovers a state, it doesn't add a duplicate or cause our set to grow. This simple fact prevents the algorithm from running in circles and ensures it efficiently finds every nook and cranny of the state space that is possible to reach.

Now, let's leave the discrete world of board games and computer logic and enter the continuous world of physics and motion. Instead of discrete inputs like 'a' and 'b', we have control signals that vary smoothly in time, like the pressure on a car's accelerator or the voltage to an electric motor. The system's state—its position, velocity, temperature—evolves not in jumps, but along a smooth trajectory.

A vast number of such systems, from satellites to chemical reactors, can be described by a linear equation:

Here, $x(t)$ is the state vector (a list of numbers describing the system's condition). The term $A x(t)$ represents the system's natural dynamics—how it would "drift" on its own if left untouched. The term $B u(t)$ represents our control action—how we "push" or "steer" the system using our input $u(t)$.

The question remains the same: starting from rest ($x(0)=0$), what states can we reach? The answer is given by a beautiful formula, an integral that sums up the effect of all our pushes over time:

This looks intimidating, but the intuition is straightforward. At each moment $\tau$ in the past, we gave the system a little "kick" equal to $B u(\tau) d\tau$. The term $e^{A(T-\tau)}$ is the ​​state transition matrix​​, which describes how that little kick, made at time $\tau$, evolves and propagates through the system's natural dynamics to contribute to the final state at time $T$. The integral simply adds up all these propagated effects from time $0$ to $T$.

The set of all states $x(T)$ we can form this way is the reachable set. For these linear systems, this set has a remarkable structure: it's not just some arbitrary blob in space, it's a perfect, flat ​​vector subspace​​. This means if you can reach state $x_1$ and you can reach state $x_2$, you can also reach any combination like $\alpha x_1 + \beta x_2$. This is a direct and profound consequence of the system's linearity. This special subspace is called the ​​controllable subspace​​.

The integral formula is elegant, but calculating it for every possible input function $u(t)$ is impossible. It defines the space, but it doesn't give us an easy way to describe it. It's like knowing there's a treasure chest, but having no key. Miraculously, for these systems, there is a key—a purely algebraic one that requires no integration at all.

The entire controllable subspace is given by the column space of a single matrix, the ​​controllability matrix​​:

This result, known as the ​​Kalman rank condition​​, is one of the crown jewels of modern control theory. The intuition is this: the columns of $B$ represent the directions we can push the system directly. The columns of $AB$ represent the directions we can move in by applying a push and letting the system's natural dynamics $A$ act for an instant. The columns of $A^2B$ are where we can get by letting it drift for another instant, and so on. The famous Cayley-Hamilton theorem from linear algebra guarantees that we don't need to look at any powers of $A$ higher than $n-1$, where $n$ is the number of state variables. The span of all these column vectors gives every possible direction we can steer the system.

Let's see this key in action. Consider a simple satellite whose state is described by three variables. Its dynamics are given by specific $A$ and $B$ matrices. By simply calculating the vectors $B$, $AB$, and $A^2B$, we might find that the third vector, $A^2B$, is just a linear combination of the first two. This means we only have two independent directions we can steer in. The controllable subspace—the set of all reachable states—is not the full 3D space but a 2D plane embedded within it. There are certain states, lying off this plane, that are fundamentally unreachable, no matter how long or how cleverly we apply our controls. This algebraic test gives us immediate, powerful geometric insight into a system's physical limitations.

Even more amazingly, for these continuous-time systems, time itself has a strange flexibility. If a state is reachable at all, it can be reached in any finite amount of time $T > 0$, be it a millisecond or a year. This is a superpower granted by the smoothness of continuous dynamics, a stark contrast to the discrete world where reaching a distant state naturally requires more steps.

So far, we've lived in a physicist's dream world of "unconstrained" controls, where we can command infinite power if needed. This is what gives us the perfect, infinite structure of a vector subspace. But in the real world, every engine has a maximum thrust, every power supply a maximum voltage. Our control inputs are bounded: $\|u(t)\| \le u_{\max}$.

What does this do to our reachable set? The effect is dramatic. The reachable set is no longer an infinite subspace but a ​​bounded, closed set​​ in the state space. We can no longer travel infinitely far in any controllable direction.

The simplest example is a toy system, the scalar integrator $\dot{x} = u$, with a control bound $|u(t)| \le u_{\max}$. The reachable states at time $T$ are simply the interval $[-u_{\max}T, u_{\max}T]$. The size of this reachable interval depends directly on our control authority ($u_{\max}$) and the time we have ($T$). Double the time or double the power, and you double the reach. For more complex systems like the double integrator (modeling position and velocity), the shape of the reachable set is no longer a simple box but a more subtle, curved shape, whose boundaries are traced out by the most extreme control strategies.

If the system has natural dynamics that are stable (it tends to return to the origin on its own), the effect is even more pronounced. Even with infinite time, the set of states reachable with bounded controls remains a bounded set. The system's inherent stability acts as a tether, constantly pulling back against our efforts to push it away from the origin.

The concept of the reachable set is a grand canvas, and we can add a few final, elegant details to complete the picture.

What if we don't start at the origin, but at some initial state $x_0$? The linearity of the system leads to a beautiful separation. The set of states reachable at time $T$ is simply the controllable subspace we already found, but translated through space. The translation vector is precisely where the system would have drifted on its own, $\Phi(T,0)x_0$, had we never applied any control at all. The reachable set becomes an ​​affine subspace​​: $\{ \Phi(T,0)x_0 + W \}$, where $W$ is the controllable subspace from the origin.

We've focused on "reachability"—getting from the origin. What about "controllability"—getting to the origin? For continuous-time linear systems, it turns out that these two concepts are equivalent. The set of states that can be driven to the origin is exactly the same as the set of states that can be reached from the origin. This elegant symmetry is not a given; it's a special property of this class of systems.

Finally, reaching a state isn't just a yes-or-no question; it comes at a cost. We can ask, "What is the cheapest way to get there?" For linear systems, we can define a "cost" as the total energy of the control signal, $\int_0^T \|u(t)\|^2 dt$. The same mathematical machinery that tells us if a state is reachable, via a structure called the ​​controllability Gramian​​, can also give us the exact control signal that gets us to our target state with the minimum possible energy. The geometry of the reachable set is thus intimately linked to the economics of control.

From the logical paths of an NFA to the bounded future of a spacecraft, the reachable set provides a unified language for describing the realm of the possible. It is a concept that is at once a practical tool for engineers, a source of deep theorems for mathematicians, and a powerful metaphor for understanding the constraints and opportunities that govern any dynamic system. It is, in short, the shape of what can be.

Now that we have grappled with the principles of what it means for a state to be reachable, we can embark on the real adventure: seeing this idea at play across the vast landscape of science and engineering. Like any truly fundamental concept, the "reachable set" is not a sterile definition to be memorized; it is a powerful lens. By looking through it, we can ask new questions and find surprising connections in fields that, at first glance, seem to have nothing to do with one another. Our journey will take us from the logical heart of a computer chip to the delicate dance of a quantum particle, and finally to the probabilistic world of engineered life itself.

Let us begin in the world of computation, a realm built from pure logic. When a programmer designs a system, perhaps a simple parser for a command-line tool, one of the first and most fundamental questions to ask is: "Does this thing even work?" A more precise version of this question is, "Is it possible for this machine to accept any input at all?" If the answer is no, the machine is useless. The concept of reachability gives us a precise way to answer this. Imagine the machine's possible configurations as a map of islands (the states). We start on a specific island, the initial state. The machine is useful only if there is a path from our starting island to at least one of the "treasure" islands, the accepting states. If the set of islands we can reach, $R(q_0)$, has no overlap with the set of treasure islands, $F$—that is, if $R(q_0) \cap F = \emptyset$—then we know our machine's language is empty. It's a beautiful, clean test for basic functionality.

Once we know a system can do something, the next question is, "What are all the things it can do?" To answer this, we must map out the entire territory of reachable states. For a system with a handful of states, like a simple Nondeterministic Finite Automaton (NFA), this is a straightforward exploration. We can start at the initial state and systematically follow every possible path, like a spider exploring every strand of its web, until we have identified every state that can possibly be reached.

This exploration is not just an academic exercise. It is a matter of life and death for safety-critical systems. Consider a digital counter in a satellite. Most of the time, it happily cycles through its designed sequence of states, the "main operational cycle." But what happens if a stray cosmic ray strikes the hardware, flipping a bit and throwing the counter into an "unused" or "illegal" state? Will it be trapped forever in a digital purgatory, unable to get back to its job? Or is there a path back home? A system that can always recover is called "lock-up-free." This crucial safety property can be defined perfectly using our concept: a counter is lock-up-free if and only if for every unused state $u$, the set of states reachable from $u$ has a non-empty intersection with the main cycle $C$. Reachability analysis here becomes a tool for building resilient and reliable machines.

Of course, modern microprocessors have more states than there are atoms in the known universe; we could never explore them one by one. Here, the idea of a reachable set forces us to make a brilliant leap of abstraction. Instead of thinking about individual states, we can think about vast sets of states, described by logical formulas. With this symbolic approach, we can ask: if we are currently in a set of states $C(s)$, what is the set of all states we can reach in the very next step? The answer is captured in a single, elegant expression: $N(s') = \exists s . (C(s) \wedge T(s, s'))$, where $T(s, s')$ represents the transition rules. This formula, used in a technique involving Binary Decision Diagrams, allows engineers to verify the behavior of billions upon billions of states simultaneously, proving that a chip design is free from lock-up and other critical flaws. It is a spectacular example of how a simple concept, when combined with the power of logic, allows us to reason about systems of unimaginable complexity.

So far, we have lived in the abstract world of bits and logic. But what happens when the "states" are not just memory locations, but the physical position and velocity of a rocket, a robot, or a chemical reaction? This brings us to the magnificent field of control theory. Here, the idea of the reachable set is given a new name: ​​controllability​​.

Imagine a simple object, like a hockey puck on a frictionless sheet of ice. Its state can be described by two numbers: its position $x_1$ and its velocity $x_2$. We can apply a force $u(t)$ to it. Starting from rest at the origin, $(x_1, x_2) = (0, 0)$, where can we get? Can we reach any desired position with any desired velocity, just by carefully applying our pushes and pulls? It turns out that for this simple system, the answer is yes. By choosing the right control input $u(t)$ over some time interval, we can steer the puck to any state in the plane. The set of reachable states is the entire state space. The system is said to be completely controllable.

For more complex systems, like a multi-jointed robotic arm or a power grid, how do we determine the reachable set? We need a more powerful mathematical tool. This tool is the ​​controllability Gramian​​, $W_c$. You can think of the Gramian as a mathematical object that absorbs all the information about how our control inputs influence the system's state over a period of time. It measures the "reach" of our inputs in every possible direction of the state space. The set of all states reachable from the origin is nothing more than the column space (or image) of this Gramian matrix. If the Gramian is invertible (or, more formally, positive definite), it means our controls have influence in every direction, and we can reach any state we choose. Controllability is no longer a mystery; it is a property we can calculate.

And the story gets even better. Once we know a state is reachable, the Gramian also tells us the best way to get there. If we want to move our system from an initial state $x_0$ to a final state $x_f$, there might be infinitely many control strategies to do it. Which one is the most efficient, using the least amount of fuel or energy? The theory provides a stunningly explicit answer: the optimal, minimum-energy control is constructed directly using the inverse of the Gramian. The very tool that tells us if we can get there also gives us the most elegant map for the journey.

Armed with this unified view of reachability, let us push into the frontiers of modern science, where the states and rules become even more exotic.

The Quantum Dance

Let’s shrink our perspective from a hockey puck to a single quantum bit, or qubit. The state of a qubit can be visualized as a point on the surface of a sphere, the so-called Bloch sphere. Our "controls" are now carefully timed laser or microwave pulses. Suppose we start at the "north pole" of the sphere, representing the state $|0\rangle$. If our control fields have a limited maximum strength $\Omega$, where can we get in a given amount of time $T$? Using the tools of optimal control, one finds a beautiful result: the set of reachable states is a perfect ​​spherical cap​​ centered at the north pole. The longer we let the system evolve, or the stronger our controls, the larger this cap grows, eventually enveloping the entire sphere. The boundary of what is possible is traced out by the most efficient paths—the quantum equivalent of straight lines on the sphere. Here, the reachable set is a concept with tangible, geometric beauty.

Now, consider building a quantum computer. We don't have infinitely variable control pulses. Instead, we have a discrete set of fundamental operations, or "gates," like the Hadamard (H) and T gates. Starting from $|0\rangle$, can we apply a finite sequence of these gates to reach any point on the Bloch sphere? The answer is one of the most profound and subtle ideas in quantum information. The set of states we can reach exactly is only a countable collection of points. Yet—and this is the miraculous part—this countable set is ​​dense​​ on the sphere. This means that for any target state you can imagine, there is an exactly reachable state that is arbitrarily, infinitesimally close to it. We may not be able to hit every bullseye exactly, but we can get as close as we desire. The set of reachable states, though full of "holes," is rich enough for universal approximation, which is the foundation of all quantum algorithms.

The Hidden Symmetries of Reachability

Let's take a brief detour back to a discrete system, but view it through the lens of abstract algebra. Consider a device with two modular counters, whose state is advanced by a few specific operations. One might expect the set of reachable states to be a somewhat random scattering of points within the total state space. But the reality is far more elegant. Because the operations combine according to the rules of modular arithmetic, the set of all reachable states forms a clean mathematical structure: a ​​subgroup​​ of the larger group of all possible states. The concept of reachability uncovers a hidden algebraic symmetry, revealing that the system's dynamics are far more orderly than they might first appear.

Engineering Life

Our final journey takes us to the messiest, most complex, and most fascinating frontier of all: synthetic biology. Here, we attempt to engineer circuits not with silicon and wires, but with DNA, proteins, and living cells. Everything is noisy, stochastic, and uncertain.

Imagine we build a synthetic memory device inside a cell using two molecular switches. One switch flips a promoter between ON and OFF, and the other irreversibly removes a "stop" sign for transcription. We use chemical inputs to try to flip these switches to a desired configuration. However, these biological parts are imperfect. They are "leaky," meaning a switch might flip on its own, or they might fail to respond to our input signal.

What is the reachable set here? The question itself must change. It is no longer "Can this state be reached?" but rather, "With what ​​probability​​ can this state be reached?" The reachable set becomes the collection of all possible final configurations that have a non-zero probability of occurring. By meticulously accounting for the probability of the intended events and all the possible failure modes—the induced actions, the leaky background activities—we can calculate the precise probability of ending up in our desired target state, and consequently, the overall error rate of our biological device.

From the clean logic of a DFA to the noisy reality of a living cell, the concept of the reachable set proves its incredible versatility. It provides a universal framework for analyzing what is possible, for ensuring safety, for optimizing control, and for designing systems in the face of uncertainty. It is a simple question—"Where can I get from here?"—whose echoes are heard across all of science.