turing-machines
2 free lessons tagged turing-machines 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.
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.