Below you will find the state transition table for a "palindrome detecting" Turing machine. You give the machine a string of a's and b's, followed by an 'x' to mark the end of the string. When you start the machine at the leftmost letter of the string, it works away and eventually detects whether that string is a palindrome. We write down the state transition table in the following format: This means that if we are in state s, and the current cell under the read/write head contains symbol i, then write w on the cell, move the head in the d direction, and then go to state s. In the instructions below, L and R stand for left and right directions, and states are numbered 0 through 7. There are three symbols: a, b, x. The asterisk ( ") means any symbol (i.e., either a,b, or x). Ce,a) - (x,R,1) State 0 (start state) Ce,b) -(x,R,2) (e,x) -> (x,L,5) We have a palindrome/ (1,a) ->Ca,R,1) Seen an "a"; skip to right end of the input to look for match Seen a "b", end of the input to look for match skip to right (2,a) -> (a,R,2) (2,b) (b,R,2) /* (3,a)-> (x,L,7) /* Test right end for "a" (3,x) -x,L,5) (4,a) -> (a,L,6) / Test right end for "b" C4,b) -> (x,L,7) (5, -> halt (6, *) -> halt Found a palindrome / /* Did not find a pal indrone (7,a) ->Ca,L,7) Already found a match at the right end; (7,b) -> (b,L,7) now returning to left end of input */