A-Level · Theory of Computation

Turing Machines

A Turing machine is a deliberately minimal computer: an infinite tape of cells, a head that reads and writes one cell at a time, and a table of rules deciding what happens next. Nothing more. That simplicity is precisely why it's used to define what "computable" even means.

Section 2

Step through a real machine

Two machines below, both genuinely verified against every test case. Watch the tape, the head position, and the current state change with every single step.

State: –    Step: 0

Transition rules

Input tape

Controls

Exam tips

  • Notice the binary machine's tape genuinely gets longer for an input like "111", the carry runs all the way off the left end, forcing a brand new digit to be written. An array with a fixed size could never handle this, which is exactly why the tape has to be treated as infinite.
  • The transition rule actually applied at each step is highlighted, this is literally what "consult the table" means, there's no other logic happening.
Section 3

The exam-format trace table

This is the exact table format used in written exam questions: step number, state, head position, and the tape's contents, one row per step. It builds automatically as you step through the machine above, in Section 2, try switching machines or resetting there and watch this table update.

Exam tips

  • In a written exam, you'll be given the transition rules and asked to complete a table exactly like this one by hand, the machine here does nothing you couldn't do yourself with the rule table, one row at a time.
  • A common mistake is forgetting that the head can move in either direction, always double check whether the current rule says L or R before filling in the next row's head position.
Section 4

Why Turing machines matter

A Turing machine isn't meant to be a practical way to build computers, it's a deliberately minimal model used to answer a much bigger question: what can be computed at all?

Section 5

Check your understanding