M2

A Turing Machine that decides 02n

M2 = “On input string w:

  1. Sweep left to right across the tape, crossing off every other 0.
  2. If in stage 1 the tape contained a single 0, accept.
  3. If in stage 1 the tape contained more than a single 0 and the number of 0’s was odd, reject.
  4. Return the head to the left-hand side of the tape.
  5. Go to stage 1.