Finite State Machine

Finite State Machine (FSM) is the correct theoretical model of every actual digital computer — not the Turing machine with its infinite tape, but a system with a finite number of internal states that transitions between them based on inputs and its current state. The FSM captures what digital hardware actually does: memory is finite, time is discrete, and the next state is a determinate function of the present state and the present input.

The gap between the FSM and the Turing machine is the gap between engineering and mathematics. A Turing machine can compute anything computable given infinite resources. A finite state machine can compute only regular languages — the simplest class in the Chomsky hierarchy. Every real computer is an FSM, yet every real computer simulates Turing-complete behavior by using external storage (disks, networks, human operators) to approximate the infinite tape. The approximation is good enough that we treat computers as universal, but the physical reality is always finite.

This matters for understanding the limits of embedded systems, control circuits, and hardware verification. A microprocessor with n bits of internal state has exactly 2^n possible configurations. That number may be astronomical, but it is not infinite. The FSM model makes this finitude explicit and tractable, where the Turing model hides it behind an abstraction.