A Turing machine has no stack, but it can write on its tape and move both ways, which is enough to do anything a computer can. The usual first exercise is aⁿbⁿ: a pushdown automaton needs a stack for it; a Turing machine solves it by marking symbols it has already matched.
The idea
Repeat until done:
- Find the leftmost unmarked a and mark it X.
- Move right past the a's and already-matched b's to the first unmarked b, and mark it Y.
- Walk back left to the last X, and start again one cell to its right.
When no a's are left, check that only Y's remain before the blank. If so, accept. Any leftover a or b means the counts didn't match.
The transition table
Each rule reads state, symbol → new state, symbol to write, move (L, R or S for stay). _ is the blank.
q0, a → q1, X, R mark an a, go find its b
q0, Y → q3, Y, R no a's left: check the rest
q0, _ → qa, _, S empty input: accept (n = 0)
q1, a → q1, a, R skip a's
q1, Y → q1, Y, R skip matched b's
q1, b → q2, Y, L mark the b, head back
q2, a → q2, a, L walk left over a's
q2, Y → q2, Y, L ...and over Y's
q2, X → q0, X, R found the last X: start the next round
q3, Y → q3, Y, R only Y's allowed now
q3, _ → qa, _, S reached the blank: accept
Any (state, symbol) pair with no rule means reject: for example q1 reaching the blank (an a with no matching b), or q3 finding a b (too many b's).
Every move on aabb
The head's cell is in brackets.
| Move | State | Tape | Rule applied |
|---|---|---|---|
| 0 | q0 | [a]abb | q0, a → q1, X, R |
| 1 | q1 | X[a]bb | q1, a → q1, a, R |
| 2 | q1 | Xa[b]b | q1, b → q2, Y, L |
| 3 | q2 | X[a]Yb | q2, a → q2, a, L |
| 4 | q2 | [X]aYb | q2, X → q0, X, R |
| 5 | q0 | X[a]Yb | q0, a → q1, X, R |
| 6 | q1 | XX[Y]b | q1, Y → q1, Y, R |
| 7 | q1 | XXY[b] | q1, b → q2, Y, L |
| 8 | q2 | XX[Y]Y | q2, Y → q2, Y, L |
| 9 | q2 | X[X]YY | q2, X → q0, X, R |
| 10 | q0 | XX[Y]Y | q0, Y → q3, Y, R |
| 11 | q3 | XXY[Y] | q3, Y → q3, Y, R |
| 12 | q3 | XXYY[_] | q3, _ → qa, _, S |
| 13 | qa | XXYY[_] | accept |
13 moves. The machine also accepts ab and the empty string, and rejects aab (q1 hits the blank looking for a b) and abb (q3 finds the extra b).
A second example: binary +1
Turing machines compute, not just accept. This one adds 1 to a binary number: walk to the right end, then turn trailing 1s into 0s until a 0 (or the blank) can become 1.
q0, 0 → q0, 0, R
q0, 1 → q0, 1, R
q0, _ → q1, _, L reached the end: start carrying
q1, 1 → q1, 0, L 1 + carry = 0, keep carrying
q1, 0 → qa, 1, S 0 + carry = 1, done
q1, _ → qa, 1, S ran off the left: new leading 1
On 1011 (eleven) it leaves 1100 (twelve) on the tape.
Common mistakes
- Not marking matched symbols. Erasing them to blanks makes it hard to find your way back; X and Y keep the tape readable.
- Forgetting the final check. Without q3, a machine can accept aabbb by matching two pairs and never looking at the last b.
- Moving the wrong way after writing. Each rule writes first, then moves.
- Leaving out n = 0. If the language includes the empty string, the machine must accept a blank tape.
Try it
The Turing machine simulator includes this machine, binary +1 and a palindrome checker. Step through any input and watch the head and tape at every move, or write your own rules in the same format. Compare it with the PDA for aⁿbⁿ, which solves the same language with a stack.
Use the Finite Automata Simulator (NFA/DFA) to experiment with finite-automaton examples.