A **state space** is the set of all possible configurations of a system.^{[1]} It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.

For instance, the toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A “counter” system, where states are the natural numbers starting at 1 and are incremented over time^{[2]} has an infinite discrete state space. The angular position of an undamped pendulum^{[3]} is a continuous (and therefore infinite) state space.

Definition

In the theory of dynamical systems, a discrete system defined by a function *ƒ*, the state space of the system can be modeled as a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from *a* to *b* if and only if *ƒ*(*a*) = *b*.^{[4]} This is known as a state diagram.

For a continuous dynamical system defined by a function *ƒ*, the state space of the system is the image of *ƒ*.

State spaces are useful in computer science as a simple model of machines. Formally, a state space can be defined as a tuple [*N*, *A*, *S*, *G*] where:

*N*is a set of states*A*is a set of arcs connecting the states*S*is a nonempty subset of*N*that contains start states*G*is a nonempty subset of*N*that contains the goal states.

References

**^***Nykamp, Duane. “State space definition”. Math Insights. Retrieved 17 November 2019.*- ^ Jump up to:
^{a}^{b}*Papernick, Norman. “Infinite States and Infinite State Transitions”. Carnegie Mellon University. Retrieved 12 November 2019.* - ^ Jump up to:
^{a}^{b}^{c}*Nykamp, Duane. “The idea of a dynamical system”. Math Insights. Retrieved 12 November 2019.* **^***Laubenbacher, R. Pareigis, B. (2001). “Equivalence Relations on Finite Dynamical Systems”**(PDF)**. Advances in Applied Mathematics.***26**(3): 237–251. doi:10.1006/aama.2000.0717.**^***Zhang, Weixong (1999). State-space search: algorithms, complexity, extensions, and applications. Springer. ISBN 978-0-387-98832-0.*- ^ Jump up to:
^{a}^{b}^{c}*Abbeel, Pieter. “Lecture 2: Uninformed Search”. UC Berkeley CS188 Intro to AI. Retrieved 30 October 2019.* **^***Abbeel, Pieter. “Lecture 3: Informed Search”. UC Berkeley CS*