What Is a Turing Machine? The Mathematical Foundation of Computing

What's the simplest possible description of what a computer does? Not "it runs apps" or "it processes data," something more basic. What is the smallest set of rules a machine needs to follow to compute anything at all?

In 1936, years before the first electronic computer existed, a 24-year-old mathematician named Alan Turing answered that question. His answer wasn't a circuit diagram. It was a thought experiment simple enough to build out of paper: an infinite strip of tape, a pointer that reads and writes one symbol at a time, and a tiny table of rules telling that pointer what to do next.

That thought experiment is called a Turing machine, and it's still the mathematical foundation everything we call "computation" rests on.

A computer isn't a chip. It's a mindless pointer following a table.

Picture yourself standing on one square of an endless strip of graph paper. You can only see the square under your feet. On it is either a mark or nothing. You're also holding a tiny notebook, and you're in one of a handful of "moods," each one just a label like A or B.

Your notebook has entries like this: "If you're in mood A and you see a 1, cross it out, write a 0, take one step left, and switch to mood B." That's it. You read the notebook, follow the one instruction that matches your current mood and what's under your feet, and repeat.

You never see the whole strip of paper. You never plan ahead. You just follow the rule in front of you, over and over. And that mindless, one-step-at-a-time process is, mathematically, everything a computer does.

We give the pieces names. The strip of paper is the tape, an unlimited row of cells that each hold one symbol. The pointer is the head, which reads the cell it's sitting on, can write a new symbol there, and then moves one cell left or right. Your "mood" is the state, a label for where you are in the machine's train of thought. And the notebook is the transition function: given a state and a symbol, it tells you what to write, which way to move, and what state to become next.

We write that transition function as $\delta(q, s) = (s', d, q')$: current state $q$ and symbol $s$ go in, a new symbol $s'$, a direction $d$, and a new state $q'$ come out.

Here's a real Turing machine running. It adds 1 to the binary number 1011 the same way you'd add 1 by hand: scan right to find the end of the number, then walk back left, flipping 1s to 0s until you hit a 0 (or run out of digits), which is exactly what carrying a 1 looks like in binary.

Step through it slowly and watch the carry. The machine spends its first few steps just scanning right, doing nothing, until it finds the blank cell past the last digit. Then it turns around, and the real work starts: 1 flips to 0, 1 flips to 0 again, and the carry finally stops the moment it hits a 0, which flips to 1. 1011 becomes 1100. Eleven becomes twelve, one mechanical step at a time.

The whole program fits on an index card

Look back at what just happened. There was no hidden logic, no separate "addition" subroutine, no memory beyond the tape itself. Every decision the machine made came from one lookup: given the current state and the symbol under the head, what do I write, which way do I move, and what state comes next?

That lookup table is the entire program. For the machine you just watched, it's six lines long.

Click through the rules. Notice how small this is. Two rules for "keep scanning right." One rule for "found the end, turn around." Three rules for the carry. Nothing else exists in this machine. No variables, no functions, no loops in the way a programming language has them, just a state, a symbol, and a table telling the head what to do about it.

This is the part that made Turing's idea so powerful. He wasn't describing one machine that adds binary numbers. He was describing a template: any computation you can imagine, sorting a list, checking a chess move, running a search engine, can in principle be written as some transition table over some states and symbols. Different tables, same machine.

Adding one more state can blow the behavior wide open

Here's a strange question: if you only allow yourself a handful of states and two symbols, and you want the machine to run as long as possible before halting, how long can you make it go?

This is called the busy beaver problem, and the function that answers it, $BB(n)$, is one of the fastest-growing functions in all of mathematics. $BB(n)$ is the largest number of steps any $n$-state, 2-symbol machine can take before it halts, assuming it halts at all, starting from a blank tape.

Slide from 1 state to 5. A 1-state machine can only run for 1 step. A 2-state machine can be coaxed into 6 steps. By 4 states you're at 107 steps. By 5 states, the best known machine, found and verified only in 2024 after decades of searching, runs for 47,176,870 steps before it finally stops.

Five states. Two symbols. Six lines of rules, structurally no more complex than the addition machine above. And the behavior it can produce is already too large to predict by staring at the table. Nobody has pinned down $BB(6)$ exactly. It's proven to be far larger still, and the honest answer is that we may never know it precisely. This function grows faster than any function a computer can actually compute, which is a strange thing to say about a function defined entirely in terms of computers.

You can't always tell if a machine will ever stop

That last fact points at something deeper. If a machine's behavior can outrun our ability to predict it just by adding one more state, is there a program that could look at any machine and tell you, in advance, whether it'll ever halt?

Try watching for yourself. Below are three tiny machines. One halts almost immediately. One grinds along for a while before it halts. One never halts at all, it just keeps going forever.

Run Machine B and Machine C side by side, at least in your head. For the first 130 steps, they look identical. Both are "still running." At step 131, one of them stops and the other keeps going, but there was no earlier moment where you could have told them apart just by watching. You'd need to wait forever to be sure a non-halting machine is really non-halting, and forever is exactly the one thing you don't have.

This is the shape of the actual halting problem, proven unsolvable by Turing in the very same 1936 paper that introduced this machine. If you want to see the full proof (it's a genuinely clever trick involving a machine that asks a question about itself), the halting problem post walks through it step by step. The same self-referential trick shows up again in Gödel's incompleteness theorem, which hits an almost identical wall inside pure logic instead of computation.

Every computer you've ever used is, underneath, just this

Here's the payoff. The Church-Turing thesis, named for Turing and his contemporary Alonzo Church, is the claim that any function computable by any reasonable notion of "an effective procedure" can be computed by some Turing machine. Nobody has ever found a counterexample.

Your phone, a graphing calculator, a data center running a neural network, a physical CPU built from billions of transistors, none of them can compute anything a Turing machine with enough tape and enough time couldn't also compute. They differ enormously in speed and convenience, but not in what's fundamentally reachable. If you're curious how those transistors turn into logic in the first place, Boolean algebra is the layer directly underneath: a handful of AND, OR, and NOT gates, combined, that eventually behave exactly like a state and a rule table.

And once you accept that everything reduces to this one model, a new question opens up: not just "can a machine compute this," but "how fast can it." Some problems a Turing machine burns through instantly. Others take longer than the age of the universe for inputs barely larger. That gap, and whether it's ever truly unavoidable, is the entire subject of the P vs NP problem.

The short version

A Turing machine is a strip of tape, a head that reads and writes one symbol at a time, and a small table of rules mapping (state, symbol) to (write, move, new state). Nothing about modern computers changes this picture in any fundamental way, they're just faster, more convenient versions of the same tape-and-table idea Turing sketched with a pencil in 1936. Small rule tables can already produce behavior too large to predict, as the busy beaver numbers show. And baked into the model is a hard limit: no matter how the table is written, some questions about what a machine will do can never be answered in general, for any machine, by any other machine. That limit isn't a bug in today's computers. It's a fact about computation itself, discovered before a single electronic computer had been built.

All four visualizations above are plain React components rendered as SVG: a real Turing machine trace, a clickable rule table, real busy beaver numbers, and a requestAnimationFrame-driven step race. No libraries beyond React.