Building a deterministic one tape turing machine

Question

I am trying to make a deterministic turing machine to do the following: find the middle letter of any word. it needs to take as input, a word containing only a's and b's and once it finds the middle character it needs to halt and accept. the machine needs to reject any word with an even number of letters and only accept odd length words. Left/right/stay moves are all allowed to be used in this machine.

The following notation is to be used: STATE, SYMBOL -> STATE, SYMBOL, DIRECTION

(_) = blank space

(l) = left move

(r) = right move

(s) = stay

I can't visualize this machine at all and need help starting. I have tried to build the machine myself but it never works for all inputs and I can only get it to work for specific words. if you can help me I would appreciate it. Thanks

Answer 1

It's unclear to me whether you need to simply recognize that there is a middle symbol (i.e., the input size is odd), you need to recognize this and end processing on the middle symbol, or you need to recognize this, erase the input, write the middle symbol to the beginning of the tape, and then accept. We'll assume the second of these and then discuss how to accomplish the third.

An easy way to solve this problem is to cross off pairs of symbols from the beginning and end of the input. If you run out of symbols after crossing off a whole number of pairs, then you halt-reject; otherwise, if you're unable to find a match for the last pair, then you halt-accept. Here's a TM that does just this:

Q    T     Q'    T'    D
q0   a,b   q1    A,B   right    // if we have a symbol, begin crossing off
q0   #,A,B hR    #,A,B same     // otherwise, |w| is even so halt reject

q1   a,b   q1    a,b   right    // go to the first blank or marked-off symbol
q1   #,A,B q2    #,A,B left     // then, go one to the left

q2   a,b   q3    A,B   left     // if we have a symbol, mark off the pair
q2   A,B   hA    a,b   same     // otherwise, |w| is odd so halt accept

q3   a,b   q3    a,b   left     // find the last marked-off symbol from the front
q3   A,B   q0    A,B   right    // move one to the right and repeat the whole thing

This TM will turn a string like aababab into AABaBAB with the read head on a. From this form, we could add some more processing to turn the tape into a, aababab, etc. and leave the read head wherever you like.