A state machine is a simple mathematical model. It is a fundamental and ubiquitous model in Computer Science. A computer is nothing but a state machine. It has registers and memory (state) which contain values that change over time as its operations are executed (state transitions). A programming language is a way to describe a class of state machines. A program written in that programming language is a description of a state machine. The execution of that program corresponds to an execution of the state machine it describes.

A software system is a very, very complicated state machine. One thing that makes it complicated is its size: there is usually an infinite number of states, an infinite number of state transitions, an infinite number of executions, and each execution may possibly be infinite (not terminate). If everything were finite and not very large, we could probably reason about the behavior of the software system entirely in our heads. But since the real world is not so small and manageable, we need to find ways to model, describe, and reason about these large things in terms of a finite and small(er) number of small things.

One purpose of this course is to tell you about some of these ways of
managing complexity. There are three themes we will visit and revisit:
*notation*, *abstraction*, and *modularization*. With the
appropriate notation, using abstraction and modularization
(composition and decomposition) techniques, you will be able to model
and reason about complex software systems. But remember, as with any
mathematical model, you will be able to discuss only those things that
that model models. If a state machine doesn't let you model the cost
of the system, then you won't be able to reason about how expensive or
cheap it will be to build.

Mon Mar 18 13:45:16 EST 1996