A computation can be described at several levels. Source code is one representation, but the underlying process can also be modeled mathematically as states and rules for moving between them.

State machines

A state machine has a current state and a set of transitions. Each transition describes how an input or condition changes the current state.

For example, a simple turnstile might have two states:

locked --coin--> unlocked
unlocked --push--> locked

The model ignores physical details and keeps only the information needed to describe behavior.

Functions as computation

Some computations can be viewed as mathematical functions mapping inputs to outputs. Other programs are naturally stateful or interactive and cannot be understood only from one final return value.

Different models, shared questions

Programming languages, finite-state machines, lambda calculus and Turing machines use different primitives, but all provide ways to describe processes precisely.

They let us ask questions that are independent of a particular processor or programming syntax: what can be computed, how much state is required, whether a process terminates and whether two procedures express the same behavior.

Models of computation separate the essence of a computational process from the particular machine or language used to implement it.