1. Describe a TM that accepts the set {an | n is a power of 2}. Your description should be at the level of the descriptions in Lecture 29 of the TM that accepts {ww We {*} and the TM that implements the sieve of Eratosthenes. In particular, do not give a list of transitions. Example 29.1 Consider the non-CFL {ww | W {a,b}*}. It is a recursive set, because we can give a total TM M for it. The machine M works as follows. On input 2, it scans out to the first blank symbol u, counting the number of symbols mod 2 to make sure x is of even length and rejecting immediately if not. It lays down a right endmarker 4, then repeatedly scans back and forth over the input. In each pass from right to left, it marks the first unmarked a or b it sees with '. In each pass from left to right, it marks the first unmarked a or b it sees with : It continues this until all symbols are marked. For example, on input a abba a abba the initial tape contents are Faabba a abbauuu... and the following are the tape contents after the first few passes. Faabba a abb tuuu... ... H abba a ab 6 tuuu... F bba a ab tuuu... F b b a a a tuuu... Marking a with formally means writing the symbol E T; thus T = {a, b, t, u, 7, , , , 6}. When all symbols are marked, we have the first half of the input string marked with and the second half marked with '. F tuuu... The reason we did this was to find the center of the input string. The machine then repeatedly scans left to right over the input. In each pass it erases the first symbol it sees marked with 'but remembers that symbol in its finite control (to erase really means to write the blank symbol u). It then scans forward until it sees the first symbol marked with ', checks that that symbol is the same, and erases it. If the two symbols are not the same, it rejects. Otherwise, when it has erased all the symbols, it accepts. In our example, the following would be the tape contents after each pass. tuuu... L b b u 5 6 7 Huuu. b a usb -.. www wuu tuuu... uuuuuuuutuuu... uuuuuuuuuuuuu... ) Example 29.2 We want to construct a total TM that accepts its input string if the length of the string is prime. This language is not regular or context-free. We will give a TM implementation of the sieve of Eratosthenes, which can be described informally as follows. Say we want to check whether n is prime. We write down all the numbers from 2 to n in order, then repeat the following: find the smallest number in the list, declare it prime, then cross off all multiples of that number. Repeat until each number in the list has been either declared prime or crossed off as a multiple of a smaller prime. For example, to check whether 23 is prime, we would start with all the numbers from 2 to 23: 2 3 4 5 6 7 8 9 10 11 4 12 13 14 15 16 17 18 19 20 21 22 23 In the first pass, we cross off multiples of 2: X 3 X 5 X 7 X 9 DO 11 13 15 DO 17 18 19 20 21 % 23 The smallest number remaining is 3, and this is prime. In the second pass we cross off multiples of 3: X X X 5 X 7 X X do 11 d 13 De 17 & 19 20 * x 23 Then 5 is the next prime, so we cross off multiples of 5; and so forth. Since 23 is prime, it will never be crossed off as a multiple of anything smaller, and eventually we will discover that fact when everything smaller has been crossed off. Now we show how to implement this on a TM. Suppose we have a written on the tape. We illustrate the algorithm with p= 23. Faa aa a aa aa a aa a aa a aa aa a aauuu... If p= 0 or p= 1, reject. We can determine this by looking at the first three cells of the tape. Otherwise, there are at least two as. Erase the first a, scan right to the end of the input, and replace the last a in the input string with the symbol $. We now have an a in positions 2, 3, 4, ...,P-1 and $ at position p. Fuaa a a aa a aa a aa aa a aa a a a a $ uuu... Now we repeat the following loop. Starting from the left endmarkert, scan right and find the first nonblank symbol, say occurring at position m. Then m is prime (this is an invariant of the loop). If this symbol is the $, we are done: p = m is prime, so we halt and accept. Otherwise, the symbol is an a. Mark it with a^and everything between there and the left endmarker with '. Fa a aa a a aa a a a a a aa a a a a a $ uuu... We will now enter an inner loop to erase all the symbols occurring at posi- tions that are multiples of m. First, erase the a under the . (Formally, just write the symbol ll.) Fa a a a a a a a a a a a a a a a a a a a $ uuu... Shift the marks to the right one at a time a distance equal to the number of marks. This can be done by shuttling back and forth, erasing marks on the left and writing them on the right. We know when we are done because the is the last mark moved. Fuua a a a a a a a a a a a a a a a a a $ uuu... When this is done, erase the symbol under the. This is the symbol occurring at position 2m. Fuualla a aa a aa a La aa a a $uuu... Keep shifting the marks and erasing the symbol under the in this fashion until we reach the end. Fua ua ua ua ua ua ua ua ua ua us... If we find ourselves at the end of the string wanting to erase the $, reject-p is a multiple of m but not equal to m. Otherwise, go back to the left and repeat. Find the first nonblank symbol and mark it and everything to its left. F uauauauauaua wauawa u$ uuu... Alternately erase the symbol under the and shift the marks until we reach the end of the string. Fuuuua wauunawa uuwawavus uu... Go back to the left and repeat. F uauuuauauuuauauuuuuu... If we ever try to erase the $, reject-p is not prime. If we manage to erase all the a's, accept