Programs without variables
Writing a Turing machine is programming with almost nothing: no variables, no arithmetic, no functions — just states and a tape. The skill is the same one you used for DFAs: the state remembers a small fact ("I erased an a and I'm looking for its partner"), while the tape holds everything big. Today you'll write two machines as data and run them on your simulator.
Palindromes are a good test: the language of strings that read the same backwards is context-free but not regular, and a Turing machine handles it by walking back and forth, crossing off matching letters from both ends.
The palindrome strategy
Erase the first letter and remember it in the state (seekA or seekB). Run right to the first blank — the end of what's left — then step left onto the last letter. If it matches, erase it too and walk back to the left end to start again. If it doesn't match, reject. When nothing is left, or one letter is left in the middle, accept.
- start: on a or b, write a blank and go to seekA / seekB; on a blank (nothing left), accept.
- seekA / seekB: move right over letters until a blank, then step left into lastA / lastB.
- lastA: an a matches — erase it and go back; a b means reject; a blank means the remembered letter was the middle one, so accept.
- back: move left over letters until a blank, then step right into start.
A machine for n letters takes about n²/2 steps — quadratic — because each pair costs a walk across the tape. Turing machines are about what's possible, not speed.