For $TM{M}_2,$ whose description and state diagram appear below.

Here we describe a Turing machine $($TM$)M_2$ that decides $A=\{0^{2^n}|n0\},$ the

language consisting of all strings of $0s$ whose length is a power of $2.$

$M_2="$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 end of the tape.

Go to stage $1."$

Now we give the formal description of $M_2=(Q,,,,q_1,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}})$ :

$Q=\{q_1,q_2,q_3,q_4,q_5,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}\},$

$=\{0\},$ and

$=\{0,x,\}.$

We describe $$ with a state diagram $($see Figure $3\mathrm{.}8).$

The start, accept, and reject states are $q_1,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},$ and $q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}},$ respectively.