EXAMPLE 3.7 = {02" | n > 0}, the Here we describe a Turing machine (TM) M2 that decides A language consisting of all strings of Os whose length is a power of 2. 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 Os was odd, reject. 4. Return the head to the left-hand end of the tape. 5. Go to stage 1." Each iteration of stage 1 cuts the number of Os in half. As the machine sweeps across the tape in stage 1, it keeps track of whether the number of Os seen is even or odd. If that number is odd and greater than 1, the original number of Os in the input could not have been a power of 2. Therefore, the machine rejects in this instance. However, if the number of Os seen is 1, the original number must have been a power of 2. So in this the machine accepts. Now we give the formal description of M2 case, • Q = {91, 92, 93, 94, 95, Jaccept, reject}, • Σ= = {0}, and • I = {0,x,u}. = (Q, E, F, 8, 91, accept, reject): • We describe & with a state diagram (see Figure 3.8). The start, accept, and reject states are 91, accept, and greject, respectively. 3.1 This exercise concerns TM M2, whose description and state diagram appear in Ex- ample 3.7. In each of the parts, give the sequence of configurations that M2 enters when started on the indicated input string. a. O. Ab. 00. c. 000. d. 000000.

EXAMPLE 3.7 = {02" | n > 0}, the Here we describe a Turing machine (TM) M2 that decides A language consisting of all strings of Os whose length is a power of 2. 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 Os was odd, reject. 4. Return the head to the left-hand end of the tape. 5. Go to stage 1." Each iteration of stage 1 cuts the number of Os in half. As the machine sweeps across the tape in stage 1, it keeps track of whether the number of Os seen is even or odd. If that number is odd and greater than 1, the original number of Os in the input could not have been a power of 2. Therefore, the machine rejects in this instance. However, if the number of Os seen is 1, the original number must have been a power of 2. So in this the machine accepts. Now we give the formal description of M2 case, • Q = {91, 92, 93, 94, 95, Jaccept, reject}, • Σ= = {0}, and • I = {0,x,u}. = (Q, E, F, 8, 91, accept, reject): • We describe & with a state diagram (see Figure 3.8). The start, accept, and reject states are 91, accept, and greject, respectively. 3.1 This exercise concerns TM M2, whose description and state diagram appear in Ex- ample 3.7. In each of the parts, give the sequence of configurations that M2 enters when started on the indicated input string. a. O. Ab. 00. c. 000. d. 000000.