theory-of-computation
4 free lessons tagged theory-of-computation across Computer Science. Each one is a short sequence of focused steps with narration and a five-question quiz at the end — take them in any order, no signup required.
What Undecidability Costs Real Tools
Rice's theorem closes every interesting question a type checker, linter or verifier wants to answer, yet those tools exist and work. They work by choosing which way to be wrong. This lesson covers the sound and unsound bargains, the provable approximation in pointer analysis, and the option of leaving Turing completeness behind on purpose.
The Halting Problem and the Shape of the Proof
Once memory stops being the constraint, a different kind of limit appears. No program can decide whether an arbitrary program halts, and the proof fits in eight lines. This lesson builds that argument, separates deciding from merely recognising, and shows how one impossibility result propagates to every other question worth asking.
Adding a Stack, Then a Tape
Finite memory fails on anything that must be counted, so add memory and watch what each purchase buys. A stack buys nesting and nothing more. An unbounded tape buys everything, and two entirely different formalisms invented in the same year turn out to buy exactly the same thing.
Finite Memory and What It Cannot Recognise
A machine with a fixed number of states can recognise a surprising amount, and then hits a wall that no amount of cleverness moves. This lesson builds the finite automaton, shows that regular expressions are the same thing in different notation, and proves by counting that balanced parentheses are out of reach.