This section is about developing a better understanding of computing as a symbolic process spanning time. This will specifically explore the idea of the finite state machine as a representation of a process with history which can model an external process. In the context of physical computing, this will assist in conceiving of programs which generate more complex time behavior, or which can discover and represent some information about the world outside the computer.
A Finite-state Machine is an abstract model of computing which assumes the machine exists in one of a finite set of states, with transition rules governing under what conditions the machine moves from the current state to a successor state.
Finite-state machines are frequently illustrated as a directed graph of state nodes linked by transition edges. Conceptually, the machine has one active node (the current state), which has rules for each edge defining when the active state transitions to another state. States can have self-transitions which return to the same state for a particular input. States can be final states if there are no edges leaving the state to another state; the machine will not leave this state once it is reached.
Every computer has finite memory and thus can be theoretically described as a single finite-state machine, however this is not generally useful. Even an Arduino UNO with 2K SRAM has at minimum 216384 states (about 104932); only an infinitesmal fraction of these (approx. 10-4907) could be achieved in the lifetime of the universe.
Finite-state machines can practically be used to describe certain types of parsers, protocols, interpreters, user interfaces, and simple world models.
The idea of state is very powerful in that it encapsulates all history of a system. This is closely related to the control-theory notion of the state vector. In both cases, the idea is that the state of a system captures enough information that all future behavior can be predicted given the inputs. Put another way, all past inputs and behavior is captured in the set of variables comprising the state vector.
The lab exercises are intended to be performed by pairs of students. The exercises will be performed in the lab during class time, but also outside class as needed. The lab exercises are not graded but are essential for developing the vocabulary and skills to fulfill the graded assignments.
Any one who completes the basic exercises should consider undertaking some of the optional challenge exercises.
Inspiration for project ideas can be found on the course website.