Machines Without Memory

Finite automata

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A finite automaton reads input once, left to right, with a fixed number of states.
• Remainders make good states: divisibility by m needs m states (or fewer).
• Finite memory can’t count without limit, so balanced brackets are out of reach.

Steps

1. A Turing machine with no tape
2. Divisible by three?
3. Follow the arrows
4. Build it yourself
5. What they can’t do
6. Multiples of four