Computer Science › Section M · Theory of computation › Topic M.2
Turing machines
A Turing machine is little more than a tape, a head and a short table of rules, yet as far as anyone knows it can compute everything any computer can. That makes it the yardstick computer scientists use to measure what is computable at all.
A model of a person computing
In 1936, years before electronic computers, the British mathematician Alan Turing asked what a person could compute by following rules with pencil and paper. He stripped the activity to its essentials: a strip of paper divided into squares, attention on one square at a time, and a limited number of states of mind. The result is now called a Turing machine. It was never meant to be built as a practical device. It is a precise model of what "following an algorithm" means, simple enough to reason about and, it turns out, as powerful as any computer.
The parts of a Turing machine
A Turing machine has three parts. The tape is a row of cells that is unlimited in length; we let it extend in both directions. Each cell holds one symbol from a finite set called the alphabet, which always includes a blank, written _ here. The read/write head sits over one cell at a time. The control unit is always in one of a finite number of states, including a start state, where every run begins, and a halt state, where it ends. There is nothing else: no arithmetic unit and no memory apart from the tape.
One step at a time
Each step follows one rule. The machine reads the symbol under the head, then finds the rule for its current state and that symbol. The rule says which symbol to write in the cell (possibly the same one), whether to move the head one cell left (L), one cell right (R) or not at all (N), and which state to enter next. We write a rule as (SCAN, 1) → (1, R, SCAN): in state SCAN reading 1, write 1, move right and stay in SCAN. The full set of rules, the transition table, is the machine's program. There is at most one rule for each state and symbol, so the machine never has to choose.
A machine that adds
Write each number in unary, as that many 1s, so 3 + 2 becomes the tape 111+11. The head starts on the leftmost symbol in state SCAN. The idea is to turn the + into a 1, giving six 1s, then erase one 1 from the end. Four rules do it:
In the traces below, square brackets mark the cell under the head.
Worked example: tracing the adder
Start: [1]11+11 in state SCAN. 1. Steps 1 to 3: SCAN reads three 1s, rewrites each and moves right, reaching 111[+]11. 2. Step 4: SCAN reads +, writes 1 and moves right: 1111[1]1. 3. Steps 5 and 6: two more 1s pass, and the head reaches the blank after them: 111111[_]. 4. Step 7: SCAN reads the blank, moves left and enters ERASE: 11111[1]. 5. Step 8: ERASE replaces that 1 with a blank and enters HALT: 11111[_]. Check: five 1s remain, and 3 + 2 = 5. The run took 8 steps, and the same four rules add any two unary numbers.
Worked example: an even-parity checker
This machine decides whether a string of 0s and 1s contains an even number of 1s, writing Y or N in the blank after it. Its state remembers the answer so far:
Run it on 1011, starting in EVEN. 1. Read 1: ODD. 2. Read 0: still ODD. 3. Read 1: EVEN. 4. Read 1: ODD, and the head reaches the blank. 5. ODD reading a blank writes N and halts: 1011[N]. Check: 1011 has three 1s, an odd number.
Computing functions, and never halting
To compute a function with a Turing machine, write the input on the tape, run the machine and read the output from the tape once it halts. A function that some Turing machine computes in this way is called Turing computable; the adder computes addition. But nothing forces a machine to halt. One with the rules (GO, 1) → (1, R, GO) and (GO, _) → (_, R, GO) moves right forever, since every cell it meets keeps it in state GO. If a machine never halts on some input, it gives no output there. Whether a machine will halt turns out to be a deep question, taken up in "A noncomputable function: the halting problem".
The Church–Turing thesis
Turing proposed that his machines can compute every function that can be computed by any algorithm. Alonzo Church reached the same conclusion with a different system, the lambda calculus, also in 1936, and the claim is now called the Church–Turing thesis. It is a thesis, not a theorem, because "algorithm" is an informal idea, so the claim cannot be proved mathematically. The evidence is strong: every other general model of step-by-step computation proposed so far, including Emil Post's, has been proved to compute exactly the same functions, and no one has found an algorithm that a Turing machine cannot imitate. Today the thesis is widely accepted.
Why the yardstick matters
The thesis turns Turing machines into a standard of comparison. A system that can imitate any Turing machine is as powerful as a computing system can be, which is how "Universal programming languages" judges languages. In the other direction, a problem that no Turing machine solves is beyond every algorithm. Adding features, such as several tapes or a larger alphabet, can make a machine faster but never lets it compute new functions. A real computer has finite memory, but a Turing machine can imitate it step by step, and given unlimited storage the computer could imitate any Turing machine in turn.
The universal machine
Turing's 1936 paper went further. Because a machine's rules are finite, they can be written as a string of symbols. Turing described a single universal Turing machine that reads such a description, followed by an input, from its tape, and then imitates the described machine step by step, producing the same result. One fixed machine can therefore carry out any algorithm, provided the algorithm is supplied as data. It is the same idea as the stored-program design of modern computers, described in "Computer architecture: CPU and stored programs".
Common mistakes to avoid
First, thinking the machine has infinitely many states: the states are finite, and only the tape is unlimited. Second, thinking the unlimited tape holds infinitely much data: at every moment only finitely many cells are not blank. Third, reading the output before the machine halts. Fourth, assuming every machine halts: the GO machine runs forever. Fifth, calling the Church–Turing thesis a proved theorem. Sixth, believing extra tapes or symbols add computing power; they can add speed, not new functions.
Key takeaways
A Turing machine has an unlimited tape of cells holding symbols from a finite alphabet, a read/write head and a control unit with finitely many states, including start and halt states. Each step reads a symbol, writes a symbol, moves left, right or not at all, and changes state, as its transition table directs. A function is Turing computable if some machine computes it, though machines need not halt. The Church–Turing thesis says the Turing-computable functions are exactly the computable ones. A universal Turing machine can imitate any other machine from its description.
Flashcards
Flashcard
A tape, a read/write head and a control unit following a table of rules
Test your understanding
Question 1 of 5
Which part of a Turing machine is limited to a finite number of possibilities?
Question 2 of 5
The four-rule adder from the reading starts on the tape 1+1, on the leftmost cell in state SCAN. What does the tape hold when it halts?
Question 3 of 5
The even-parity checker from the reading runs on 0110, starting in EVEN. What happens?
Question 4 of 5
Why is the Church–Turing thesis called a thesis rather than a theorem?
Question 5 of 5
What does a universal Turing machine do?
