Short version: a Turing machine is an imaginary device that reads and writes symbols on a long tape, one square at a time, following a small table of rules. Alan Turing described it in 1936 to pin down exactly what “following a method” means. His bigger discovery was the universal machine: one machine that can do the job of any other, if you write the other machine’s rules onto its tape. That’s the idea inside every computer you own. The hardware stays the same, and the software, which is just more data, decides what it is. The same paper also proved that some questions can never be answered by any computer, which is why, for example, no antivirus can ever promise to catch everything.

The question that started it

In 1928 the mathematician David Hilbert (with Wilhelm Ackermann) asked whether there could be a mechanical procedure that decides, for any statement in logic, whether it can be proved: feed in the statement, follow the steps, get a yes or no. It was known by its German name, the Entscheidungsproblem, the “decision problem”.

To answer it, someone first had to say exactly what a “mechanical procedure” is. That’s what Turing did. At the time a “computer” wasn’t a machine, it was a job: a person who did calculations with pencil and paper by following instructions. Turing asked what such a person is really doing and stripped it down to the bare minimum:

Women at desks in a 1949 office, working through paper records with slide rules and a mechanical calculator
Before computers were machines, they were people. “Computers” at work at NACA’s High Speed Flight Station in the United States, summer 1949, turning raw flight-test records into engineering numbers with slide rules and calculators. Turing’s 1936 machine was modelled on exactly this kind of work. Photo: NACA (NASA), public domain, via Wikimedia Commons (resized)
  • They look at a few symbols on the page at a time.
  • They write a symbol or rub one out.
  • They move their attention to a nearby spot.
  • They remember which step of the method they’re up to.

Anything a human computer could do by following rules, he argued, a machine doing only those four things could do too.

From a human computer to a Turing machineFour things a person does when following a method by hand, each matched to the machine version: looking at a few symbols becomes reading one square; writing or rubbing out becomes writing one symbol; moving to a nearby spot becomes moving one square left or right; remembering the step becomes holding one state.A person following a methodA Turing machinelooks at a few symbolsreads one squarewrites a symbol or rubs one outwrites one symbolmoves to a nearby spotmoves one square left or rightremembers which step it’s onholds one stateNothing else: no arithmetic, no memory beyond the tape and one state.
Turing started from a person, not a machine. In 1936 a “computer” was someone doing sums by hand. He boiled what they do down to four actions small enough for a machine.

How a Turing machine works

A Turing machine has four parts:

  1. A tape: a strip divided into squares, as long as it needs to be. Each square holds one symbol, say 0, 1 or blank.
  2. A head: it sits over one square, reads the symbol there, can write a new one, and can move one square left or right.
  3. A state: a note of which step it’s up to, like a person remembering “I’m carrying a one”.
  4. A rule table: the program. Each rule says: if you’re in this state and you read this symbol, write this, move this way, and switch to that state.

That’s it. No screen, no memory chips, no maths unit. Every step is something a child could do.

The four parts of a Turing machineA tape of squares holding the binary number 1011 with blanks either side. The head sits under the last 1, reading it. Below, the state box says carry, and the rule table lists three rules, with the one that applies now highlighted: in state carry, reading 1, write 0, move left, stay in carry.1. Tape……10112. Headreads and writes one square,then moves left or right3. State (which step it's on)carry4. Rule table (the program)statereadswritemovenextcarry10leftcarrycarry01staydonecarryblank1staydone
A tape, a head, a state and a rule table: that's the whole machine. Here it's adding one to 1011. The head reads a 1 while in the state “carry”, so the highlighted rule applies: write 0, move left, keep carrying.

Take adding one to the binary number 1011 (eleven). The head starts on the rightmost digit, in the state “carry”. The whole program is three rules:

StateReadsWriteMoveNext state
carry10leftcarry
carry01staydone
carryblank1staydone

The machine turns the last 1 into 0 and carries left, turns the next 1 into 0 and carries again, finds a 0, writes 1 and stops: 1100, which is twelve. It’s exactly what you’d do with a pencil.

Adding one to 1011, step by stepFour snapshots of the tape. Start: 1011, the head on the last digit, state carry. Step 1: it reads 1, writes 0 and moves left, giving 1010. Step 2: it reads 1, writes 0 and moves left, giving 1000. Step 3: it reads 0, writes 1 and stops in the state done, giving 1100, which is twelve.start1011head on the last digitstate: carrystep 11010read 1: write 0, move leftstate: carrystep 21000read 1: write 0, move leftstate: carrystep 31100read 0: write 1, stopstate: done1011 (eleven) + 1 = 1100 (twelve)square just written
Three rules, three steps. Green marks the head, amber the square it has just written. It carries left exactly as you would with a pencil, then stops when there’s nothing left to carry.

The surprise is how far this goes. Give a Turing machine enough tape and a big enough rule table and it can do any calculation any computer has ever done: multiply, sort a list, edit a photo, run a spreadsheet. It would be absurdly slow, but it would get there. The American logician Alonzo Church reached the same answer to Hilbert’s question the same year by a different route, and the idea that ties their work together is now called the Church–Turing thesis: anything that can be worked out by a step-by-step method can be worked out by a Turing machine. It’s a thesis, not a proof, but in ninety years nobody has found an exception.

Try it: a Turing machine in your browser

This part of the page is a small working Turing machine that runs in your browser with JavaScript. It runs three different rule tables on the same machine: add one to a binary number, flip every bit, and decide whether a number is odd or even.

Notice what never changes as you switch programs: the tape, the head and the way it steps. Only the rule table changes. Hold that thought.

The big idea: one machine that can be any machine

Before Turing, a machine did one job. A loom wove, a cash register added up, and even the code-breaking machines built a few years later at Bletchley Park were made for one particular task. For a different job, you built a different machine.

Turing noticed that a rule table is just a list of symbols, and a list of symbols can be written on a tape. So he described a universal machine: one Turing machine whose rules say, in effect, “read the description of a machine written on the tape, then do whatever that machine would do to the data written next to it.” Give it the description of an adding machine and it adds. Give it a sorting machine and it sorts. One fixed piece of hardware, endlessly repurposed by changing what’s on the tape.

A universal machine reads a program and data from the same tapeOne tape holds two things side by side: on the left, the rule table of some machine M written out as symbols (the program); on the right, the data. Both feed into one universal machine with a fixed rule table, which then does whatever M would do to the data. Underneath: today the chip is the machine, the app is the program and your files are the data.the programthe dataq110←q101…1011machine M’s rule table, written as symbolswhatever M should work onUniversal machineone fixed rule table: “read M, then be M”does whatever M would do to the dataToday: the chip is the machine, the app is the program, your files are the data.
Change the program, not the machine. The universal machine never changes. Write a different machine’s rules on the tape and it becomes that machine. That’s why one phone can be a camera, a calculator and a map.

That’s the stored-program computer, and it’s every computer you own:

  • Your phone is one machine pretending to be hundreds. A calculator, a camera, a map, a bank branch: each app is a description held in memory, and the same chip carries it out.
  • Software is data. A program is downloaded, copied, emailed and backed up exactly like a photo, because to the machine it’s the same kind of thing.
  • Computers can pretend to be other computers. Emulators that run old games, the virtual machines that make up “the cloud”, and the tools that keep old business software running on new hardware all work because a universal machine can imitate any other machine, given its description.
  • AI is software too. A large language model is an enormous table of numbers running on the same universal machines as your spreadsheet. That’s worth remembering both when someone calls it magic and when someone calls it “just a program” (more on that in does AI really understand?).

From paper to real machines

Turing’s machine was a thought experiment: nobody needed to build one with an actual tape (though people have, for fun). But the idea fed straight into the first real computers.

A small working Turing machine on a display stand: a tape wound between two white reels, passing through a clear box that holds the read and write head
Someone did build one. A working Turing machine made by Mike Davey, with a real tape wound between two reels, on show at Harvard University in 2012. Real computers do the same job with memory instead of tape. Photo: Rocky Acosta, CC BY 3.0, via Wikimedia Commons (resized)

During the Second World War Turing worked at Bletchley Park on the German Enigma cipher, and designed the Bombe, an electromechanical machine developed from an earlier Polish design, the bomba, and improved by Gordon Welchman, that hunted for each day’s Enigma settings. It was brilliant, but built for one job. So was Colossus, built by the Post Office engineer Tommy Flowers to attack a different cipher, Lorenz. Colossus is often credited to Turing, but it wasn’t his design. It could be set up for different tasks with switches and plugs, but it wasn’t a stored-program computer.

After the war, teams raced to build a universal machine out of electronics:

  • In June 1945, John von Neumann’s First Draft of a Report on the EDVAC laid out the stored-program design that most computers still follow, drawing on the ENIAC team’s work with J. Presper Eckert and John Mauchly.
  • Turing designed his own, the ACE (Automatic Computing Engine), for Britain’s National Physical Laboratory, with a detailed proposal in 1945–46. A smaller version, the Pilot ACE, ran its first program in May 1950, by which time Turing had moved to Manchester.
  • On 21 June 1948, the Manchester Baby ran the world’s first program stored in electronic memory.
The back of a large cabinet packed with rows of rotating drums and red wiring
The Bombe (a rebuild at Bletchley Park): built for one job, finding each day’s Enigma settings. Photo: Mike Peel, CC BY-SA 4.0, via Wikimedia Commons (resized)
Two women operating Colossus, a wall of valves and switches, with a paper tape running over pulleys on a frame
Colossus Mark 2 at Bletchley Park, operated by Dorothy Du Boisson and Elsie Booker. Set up with switches and plugs, not a stored program. Photo: The National Archives (UK), public domain, via Wikimedia Commons (resized)
A long row of grey equipment racks in a museum gallery, with visitors looking at them
The Manchester Baby (a replica in Manchester’s Science and Industry Museum). The original ran the first stored program in 1948. Photo: Parrot of Doom, CC BY-SA 3.0, via Wikimedia Commons (resized)
A wooden control desk beside a tall cabinet of valves behind glass in a museum
The Pilot ACE, built at the National Physical Laboratory from Turing’s ACE design, now in the Science Museum, London. Photo: Philafrenzy, CC BY 2.0, via Wikimedia Commons (resized)

So it’s fairest to say Turing didn’t invent “the computer” on his own; many people did that, on both sides of the Atlantic. What he gave everyone was the theory of what a computer is, and the proof that one general-purpose machine is enough.

From an idea to real computers: a timeline1928: Hilbert and Ackermann ask the decision problem. 1936: Turing publishes On Computable Numbers, and Church answers the same question. Second World War: at Bletchley Park the Bombe attacks Enigma, and in 1944 Colossus attacks the Lorenz cipher. 1945: von Neumann's EDVAC report, and Turing designs the ACE. 1948: the Manchester Baby runs the first stored program, on 21 June. 1950: the Pilot ACE runs, and Turing publishes the imitation game. 1954: Turing dies, aged 41. 2009 to 2021: an apology, a royal pardon and the £50 note.1928Hilbert and Ackermann ask the “decision problem”1936Turing’s On Computable Numbers; Church answers it tooWWIIBletchley Park: the Bombe (Enigma); Colossus (Lorenz, 1944)1945von Neumann’s EDVAC report; Turing designs the ACE1948Manchester Baby runs the first stored program (21 June)1950Pilot ACE runs; Turing publishes the imitation game1954Turing dies, aged 412009–21An apology, a royal pardon and the £50 notetheorymachinesbothTuring’s life
Twelve years from a thought experiment to a working stored-program computer. The theory came first; the machines that could actually be “any machine” followed after the war.

“Turing complete”: the strange places universal machines turn up

A system is Turing complete if it can compute anything a Turing machine can, given enough time and memory. Every mainstream programming language is. So, it turns out, are some things that were never meant to compute anything:

  • Excel formulas, once Microsoft added the LAMBDA function. Microsoft’s own researchers said so when they announced it.
  • PowerPoint, built from nothing but its own shapes and animations, as a researcher demonstrated in 2017. It was a tongue-in-cheek paper, but it works.
  • Conway’s Game of Life, a grid of squares that live or die by a handful of simple rules.
  • Magic: The Gathering, the card game, shown to be Turing complete in 2019.

Two lessons. First, universality is surprisingly easy to stumble into: give something a way to store information, make decisions and repeat, and you’ve probably built a computer. Second, “Turing complete” says nothing about speed. Strictly, your laptop isn’t quite a Turing machine either, because its memory eventually runs out and a Turing machine’s tape never does. In practice it’s close enough that nobody minds.

What no computer can ever do

The 1936 paper had a sting in the tail. Turing proved that some questions can’t be answered by any machine, ever, however fast it is.

The best-known version is now called the halting problem (the name came later). Can you write a program that looks at any other program and its input, and says correctly whether it will eventually finish or run forever? You can’t, and the reason fits in three steps:

  1. Suppose someone hands you a perfect checker, call it WillItStop, that always answers correctly.
  2. Build a contrary program, Contrary, that asks WillItStop about itself and then does the opposite: if the answer is “it stops”, it loops forever; if the answer is “it runs forever”, it stops at once.
  3. Now ask: does Contrary stop? Whatever WillItStop says, Contrary does the opposite, so WillItStop is wrong.
Why a perfect WillItStop checker can't existA program called Contrary asks WillItStop whether Contrary will stop. If WillItStop says it stops, Contrary loops forever, so the answer was wrong. If WillItStop says it runs forever, Contrary stops at once, so the answer was wrong again. Either way the checker is wrong, so a perfect checker cannot exist.Contrary: a program built to do the oppositeAsk WillItStop: “will I stop?”it says “it stops”it says “it runs forever”so Contrary loops foreverso Contrary stops at onceit never stops: wrongit stops: wrongWhatever WillItStop answers, it’s wrong,so a perfect checker can’t exist.The same trap is why no tool can perfectly spot every virus.
A checker that is always right would have to predict a program that does the opposite of whatever it predicts. That’s impossible, so no such checker can be built, however clever or fast.

So a perfect checker can’t exist. Turing’s own version was framed a little differently, but the idea is the same, and it answered Hilbert’s question: no, there’s no mechanical procedure that settles every statement.

This isn’t just a puzzle for mathematicians. It shows up in everyday IT:

  • No antivirus can catch everything. In the 1980s the researcher Fred Cohen showed, with the same kind of argument, that no program can perfectly decide whether any other program is a virus. A more general result, Rice’s theorem, says no tool can perfectly decide any non-trivial question about what a program will do. That’s why good security works in layers instead of trusting one product (see the Essential Eight in plain English), and why services that watch behaviour and respond, like managed detection and response, exist.
  • No tool can prove all your software is bug-free. Checking tools find a lot, but none can promise to find everything. Testing, review and backups are there for what slips through.

Why it matters for a business

You don’t need the theory to run a business, but three practical points fall straight out of it:

  • Your software and data are the asset; the hardware is replaceable. Any modern computer can run your systems given the right software and settings, which is why moving to new machines, or to the cloud, is a migration job, not a rebuild. Keep your data and configuration somewhere you control, and backed up.
  • Be wary of anyone promising to catch 100% of threats. In general it’s mathematically impossible. Ask how they detect, how they respond, and what happens when something gets through. That’s also why tested backups matter.
  • General-purpose beats single-purpose. The lesson of 1936 is that one flexible machine plus good instructions beats a cupboard full of gadgets. The same is turning out to be true of AI: one capable, well-briefed assistant often does more than a handful of single-job apps.

Alan Turing, briefly

Alan Turing was born in London on 23 June 1912 and wrote On Computable Numbers at 23. As well as the Turing machine and his wartime code-breaking, in 1950 he asked whether machines could think, and proposed the “imitation game” now known as the Turing test.

Black and white passport photograph of Alan Turing as a teenager, in a jacket and tie
Alan Turing at 16, around 1928, eight years before On Computable Numbers. Photo: unknown photographer (possibly Arthur Reginald Chaffin), public domain, via Wikimedia Commons, from the Turing Archive, King’s College Cambridge (resized)

In 1952 he was prosecuted for homosexuality, then a crime in Britain, and accepted hormone treatment instead of prison. He died in June 1954, aged 41. The British Prime Minister apologised for his treatment in 2009, he received a royal pardon in 2013, and since 2021 he has been on the Bank of England £50 note. The best-known award in computing, the ACM A.M. Turing Award, is named after him.

Common questions

What is a Turing machine in simple terms?
An imaginary machine that reads and writes symbols on a long tape, one square at a time, following a short table of rules. Alan Turing described it in 1936 to define exactly what following a step-by-step method means. Despite how simple it is, it can carry out any calculation a modern computer can, just far more slowly.
What is a universal Turing machine?
A single Turing machine that can imitate any other. You write the other machine’s rules on its tape, followed by the data, and it does whatever that machine would do. It’s the idea behind the stored-program computer: one fixed piece of hardware that becomes a different machine depending on the software it’s given.
Was a Turing machine ever actually built?
Not as a practical computer. It’s a thought experiment for reasoning about what can and can’t be computed. People have built working models for fun and for display, but real computers use the same idea far more efficiently, with memory they can jump around in instead of a tape they have to walk along.
Is my phone or laptop a Turing machine?
In practice, yes: it’s a universal machine that can run any program you give it. Strictly, a true Turing machine has unlimited tape and your device has limited memory, but for everyday purposes it’s close enough.
What’s the difference between a Turing machine and the Turing test?
They’re two different ideas from the same person. The Turing machine (1936) is a model of what computing is. The Turing test (1950) is a way of judging whether a machine’s conversation can pass for a human’s.
What does Turing complete mean?
That a system can compute anything a Turing machine can, given enough time and memory. Every mainstream programming language is Turing complete, and so, surprisingly, are Excel formulas, PowerPoint animations and the card game Magic: The Gathering.
What is the halting problem?
The question of whether one program can look at any other program and decide whether it will finish or run forever. Turing’s work shows it can’t be done in general, and the same limit means no antivirus or code-checking tool can ever be perfect.
Did Alan Turing invent the computer?
Not single-handedly. He gave the theory of what a computer is, showed that one universal machine is enough, and designed an early computer, the ACE. The first working stored-program computers were built by teams in Britain and the United States in the late 1940s.

Sources

All checked 14/10/2026.

  • A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, series 2, vol. 42 (received 28 May 1936). academic.oup.com
  • Stanford Encyclopedia of Philosophy, The Church-Turing Thesis. plato.stanford.edu
  • Stanford Encyclopedia of Philosophy, Alan Turing. plato.stanford.edu
  • The University of Manchester, How a 70-year-old baby changed the face of modern computing (the Manchester Baby, 21 June 1948). manchester.ac.uk
  • Computer History Museum, First Draft of a Report on the EDVAC (30 June 1945). computerhistory.org
  • The Turing Archive for the History of Computing, the ACE and the Pilot ACE (first program 10 May 1950). alanturing.net
  • The National Museum of Computing, Colossus. tnmoc.org
  • A. M. Turing, Computing Machinery and Intelligence, Mind, vol. 59 (October 1950). academic.oup.com
  • Fred Cohen, Computer Viruses: Theory and Experiments (1984; Computers & Security, 1987). all.net
  • Microsoft Research, LAMBDA: The ultimate Excel worksheet function (25 January 2021). microsoft.com
  • Churchill, Biderman and Herrick, Magic: The Gathering is Turing Complete (2019). arxiv.org
  • Hamkins and Nenu, on the origin of the name “halting problem” (2024). arxiv.org

Photographs (all via Wikimedia Commons, used under the licence shown, checked 14/10/2026)

  • NACA (NASA), “Human computers, Dryden” (1949), Wikimedia Commons, public domain (resized). file page
  • Rocky Acosta, “Turing Machine Model Davey 2012”, Wikimedia Commons, CC BY 3.0 (resized). file page
  • Mike Peel, “Bletchley Park Bombe” (2006), Wikimedia Commons, CC BY-SA 4.0 (resized). file page
  • The National Archives (UK), “Colossus”, Wikimedia Commons, public domain (resized). file page
  • Parrot of Doom, “SSEM Manchester museum” (2009), Wikimedia Commons, CC BY-SA 3.0 (resized). file page
  • Philafrenzy, “Pilot ACE in the Science Museum” (2011), Wikimedia Commons, CC BY 2.0 (resized). file page
  • Possibly Arthur Reginald Chaffin, “Alan Turing Aged 16” (about 1928), Turing Archive, King’s College Cambridge, Wikimedia Commons, public domain (resized). file page

Keep reading

AI at work Does AI really understand, or is it just autocomplete? Simple rules, astonishing results, and what researchers found inside the models. How AI works The complete history of AI From Talos and Ada Lovelace to Turing, Deep Blue, AlphaGo and ChatGPT. Data & encoding How a computer knows a file isn’t broken Parity, checksums, hashes and ECC — and why backups need checking. Stanford Encyclopedia of Philosophy Turing machines The deep version: formal definitions, the universal machine and the limits of computation.