A turing machine that detects a palindrome over {a,b}.  

Starts at the beginning of the tape, and matches symbols at the start of the
tape with symbols at the end.  Deletes the symbol pairs that match.

(0  9r  Done.  We have found a palindrome.
(0a 7r  First character is an 'a'.
(0b 8r  First character is a 'b'.
(7  9r  |   There was only
(8  9r  |      one character.  Found a palindrome.
(7aa1r   |
(7bb1r   |  There is more than one character,
(8aa2r   |     go to state 1 if we read an 'a',
(8bb2r   |     go to state 2 if we read a 'b'.
(1aa1r  |
(1bb1r  | Once we have found an 'a' or a 'b', move
(2aa2r  |      to the end of the tape to see
(2bb2r  |      if there is a match.
(1  3l  |
(2  4l  |
(3a 6l   |  state 3: need to match an 'a'
(4b 6l   |  state 4: need to match a 'b'
(6aa6l  |
(6bb6l  |  Last match was okay.  Go back to start of tape.
(6  0r  |