⚙️What is Computation?
How simple rules can create complex behavior
Take your time with this one. The interactive parts are here to help you test the idea, not rush through it.
Pause and experiment as you go.
Before We Begin
What we are learning today
The Turing machine is not important because anyone builds computers this way today. It matters because it strips computation down to its bare essentials: read a symbol, follow a rule, write a new symbol, move, and repeat. Once students understand that loop, programming stops feeling magical and starts feeling mechanical in the best possible way.
How this lesson fits
This module builds the mental model underneath everything else in the curriculum. We start with explicit rules, then add uncertainty, then explore search, so students can see AI as a chain of concrete decisions rather than a pile of mysterious buzzwords.
The big question
How can a machine move from rigid step-by-step instructions to making sensible choices in a messy, uncertain world?
Why You Should Care
This lesson gives students a clean answer to a foundational question: what does it actually mean for a computer to compute? It shows that sophisticated output can emerge from extremely small local actions, which is a theme that keeps returning throughout AI.
Where this is used today
- ✓Regular-expression engines and pattern matchers that scan text for structured strings
- ✓Compiler design, where high-level code is broken into small symbolic steps a machine can execute
- ✓Theory of computation, which proves the kinds of problems computers can and cannot solve
Think of it like this
Picture a student standing beside an endless roll of paper with a tiny instruction card in hand. They can only inspect one square at a time, but the rule card tells them exactly what to write and where to move next. That is enough to create surprisingly rich behavior, just very slowly.
Easy mistake to make
A Turing machine is not a literal blueprint for modern laptops. It is a deliberately minimal model that helps us reason about what computation is and where its limits are.
By the end, you should be able to say:
- Describe the tape, read-write head, current state, and transition rule in plain language
- Trace a simple computation one step at a time without skipping intermediate states
- Explain why very simple instructions can still add up to powerful computation
Think about this first
If you were only allowed to inspect one binary digit at a time, how would you add 1 to the number 0111? Describe the exact sequence of checks and moves you would make.
Words we will keep using
What is a Turing Machine?
A Turing machine is just a strip of paper, a pen, and a list of rules. Yet this tiny setup can compute anything your laptop can — just much, much slower. It is the theoretical foundation of all modern computing.
▶ TURING TERMINAL
Machine setup
State Transition Diagram
The machine's rulebook as a picture. The orange node tracks where the machine is right now. Step through to watch it move.
Edge labels: read/write,direction. Double circle = accept state.
Try These Examples
Flips every bit: 0→1 and 1→0. Head moves right until blank, then accepts.
Why Does This Matter?
This matters because it strips computing down to its bare idea: rule-following. Modern computers are far more powerful than this toy model, but the central lesson is identical — complex behaviour grows out of very simple instructions applied repeatedly.