6.4Church–Turing thesis and TM design
The idea
Designing a TM usually means a mark-and-scan loop: mark one symbol, find its partner, mark it, return, repeat.
Think of it like this: Crossing off matching items on two shopping lists.
Why it exists
It gives a feel for what a TM can do and why comparisons cost quadratic time.
How it works
- Mark the leftmost unmarked symbol.
- Move to find its match and mark it.
- Return to the left end and repeat.
- Accept when everything is marked and nothing is left over.
Worked example: aⁿbⁿcⁿ
Mark an a, then a b, then a c, return, repeat. It accepts aabbcc and rejects aabbc. A PDA cannot do this, a TM can.
Now play with it
- →Run the aⁿbⁿcⁿ machine on
aabbccandaabbc. - →Try the binary-increment machine on
1011.
state q0 · head at cell 0
- 0. start
- 1. δ(q0, a) = (q1, X, R)
- 2. δ(q1, a) = (q1, a, R)
- 3. δ(q1, b) = (q2, Y, R)
- 4. δ(q2, b) = (q2, b, R)
- 5. δ(q2, c) = (q3, Z, L)
- 6. δ(q3, b) = (q3, b, L)
- 7. δ(q3, Y) = (q3, Y, L)
- 8. δ(q3, a) = (q3, a, L)
- 9. δ(q3, X) = (q0, X, R)
- 10. δ(q0, a) = (q1, X, R)
- 11. δ(q1, Y) = (q1, Y, R)
- 12. δ(q1, b) = (q2, Y, R)
- 13. δ(q2, Z) = (q2, Z, R)
- 14. δ(q2, c) = (q3, Z, L)
- 15. δ(q3, Z) = (q3, Z, L)
- 16. δ(q3, Y) = (q3, Y, L)
- 17. δ(q3, Y) = (q3, Y, L)
- 18. δ(q3, X) = (q0, X, R)
- 19. δ(q0, Y) = (q4, Y, R)
- 20. δ(q4, Y) = (q4, Y, R)
- 21. δ(q4, Z) = (q4, Z, R)
- 22. δ(q4, Z) = (q4, Z, R)
- 23. δ(q4, _) = (qa, _, S)
- Halts: ACCEPT
Result: accept in 23 steps. A missing rule means the machine rejects.
Check yourself
The Church–Turing thesis says that
Exam notes (the dense version)
Anything that is intuitively computable is computable by a TM. To design a TM: mark a symbol, scan to its partner, mark that, return to the start, repeat; accept when all are marked. The number of steps is usually Θ(n²) for such comparisons.
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.