What Can a Computer Actually Do?

Imagine a chef who can only see one tiny cutting board at a time. To cook, they follow a strict recipe book: "If you see an egg and you are in the Baking State — crack it, step right, enter the Mixing State." That chef is a Turing Machine.

A Turing Machine (TM) is an idealized mathematical model of a computer invented by Alan Turing in 1936. By stripping computation down to its bare essentials — a tape of memory, a read/write head, and a rulebook — it reveals the absolute limits of what any algorithm can and cannot do.

We study TMs not because we build them, but because understanding them means understanding computation itself — which problems are solvable, which are provably impossible, and why.

The head reads one cell at a time. Every 1.5 s it moves right — looping forever on the infinite tape.