
State Machines
Erik Demaine introduces state machines as a tool for modeling how algorithms behave, part of MIT's 6.1200J Mathematics for Computer Science. The lecture defines the components of a state machine (states, start states, and transitions) and shows how to represent stepwise processes abstractly. Demaine then connects this new abstraction to induction, demonstrating how to prove invariant properties that hold across every reachable state of a machine. Examples work through how an algorithm's behavior can be tracked state by state, and how inductive proofs establish that certain properties persist no matter how many transitions occur. The session builds on earlier proof techniques from the course and sets up state machines as a recurring tool for later topics in discrete mathematics and computer science. Eighty-one minutes of blackboard-style instruction aimed at students already familiar with basic induction and proof writing.