Every computational model studied so far in this course has had a clear weakness. Finite automata cannot count. Pushdown automata can count once, using a single stack, but cannot coordinate several counts at the same time, as the pumping lemma for context-free languages proved in the previous chapter. Each new model solved the previous model's limitation by adding a specific, restricted kind of memory. This chapter introduces the machine that removes the restriction entirely: the Turing machine, a model with an unlimited amount of memory and complete freedom to move around within it.
The Turing machine, introduced by Alan Turing in 1936, is widely regarded as the most important computational model in the entire history of computer science. It was not designed with electronic computers in mind, since none existed yet; it was designed to answer a deep mathematical question about what "computation" even means. Remarkably, despite being conceived decades before the first electronic computer was built, the Turing machine remains the gold standard against which every modern computer's computational power is still measured today.
In this tutorial, you will learn the formal definition of a Turing machine, how its tape and read-write head operate, how to represent its configuration using instantaneous descriptions, and a complete worked example designing and tracing a Turing machine that solves a genuinely useful task. By the end, you will understand why this deceptively simple machine is considered as powerful as any computer that has ever been built.
A Turing machine consists of an infinitely long tape, divided into individual cells, each capable of holding a single symbol. A read-write head sits over one cell of the tape at any given moment, capable of reading the symbol currently under it, writing a new symbol to replace it, and then moving one cell to the left or one cell to the right. Based on the machine's current state and the symbol it reads, the machine's transition function determines what symbol to write, which direction to move, and which state to enter next.
This might sound almost identical to a pushdown automaton at first glance, but the differences are enormous in practice. A PDA's stack can only be accessed at its very top, following strict last-in-first-out rules, and once a stack symbol is popped, it is gone. A Turing machine's tape, by contrast, can be read from and written to at any position the head can reach, the head can move freely back and forth in either direction, and any cell that has already been written can be revisited and even overwritten again later. This unrestricted read-write access to unlimited memory is precisely what gives the Turing machine its enormous computational power.
A Turing machine is formally defined as a 7-tuple (Q, Σ, Γ, δ, q0, B, F).
| Component | Meaning |
|---|---|
| Q | A finite, non-empty set of states the machine can be in. |
| Σ | The input alphabet, the set of symbols allowed to appear in the initial input written on the tape. |
| Γ | The tape alphabet, a superset of Σ that also includes the special blank symbol, used for any symbols that may be written during computation. |
| δ | The transition function, mapping a state and a tape symbol to a new state, a symbol to write, and a direction to move, left or right. |
| q0 | The start state, where the machine begins with its head positioned at the first symbol of the input. |
| B | The blank symbol, filling every tape cell that has not yet been written to. |
| F | The set of accepting or final states. |
Unlike a PDA's transition function, which produces a set of possible outcomes, a standard deterministic Turing machine's transition function produces exactly one outcome for every combination of state and symbol, specifying precisely what to write, which direction to move, and which state to enter next.
Since a Turing machine's tape can be extremely long, and only a small portion of it is usually relevant at any given moment, it is common to describe the machine's current configuration using a shorthand notation called an instantaneous description, or ID. An instantaneous description shows the tape contents around the head, with the current state written directly into the string at the exact position of the read-write head.
Tape contents: 0 0 1 1 Head currently over the third cell (the first 1) Current state: q1 Instantaneous description: 00 q1 11
This notation is extremely convenient for tracing a Turing machine's execution step by step, since each move of the machine corresponds to a clean, readable transformation from one instantaneous description to the next, without needing to redraw the entire tape at every step.
Consider the task of designing a Turing machine that takes a binary number written on the tape and produces that number plus one, written back onto the tape, overwriting the original. This is a genuinely practical example, unlike the pure language-recognition examples used in earlier chapters, and it nicely demonstrates why unrestricted tape access matters: incrementing a binary number sometimes requires carrying a 1 all the way from the rightmost digit back toward the left, potentially flipping many digits along the way.
The overall strategy is to first move the head all the way to the rightmost digit of the number, then begin moving leftward, flipping any 1 encountered into a 0 and continuing the carry, until either a 0 is found, which gets flipped into a 1 and the process stops, or the machine runs off the left edge of the number entirely, in which case a new 1 must be written in front of all the existing digits.
States: { q0, q1, q2, qaccept }
Input alphabet: { 0, 1 }
Tape alphabet: { 0, 1, B }
Start state: q0
Blank symbol: B
Accepting state: { qaccept }
| Current State | Symbol Read | Write | Move | Next State |
|---|---|---|---|---|
| q0 | 0 | 0 | Right | q0 |
| q0 | 1 | 1 | Right | q0 |
| q0 | B | B | Left | q1 |
| q1 | 1 | 0 | Left | q1 |
| q1 | 0 | 1 | Right | qaccept |
| q1 | B | 1 | Right | qaccept |
State q0 handles the first phase, simply scanning rightward past every digit until it reaches the blank symbol marking the end of the number, then switching into state q1 and moving one step back onto the last actual digit. State q1 handles the carry itself, flipping every 1 it encounters into a 0 while continuing to move left, since a 1 becoming 0 always triggers a carry into the next digit. As soon as q1 either finds a 0, which becomes a 1 with no further carry needed, or runs off the left edge of the number entirely, encountering a blank symbol, the machine writes a fresh 1 and halts in the accepting state.
Initial tape: 0 1 1 Initial ID: q0 011 q0 011 → 0 q0 11 (read 0, move right, stay in q0) 0 q0 11 → 01 q0 1 (read 1, move right, stay in q0) 01 q0 1 → 011 q0 B (read 1, move right, stay in q0) 011 q0 B → 01 q1 1B (read B, move left, switch to q1) Now in q1, reading the last actual digit, a 1: 01 q1 1 → 0 q1 10 (read 1, write 0, move left, stay in q1) Now in q1, reading the next digit, also a 1: 0 q1 10 → q1 010 (read 1, write 0, move left, stay in q1) Now in q1, reading the first digit, a 0: q1 010 → 1 qaccept 10 (read 0, write 1, move right, switch to qaccept) Final tape: 100
The original input, 011, representing the number three in binary, correctly becomes 100, representing the number four, exactly the expected result of incrementing three by one. Notice how the carry rippled leftward through both of the trailing 1s, flipping each one to 0, before finally reaching the leading 0 and flipping it to 1, exactly the behavior expected of binary addition by hand.
The increment example above highlights the key advantage a Turing machine has over a pushdown automaton: the ability to move freely in both directions and to overwrite previously written symbols as many times as needed. A PDA's stack can only ever be accessed at its top, and information once popped is permanently lost, making an operation like flipping an arbitrary number of digits somewhere in the middle of previously processed input essentially impossible.
Turing machines can recognize every context-free language a PDA can recognize, every regular language a finite automaton can recognize, and additionally, languages like 0^n 1^n 2^n from the previous two chapters, which no PDA can handle. In fact, Turing machines can compute essentially anything that is intuitively "computable" at all, a claim formalized by the Church-Turing thesis, introduced briefly back in the very first chapter of this course.
| Aspect | Pushdown Automaton | Turing Machine |
|---|---|---|
| Memory Structure | A single stack, accessible only at the top. | An infinite tape, accessible and writable at any position the head can reach. |
| Movement | Reads input strictly left to right, one symbol at a time. | The read-write head can move left or right freely, revisiting any cell as needed. |
| Can Overwrite Data? | No, popped stack symbols are permanently discarded. | Yes, any tape cell can be rewritten any number of times. |
| Language Class | Context-free languages. | Recursively enumerable languages, the most general class studied in this course. |
| Mistake | Correct Understanding |
|---|---|
| Assuming a Turing machine's tape is finite in length. | The tape is considered infinite in at least one direction, providing effectively unlimited memory for computation. |
| Believing a Turing machine can only move in one direction, like a PDA reading input. | A Turing machine's head can move both left and right freely, revisiting cells as many times as needed. |
| Forgetting that a Turing machine can overwrite the same cell multiple times. | Unlike a PDA's stack, tape cells can be read and rewritten repeatedly throughout the computation. |
| Confusing accepting a language with computing a function. | Turing machines can be used both to accept or reject strings, as in this course's earlier automata, and to compute output values, as demonstrated in the binary increment example. |
The Turing machine removes the restrictions found in every earlier computational model studied in this course, replacing a finite automaton's fixed states or a pushdown automaton's single stack with an infinite, freely accessible tape. Through its formal definition, the instantaneous description notation, and a fully traced example incrementing a binary number, this chapter demonstrated exactly why this simple-looking machine remains the standard against which all computation is measured, even decades after its introduction.
In this tutorial, you learned the formal 7-tuple definition of a Turing machine, how instantaneous descriptions represent its configuration, and walked through a complete worked example designing and tracing a Turing machine that increments a binary number. With this foundation, you are ready to move on to the variants of Turing machines, including multi-tape and non-deterministic versions, and to see how each of these variants compares in power to the standard single-tape model introduced here.