Introduction
Finite automata have a fixed memory; pushdown automata add a stack. Alan Turing's 1936 model goes further and is surprisingly simple: a finite control that reads and writes an unlimited tape, moving one cell at a time in either direction. Despite its simplicity, a Turing machine can do anything a modern computer can do, given time. It is the model on which the limits of computation, decidability and complexity are all defined.
How it works
A Turing machine has:
- a tape divided into cells, unlimited in both directions; the input is written at the start and every other cell holds the blank symbol _;
- a head that points at one cell;
- a finite set of states, with a start state and halting states (accept and reject);
- a transition function: δ(state, symbol) = (new state, symbol to write, move), where the move is left (L) or right (R).
Each step reads the symbol under the head, writes a symbol there, moves the head one cell, and changes state. The machine halts when it enters a halting state, or when no move is defined. Unlike the earlier machines, it can also run forever.
Designing a machine. To add 1 to a binary number, the machine first moves right to the end of the number, then adds with carry, moving left:
- a 1 becomes 0 and the carry continues left;
- a 0 becomes 1 and the machine stops;
- a blank (the number was all 1s) becomes 1 and the machine stops.
In Python, a dictionary is a natural tape: missing positions are blank, and negative positions work as well as positive ones.
The Church–Turing thesis says that every procedure that could be called an algorithm can be carried out by a Turing machine. It cannot be proved, because "algorithm" is informal, but every model of computation proposed since 1936, including real programming languages, has turned out to be equivalent in power. A universal Turing machine reads the description of another machine from its tape and simulates it, which is exactly what your Python simulator does.
Syntax
delta = {("q", "0"): ("q", "0", +1), ...} # (state, read) -> (state, write, move)
tape = dict(enumerate(word)) # missing cells are blank "_"
symbol = tape.get(head, "_")
state, write, move = delta[(state, symbol)]
tape[head] = write
head += move
Example
delta = {
("right", "0"): ("right", "0", +1),
("right", "1"): ("right", "1", +1),
("right", "_"): ("carry", "_", -1),
("carry", "1"): ("carry", "0", -1),
("carry", "0"): ("done", "1", -1),
("carry", "_"): ("done", "1", -1),
}
def run(word):
tape = dict(enumerate(word))
state, head, steps = "right", 0, 0
while state != "done":
symbol = tape.get(head, "_")
state, write, move = delta[(state, symbol)]
tape[head] = write
head += move
steps += 1
cells = range(min(tape), max(tape) + 1)
return "".join(tape.get(i, "_") for i in cells).strip("_"), steps
for word in ["1011", "111", "0"]:
result, steps = run(word)
print(f"{word} + 1 = {result} in {steps} steps")Line by line
- In state "right" the machine moves right over 0s and 1s; at the first blank it turns back into state "carry".
- In "carry", a 1 becomes 0 and the carry continues left; a 0 or a blank becomes 1 and the machine enters "done".
runkeeps the tape in a dictionary, so the head may move to position −1 when the number grows a digit.- The result is the written part of the tape with surrounding blanks removed, and
stepscounts the moves. - 1011 (eleven) becomes 1100 (twelve), and 111 (seven) becomes 1000 (eight), the case where the head moves left of the input.
Expected result
1011 + 1 = 1100 in 8 steps
111 + 1 = 1000 in 8 steps
0 + 1 = 1 in 3 steps
In the real world
Every computer, phone and server is, in theory, a Turing machine with a finite tape. Interpreters, emulators and virtual machines such as the JVM are universal machines: programs that run other programs from their descriptions. The model also defines which problems no computer can ever solve, which is the subject of the next lesson.
Common mistakes
- Moving past the end of a Python list: use a dictionary, or grow the list in both directions.
- Forgetting the blank symbol: the input is surrounded by blanks, and the machine must handle them.
- Missing a transition, which halts the machine unexpectedly.
- Assuming every machine halts: always put a step limit on a simulation.
Best practices
- Plan the machine in words (phases such as "move right", "carry") before writing moves.
- Name states after what they are doing.
- Print the tape and head after each step when debugging a machine.
Summary
A Turing machine reads and writes an unlimited tape one cell at a time, moving left or right as its transitions say. It halts in an accepting or rejecting state, or runs forever. A dictionary makes a simple tape in Python. By the Church–Turing thesis, Turing machines capture everything algorithms can compute.
Quick check
Key takeaways
- A Turing machine reads one cell, writes it, moves one step and changes state, again and again.
- Its tape is unlimited, so it has no fixed memory bound, unlike DFAs and PDAs.
- A Turing machine may halt and accept, halt and reject, or run forever.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.