What is a Turing machine? The idea behind every computer

A Turing machine is an imaginary computer reduced to its bare parts: a long tape of squares, a head that reads and writes one square at a time, a current state, and a table of rules saying what to do next. Alan Turing described it in 1936 to define exactly what "computing by following rules" means. Anything a modern computer can calculate, a Turing machine can too, given enough tape and time.

In short

• A Turing machine has four parts: a tape, a read-write head, a finite set of states, and a rule table that, given the state and the symbol read, says what to write, which way to move and which state to enter.
• A universal Turing machine reads another machine's rules from its tape and imitates it, which is the idea behind every programmable computer.
• Turing used the model to prove that some well-defined questions, such as whether a program will ever stop, can't be answered by any computer at all.

What are the parts of a Turing machine?

There are four, and none is more than a clerk with a pencil would need. The tape is divided into squares, each blank or holding one symbol, and it is as long as needed. The head sits over one square: it can read the symbol there, write a new one, and move one square left or right. The state is the machine's only memory apart from the tape, one of a fixed, finite list, such as "even so far" or "carrying a 1". And the rule table lists, for each combination of state and symbol read, three things: the symbol to write, the direction to move, and the next state.

The Stanford Encyclopedia of Philosophy's entry notes that Turing called the states "m-configurations" and wrote each rule as one line of a table. Nothing else is allowed: no arithmetic circuit, no memory chips, no instructions besides the table. The surprise is that these few parts are enough for any calculation a computer can do. Turing modeled them on a person working a problem on paper, who at each moment looks at a little of the page, keeps a little in mind, and follows fixed rules.

How does one actually run? A worked example

Here is a small machine with a job: decide whether a row of 1s has an even or odd number of them. Its tape holds 1 1 1 followed by blanks, the head starts on the first 1, and it starts in the state EVEN. Its rule table has four lines.

State	Reads	Writes	Moves	Next state
EVEN	1	1	right	ODD
ODD	1	1	right	EVEN
EVEN	blank	E	stays	halt
ODD	blank	O	stays	halt

Run it square by square.

1. In EVEN, the head reads 1. The rule says: leave the 1, move right, switch to ODD.
2. In ODD, it reads the second 1. Move right, switch to EVEN.
3. In EVEN, it reads the third 1. Move right, switch to ODD.
4. In ODD, it reads a blank. Write O and halt.

The tape now reads 1 1 1 O: odd, which is right. Notice what the state did. The machine never counted to three; it couldn't, with only two states. It kept just enough memory, one flip of a switch per 1, to answer the question. With 1,000 ones it would take 1,001 steps, and the same four rules. Machines that add, multiply or sort are built the same way, with longer tables; the note on Alan Turing's life and work runs one that adds 1 to a binary number.

What is a universal Turing machine?

It is a Turing machine whose job is to run other Turing machines. Write a machine's rule table onto the tape as a string of symbols, followed by that machine's input, and the universal machine reads the table and does what the described machine would do, step by step. Turing showed in the same 1936 paper that one fixed table of rules can do this for every possible machine.

That is the stored-program idea, more than a decade before hardware that worked this way was built. A laptop is one machine that becomes a word processor, a game or a browser depending on the program it loads, because its rules for running programs are fixed while the programs themselves are just data. The note on how computers work follows how real processors do that. A real computer differs in one honest way: its memory is finite, while the Turing machine's tape never runs out. For any task that fits in memory, the two can do the same things.

It is also why nearly every programming language is equally powerful in principle. A language that can simulate a Turing machine is called Turing complete, and any two such languages can each, in principle, compute whatever the other can.

What does the Church–Turing thesis say?

It says that anything that can be computed by a step-by-step method at all can be computed by a Turing machine. In other words, the Turing machine doesn't just model one kind of computer; it captures what an algorithm is.

It is called a thesis, not a theorem, because it can't be proved: "a step-by-step method" is an everyday idea, not a mathematical one. The evidence is that every other definition anyone has proposed has turned out to compute exactly the same things. Alonzo Church's definition through his lambda calculus and Emil Post's 1936 machine both compute exactly what Turing's does, as the Stanford Encyclopedia's entry on the thesis sets out. Note what it does not say: it is about what can be computed, not how fast. Speed is a separate question, the one behind P vs NP.

What did Turing prove can't be computed?

The question Turing set out to answer was the Entscheidungsproblem, German for "decision problem", posed by David Hilbert and Wilhelm Ackermann in 1928: is there a mechanical method that decides, for any statement of logic, whether it is valid? To answer no, Turing needed a precise meaning for "mechanical method", and the machine was it. Its best-known descendant is the halting problem: is there a program that can look at any program and its input, and say correctly whether it will eventually stop or run forever?

There isn't, and the argument fits in a paragraph. Suppose a program called Halts could always answer. Build a new program, Contrary, that takes a program P, asks Halts whether P stops when given its own text as input, and then does the opposite: if Halts says "stops", Contrary loops forever; if "runs forever", Contrary stops. Now feed Contrary its own text. If Halts says it stops, it loops; if Halts says it loops, it stops. Either answer is wrong, so no such Halts can exist.

The common misreading is that it is impossible to tell whether a program halts. It isn't: for most programs people write, tools can tell. What can't exist is one method that is right for every program. The consequence is practical: no tool can check every program perfectly for any interesting behavior, such as whether it will ever crash, which is why bug-finders and virus scanners work by rules of thumb and still miss things.

When did all this happen?

When	What happened
1928	Hilbert and Ackermann pose the Entscheidungsproblem
15 April 1936	Alonzo Church's paper giving a negative answer, using his lambda calculus, is published
28 May 1936	Turing's paper, "On Computable Numbers", is received by the London Mathematical Society
1936	Emil Post publishes a nearly identical model of computation
12 November 1936	Turing's paper is read to the Society
Winter 1936–37	It appears in the Society's Proceedings, volume 42, dated 1936–37
1937	Church, reviewing the paper, first calls the device a "Turing machine"

Turing reached his answer independently and had his paper nearly done when Church's appeared; the dates, from the paper itself and the history collected in the Turing machine article, show how close the race was. Turing's model became the standard one, largely because a tape and a table made the idea of computing concrete.

Check yourself

• Without looking back, name the four parts of a Turing machine and what the rule table decides at each step.
• Explain why the Church–Turing thesis can't be proved, and what counts as evidence for it.
• Walk through why a program that answers the halting question for every program leads to a contradiction.

Sources

• On Computable Numbers, with an Application to the Entscheidungsproblem — Alan Turing, Proceedings of the London Mathematical Society, 1936
• Turing machines — Stanford Encyclopedia of Philosophy, revised 2025
• The Church–Turing thesis — Stanford Encyclopedia of Philosophy, revised 2023
• Entscheidungsproblem — Wikipedia
• Turing machine — Wikipedia