What Is Computation?

Tape, head and rules

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 Turing machine has a tape, a head, a state, and a table of rules.
• Each rule says what to write, which way to move, and the next state.
• Simple rules can carry out arithmetic.

Steps

1. Hilbert’s challenge
2. Adding one
3. Run it in your head
4. Counting steps
5. States are memory
6. What does it compute?