Back to all lessons
FoundationsBeginner

⚙️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.

20 min- Explore at your own pace

Before We Begin

What we are learning today

The Turing Machine isn’t a dusty relic—it’s the story of how all computers think. With a strip of paper and a tiny rulebook, it proves you can compute almost anything by moving one square at a time.

How this lesson fits

Welcome to the bedrock of AI. Think of this module as the class warm-up where we learn how computers follow rules, deal with uncertainty, and search for answers—exactly the skills we’ll lean on all year.

The big question

How can something as ordinary as metal and silicon learn to follow rules, handle uncertainty, and still find its way through a messy world?

Trace a computation step by step and explain the “why” out loudReason about chance with simple, friendly distributionsDescribe how search algorithms pick a smart path forward

Why You Should Care

This pulls back the curtain on the “magic” of code. Intelligence here is just a chain of simple, repeatable steps—and that’s empowering once you see it.

Where this is used today

  • ✓Regular Expressions (Regex) finding patterns in text
  • ✓Compiler design (how code becomes software)
  • ✓Theoretical limits (proving what computers CANNOT do)

Think of it like this

Picture a focused student with an endless roll of paper. They read one square, peek at the rulebook, jot down the next symbol, and step left or right. It feels slow, but it’s the same idea your laptop repeats at lightning speed.

Easy mistake to make

A Turing machine isn’t a blueprint for the laptops we buy. It’s a minimal model we use to understand the *limits* of computation.

By the end, you should be able to say:

  • Describe the tape, head, state, and transition rule
  • Trace a computation one step at a time
  • Explain why simple instructions can still solve meaningful tasks

Think about this first

If you could only look at one symbol at a time, how would you still add 1 to a binary number? Walk me through your steps.

Words we will keep using

tapestatetransitionaccepthalt

What is a Turing Machine?

This is the simplest computer science lesson in the world. 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 compute—just much, much slower.

TapeThe memory. An infinite roll of paper.
HeadThe eye and the hand. It reads a square, writes a square, and moves.
StatesThe brain. A simple "What am I doing right now?" tracker.

▶ TURING TERMINAL v2.0

STATE: q0 | STEPS: 0 | HALTED
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
_
▲
300ms

State Transition Diagram

This diagram is the machine's rulebook turned into a picture. As you step through the program, the orange node shows where the machine currently is.

Edges are labelled read/write,direction. Double circle = accept state.

Try These Examples

Flips every bit: 0→1 and 1→0. Heads 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 practical than this toy model, but the central lesson is the same. Complex behavior can grow out of very small instructions.