6.1The Turing machine model
The idea
A Turing machine has an infinite tape, a head that reads and writes, and a finite set of states. It can accept, reject or loop forever.
Think of it like this: A person with an endless notebook and a fixed list of rules.
Why it exists
It is the standard model of what can be computed at all.
How it works
- δ(q, a) = (p, b, L/R): write b, move, change state.
- Accepts by reaching the accept state.
- May also reject or never halt.
- Decide = always halts with the right answer; recognise = accepts exactly the members.
Worked example: aⁿbⁿ with markers
Mark an a (X), find a b and mark it (Y), return, repeat. When only Y's remain, accept. Total work is about n² steps.
Now play with it
- →Step through
aaabbband watch the head mark symbols. - →Try
aabbband see a rejection.
state q0 · head at cell 0
- 0. start
- 1. δ(q0, a) = (q1, X, R)
- 2. δ(q1, a) = (q1, a, R)
- 3. δ(q1, a) = (q1, a, R)
- 4. δ(q1, b) = (q2, Y, L)
- 5. δ(q2, a) = (q2, a, L)
- 6. δ(q2, a) = (q2, a, L)
- 7. δ(q2, X) = (q0, X, R)
- 8. δ(q0, a) = (q1, X, R)
- 9. δ(q1, a) = (q1, a, R)
- 10. δ(q1, Y) = (q1, Y, R)
- 11. δ(q1, b) = (q2, Y, L)
- 12. δ(q2, Y) = (q2, Y, L)
- 13. δ(q2, a) = (q2, a, L)
- 14. δ(q2, X) = (q0, X, R)
- 15. δ(q0, a) = (q1, X, R)
- 16. δ(q1, Y) = (q1, Y, R)
- 17. δ(q1, Y) = (q1, Y, R)
- 18. δ(q1, b) = (q2, Y, L)
- 19. δ(q2, Y) = (q2, Y, L)
- 20. δ(q2, Y) = (q2, Y, L)
- 21. δ(q2, X) = (q0, X, R)
- 22. δ(q0, Y) = (q3, Y, R)
- 23. δ(q3, Y) = (q3, Y, R)
- 24. δ(q3, Y) = (q3, Y, R)
- 25. δ(q3, _) = (qa, _, S)
- Halts: ACCEPT
Result: accept in 25 steps. A missing rule means the machine rejects.
Check yourself
A TM that never halts on some input and accepts all strings of L is
Exam notes (the dense version)
A TM has an infinite tape, a read/write head and a finite control: δ(q, a) = (p, b, L/R). It accepts by entering the accept state, rejects by entering the reject state, or loops forever. A language is recognised if the TM accepts exactly its strings, and decided if the TM also always halts.
Previous year questions: Turing Machines (4)
PYQs are grouped by topic, so this is the full set for Turing Machines; try the ones that match this subtopic. Open all 4 on the topic page.