Contents > Abstract Machines > State Machine

Sequencer

The simplest state machine is a sequencer, a device that generates the next element of a sequence when prompted. A classic example is a traffic light, a sequencer prompted by a timer. Another example is a linear-feedback shift register, such as the one that serves as the pseudorandom number generator in a Tetris implementation described in a subsequent section. It is a sequencer prompted when a piece spawns.

The infinite array abstract permits a straightforward implementation of a sequencer. The first N bytes of the array, a0‥aN−1, serve as an N-byte register, where a subset or all those bytes store the most recently generated element of the sequence. A process initializes the register to a starting value. When the process wants the next element of the sequence, it runs an MC program equivalent to the single line of pseudocode below.

a0‥aN−1 ← Ts(a0‥aN−1)

The program passes the register value into a transition function, Ts, and it puts the result back into the register.

Since the register is limited to a finite number of values, the generated sequence eventually becomes cyclic.