Finite-state machine

There are many calculations or other processes that can be described using a specific series of states or conditions. For example, the state of a combination lock depends not only on what numeral is being dialed or punched at the moment, but on the numbers that have been previously entered. An even simpler example is a counter (such as a car odometer), whose next output is equal to one increment plus its cur-rent setting. In other words, a state-based device has an inherent “memory” of previous steps.

In computing, a program can be set up so that each possible input, when combined with the current state, will result in a specified output. That output becomes the new state of the machine. (Alternatively, the machine can be set so that only the current state determines the output, without regard to the previous state.) This is supported by the underlying structure of the logic switching within computer circuits as well as the “statefulness” of all cal-culations. (Given n, n+1 is defined, and so on.) Alan Tur-ing showed that combining the state mechanism with an infinite memory (conceptualized as an endless roll of tape) amounted to a universal computer—that is, a mechanism that could perform any valid calculation, given enough time (see Turing, Alan). The idea of the sequential (or state) machine is closely related to automata, which are entities whose behavior is controlled by a state table. The interaction of such automata can produce astonishingly complex patterns (see cellular automata).

Applications

Many programs and operating systems are structured as an endless loop where an input (or command) is processed, the results returned, the next input is processed, and so on, until an exit command is received. A mode or state can be used to determine the system’s activity. For example, a program might be in different modes such as waiting for input, processing input, displaying results, and so on. The program logic will refer to the current state to determine what to do next and at some point the logic will transition the system to the next state in the sequence. The validity of some kinds of programs, protocols, or circuits can therefore be proven by showing that there is an equivalent finite-state machine—and thus that all possible combinations of inputs have been accounted for.

Finite-state machines have many other interesting appli-cations. Simple organisms can be modeled as a set of states that interact with the environment (see artificial life). The lower-level functions of robots can also be represented as a set of interacting finite-state machines. Even video game characters often use FSMs to give them a repertoire of plausible behavior.