The theory of computation, made visible.
From finite automata to the P versus NP question — learn the mathematics of what computers can and cannot do, through interactive machines you can run yourself.
Automaton simulator
Build DFAs and NFAs, then step through any input and watch states light up.
Turing machine
Drive a head across an infinite tape and see real computation unfold.
Pumping & regex labs
Pump strings to prove non-regularity and test live regular expressions.
Three parts, one journey
Automata & Languages
Finite automata, regular expressions, and context-free grammars.
Mathematical Foundations
The vocabulary the whole theory is written in: sets, sequences, functions, relations, graphs — and the handful of proof techniques used everywhere.
OpenFinite Automata
The simplest model of computation: a machine with finitely many states that reads input one symbol at a time.
OpenNondeterminism
Allow a machine to be in several states at once. NFAs are no more powerful than DFAs — but far easier to design.
OpenRegular Expressions
A compact algebra for describing languages. Kleene’s theorem: regular expressions and finite automata describe exactly the same class.
OpenDFA Minimization
Every regular language has a unique smallest DFA. Partition refinement finds it by merging states no string can tell apart.
OpenNonregular Languages
Some languages need unbounded memory. The pumping lemma is our tool for proving a language is not regular.
OpenContext-Free Languages
Grammars with recursive structure. They power programming-language parsers and describe nested, balanced patterns.
OpenComputability Theory
Turing machines, decidability, and the limits of computation.
Turing Machines
The definitive model of computation. An infinite tape and a head that reads, writes, and moves — the basis of the Church–Turing thesis.
OpenDecidability
Which problems can a computer solve at all? Diagonalization reveals languages no machine can decide.
OpenReducibility
The central technique for spreading undecidability: if solving B would let us solve a known-hard A, then B is hard too.
OpenAdvanced Computability
Self-reference made rigorous: machines that print themselves, and an absolute notion of information content.
OpenComplexity Theory
Time, space, P vs NP, and the geography of hardness.
Time Complexity
Not just what is computable, but what is feasible. The classes P and NP, and the most famous open problem in computer science.
OpenSpace Complexity
Measure memory instead of time. Space can be reused, which leads to surprising results like PSPACE = NPSPACE.
OpenIntractability
Problems we can prove are genuinely hard. The hierarchy theorems guarantee that more time and space really do buy more power.
OpenReady to compute?
Start with the simplest machine there is and work your way up to the deepest open question in computer science.
Begin the course