skills grow you’ll find that finite state machines provide a solid backbone
with which you can combine other techniques such as fuzzy logic or neural
networks.
What Exactly Is a Finite State Machine?
Historically, a finite state machine is a rigidly formalized device used by
mathematicians to solve problems. The most famous finite state machine is
probably Alan Turing’s hypothetical device: the Turing machine, which he
wrote about in his 1936 paper, “On Computable Numbers.” This was a
machine presaging modernday programmable computers that could per

form any logical operation by reading, writing, and erasing symbols on an
infinitely long strip of tape. Fortunately, as AI programmers, we can forgo
the formal mathematical definition of a finite state machine; a descriptive
one will suffice:
A finite state machine is a device, or a model of a device, which has a
finite number of states it can be in at any given time and can operate on
input to either make transitions from one state to another or to cause an
output or action to take place. A finite state machine can only be in one
state at any moment in time.
The idea behind a finite state machine, therefore, is to decompose an
object’s behavior into easily manageable “chunks” or states. The light
switch on your wall, for example, is a very simple finite state machine. It
has two states: on and off. Transitions between states are made by the input
of your finger. By flicking the switch up it makes the transition from off to
on, and by flicking the switch down it makes the transition from on to off.
There is no output or action associated with the off state (unless you con

sider the bulb being off as an action), but when it is in the on state
electricity is allowed to flow through the switch and light up your room via
the filament in a lightbulb. See Figure 2.1.
44  Chapter 2
What Exactly Is a Finite State Machine?
Figure 2.1. A light switch is a finite state machine. (Note that the switches are reversed
in Europe and many other parts of the world.)