A Turing Machine that decides 02n
M2 = “On input string w:
- Sweep left to right across the tape, crossing off every other 0.
- If in stage 1 the tape contained a single 0, accept.
- If in stage 1 the tape contained more than a single 0 and the number of 0’s was odd, reject.
- Return the head to the left-hand side of the tape.
- Go to stage 1.