Configuration graph

The model explains both what is an initial configuration of the machine and which steps can be taken to continue the computation, until we eventually stop.

A configuration, also called an instantaneous description (ID), is a finite representation of the machine at a given time.

For example, for a finite automata and a given input, the configuration will be the current state and the number of read letters, for a Turing machine it will be the state, the content of the tape and the position of the head.

If there exists exactly one initial state, then a computation is deterministic if and only if from any configuration there is at most one possible step, so if and only if the graph is of out-degree 1.

A cycle in the graph corresponds to an infinite loop in the computation.

[1] In the other direction, it helps to verify the complexity of a computation model; the decision problem for a (deterministic) model whose configurations are of space which is logarithmic in the size of the input is in (L) NL.