01
Finite automaton
finite state
regular languages
The machine remembers only which state it occupies. It is powerful enough for many pattern-recognition tasks but cannot count without bound.
Machine models · computability · complexity · proof
Computation Theory
Computation theory asks what an algorithm is, which problems algorithms can solve in principle, and how resource requirements separate easy computation from hard computation. The subject progresses from machine models to impossibility to complexity.
Theoretical spine
Change the question before changing the mathematics.
Automata theory asks what a chosen machine model can express. Computability asks whether any algorithm can solve a problem. Complexity keeps the problem computable and asks how expensive solving it must be.
Machine-power ladder · reference
Memory changes what patterns a machine can distinguish.
These models are not historical computer generations. They are mathematical abstractions designed to isolate how memory and control affect expressive power.
02
Pushdown automaton
one unbounded stack
context-free languages
Adding a stack makes nested structure possible: balanced delimiters and recursive syntax become recognizable in ways finite state alone cannot support.
03
Turing machine
unbounded read/write tape
general computation model
The model is intentionally simple but expressive enough to formalize the ordinary notion of an algorithm and expose problems no algorithm can decide.
Common proof moves
Theory often proves limits by translation rather than by trying every program.
01
Simulation
Show that one model can reproduce the behavior of another, establishing relative computational power.
02
Reduction
Translate one problem into another so a hypothetical solver for the target would also solve the source problem.
03
Counting & lower bounds
Prove that certain resources or distinctions are unavoidable rather than merely artifacts of a particular algorithm.
04
Diagonalization
Construct an object that escapes an assumed complete list, a classic route to impossibility and hierarchy results.