Consider the following specification of a Turing machine that, when placed on the leftmost letter of a string of a's and b's (where the end of the string is marked by an 'x' -- think of 'x' as denoting a blank cell on the tape), detects whether that string is a palindrome. We will write down the transition function in the following format:

(s, i) -> (s', w, d)

This would mean that if the Turing machine is in state s, and the current cell under the read/write head contains symbol i, then it changes to state s', writes w on the cell, and then moves the head in the d direction. In the instructions below, L and R stand for left and right directions, and the states are the numbers 0 through 7.

Note: The comments after the transition rules (text between /* and */) are just comments to help explain in conceptual terms what the Turing machine is "doing" when in different states. The actual functioning of the Turing machine is completely determined by the transition rules themselves.

CO, a) - (1,x, R) State 0 (start state) */ C0,b) - (2,x, R) CO, x) -> C5,x, L) (1,a) -> (1,a, R) /*Seen an askip to right end of the input to look for match* (2,a) -> (2,a, R) /*Seen a b; skip to right end of the input to look for match* (3,a) -> (7,x, L) Test right end for a * (3,x) -> C5,x, L) (4,a) -> (6,a, L) Test right end for b */ C4,b) - (7,x, L) C4,x) -> C5,x, L) 5,* ->halt (6,*) ->halt Found a palindrome* /* Did not find a palindrome */ (7,a) -> (7,a, L) Found a match at the right end; return to left end of input (7,x) -> C0,x, R)

Suppose that the machine starts with the following sequence of symbols on its input tape: a b a b x x x . . . Assume that the machine starts with the read/write head on the leftmost non-blank cell (so it is reading the first "a"), and starts in state 0.

If this Turing machine executes on this input:

a. What is the sequence of states that it will enter? Show your work. (Note: You should enter one state number for each step of the computation. The machine may enter the same state twice or more--you should still list that state each time it is entered.)
b. What are the contents of the tape at the end of the execution?